3
$\begingroup$

I am working on a proof of the theorem that every LEFT-RESET Turing machine has an equivalent conventional, single tape Turing machine. The transitions for the LEFT-RESET Turing machine are {Right, RESET}, and the transitions for the conventional Turing machine are {Left, Right}. Here is the general outline of my proof:

Given a LEFT-RESET Turing machine $T_1$ and a conventional, I will prove that $T_1$ has an equivalent conventional Turing machine $T_2$. There are two possible transitions for $T_1$: right and reset. The right transition of $T_1$ is identical to the right transition of $T_2$. When $T_1$ performs a reset, $T_1$ moves its read-write head left until it reaches the leftmost cell on the tape. Therefore, a LEFT-RESET Turing machine is equivalent to a conventional Turing machine. Q.E.D.

Do I have to prove that there is a series of transitions on $T_1$ that are equivalent to a single left transition on $T_2$? Other write-ups I have seen include this, but if the LEFT-RESET Turing machine cannot perform a traditional left transition as an operation, I do not understand why it is part of the proof.

$\endgroup$
1
$\begingroup$

The other write-ups you mention show that the two models are equivalent. That is, they also show that a normal Turing machine can be simulated by a left-reset Turing machine.

$\endgroup$
  • $\begingroup$ So proving a LEFT-RESET Turing machine is equivalent to a conventional Turing machine is not a "bi-directional" proof of showing that the two are equivalent to each other? $\endgroup$ – tpm900 Mar 13 '17 at 19:47
  • 1
    $\begingroup$ Showing that a single machine of one type is equivalent to a machine of another type is not the same as showing that one model is equivalent to another. $\endgroup$ – Yuval Filmus Mar 13 '17 at 19:48

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.