Time complexity versus space complexity in Turing machines
I think defenitions of time complexity and space complexity for Turing machines are identical and I can't differentiate between them.
Please help me. Thanks.
Answer
With regards to a Turing machine, time complexity is a measure of how many times the tape moves when the machine is started on some input. Space complexity refers to how many cells of the tape are written to when the machine runs.
The time complexity of a TM is connected to its space complexity. In particular, if tue space complexity of a TM is f(w) for input w, then its time complexity must be at least f(w), since the tape has to move at least f(w) steps to write out that many cells. Additionally, if the TM has tape alphabet Γ and set of states Q, then if the space complexity of the TM on an input w is f(w) and the TM halts on w, the time complexity must be at most |Q|Γf(n). To see this, note that the configuration of the TM at any point in its execution consists of a string of f(n) tape cells, each of which can contain any tape symbol, and can be in one of any of its |Q| states.
An interesting example of this distinction appears if you look at restricted Turing machines like the linear bounded automaton (LBA), a Turing machine that has its tape restricted to space proportional to the size of the input. Although the TM's space complexity is restricted to O(n), the time complexity of any particular LBA can be exponential in the size of the input.
Hope this helps!