1
$\begingroup$

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?

$\endgroup$
  • $\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 Bojikian Oct 23 '19 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$ – Tassle Oct 23 '19 at 22:24
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.