I've got a question. How can i simulate Turing machine with a double-sided infinite tape by a Turing machine with one-sided infinite tape? The condition is, that the simulation of one step of the first machine must be equal to O(1) steps of second machine. Do you have any idea, how to do this?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ do you have more description about what a dopple sided tape is? what properties does it have and how does it work? $\endgroup$– Narek BojikianOct 23, 2019 at 19:30
-
$\begingroup$ I believe that you can find the transformation you look for in this document : staff.um.edu.mt/afra1/teaching/coco4.pdf $\endgroup$– TassleOct 23, 2019 at 22:24
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
As I understand your question, the double-sided machine has a tape indexed by $\mathbb{Z}$ and the one-sided has a tape indexed by $\mathbb{N}$.
The question then boils down to finding a bijection f between the two sets st. $\forall z \in \mathbb{Z}: |f(z) - f(z+1)| < k$ for some constant k. Can you find such a bijection:
Hint: k = 3 is sufficient.
