How to prove that standard Turing machine is equivalent to a variant model where a string is accepted if the machine enters an accept state during computation? However, the machine may leave the accept state, and this action does not change the acceptance outcome.
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ Seems simple enough. What did you try? $\endgroup$– Karolis JuodelėCommented Nov 18, 2016 at 8:12
-
3$\begingroup$ You just have to show that given a 'variant' Turing machine $M$, you can construct a 'standard' Turing machine $M^\prime$ such that $L(M^\prime) = L(M)$. $\endgroup$– skankhunt42Commented Nov 18, 2016 at 8:21
-
$\begingroup$ I'm struggling to construct the turing machine which simulates the given criteria. $\endgroup$– sumoCommented Nov 18, 2016 at 16:39
-
$\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$– RaphaelCommented Dec 18, 2016 at 21:34
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
In order to prove that your modified Turing machine is equivalent to a standard Turing machine, you need to do two things:
Given a standard Turing machine $T_1$, give a modified Turing machine $T_2$ such that $L(T_1) = L(T_2)$.
Given a modified Turing machine $T_3$, give a standard Turing machine $T_4$ such that $L(T_3) = L(T_4)$.
Good luck!
answered Nov 18, 2016 at 11:28
-
$\begingroup$ Hey thanks for the info, but i know the steps involved. I'm not able to prove how L(T1)=L(T2) and L(T3)=L(T4). $\endgroup$– sumoCommented Nov 18, 2016 at 16:37
-
1$\begingroup$ Part 1 is trivial because every standard Turing machine is also a modified Turing machine (argue why!). For part 2, it might help if you write down the formal definition of acceptance of a modified Turing machine and try to work from there (i.e. how to convert it so that you get the standard acceptance condition and then show that the two Turing machines accept the same language). $\endgroup$ Commented Nov 18, 2016 at 17:03
$\begingroup$
$\endgroup$
You need to begin with a formal definition of a Turing Machine, such as the one given (from a common textbook) in Wikipedia:
The 7-tuple: $<Q,\Gamma,b,\Sigma,\delta,q_{0},F>$
Here $F$ is given as the Final or Acceptance States. In your example the Acceptance states are not final, and so the definitions of $\delta$ and $F$ will need to change, perhaps by introducing a new category $A$. So you can construct a second, slightly different definition of a Turing Machine as the variant.
Then the question is to establish that if the original definition accepts string $<x>$ so does the variant and vice-versa.
