I have a question regarding proofs to show the equivalence of different turing machines and their possible time and space overhead:
I have to show, that a usual deterministic turing machine is equivalent to each of the following:
- read-only input turing machines, whiche can only write back the symbol it reads
- turing machines, that have alle tapes (except for the output tape) erased and only blanks when it halts
- double tape turing machines, where there is no left marker. Instead of that, there are infinitely many blank symbols to both sides.
My suggestions so far:
- Assuming we only have 0, 1 and blanks, then if we read 0 we write 0 and go right. If we read 1 we write 1 and go right and when we read a blank we halt. No time and space overhead. Would that be right?
- Before the halting state, we have to insert another state which goes to the left beginning and then writes only blanks while going right. If then there is a blank, it halts. Time over head would be O(n) i think and no space overhead.
- No idea for this one.
Maybe anyone could help me with this. Thank you very much.