1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Seems simple enough. What did you try? $\endgroup$ – Karolis Juodelė Nov 18 '16 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$ – skankhunt42 Nov 18 '16 at 8:21
  • $\begingroup$ I'm struggling to construct the turing machine which simulates the given criteria. $\endgroup$ – sumo Nov 18 '16 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$ – Raphael Dec 18 '16 at 21:34
1
$\begingroup$

In order to prove that your modified Turing machine is equivalent to a standard Turing machine, you need to do two things:

  1. Given a standard Turing machine $T_1$, give a modified Turing machine $T_2$ such that $L(T_1) = L(T_2)$.

  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!

$\endgroup$
  • $\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$ – sumo Nov 18 '16 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$ – skankhunt42 Nov 18 '16 at 17:03
1
$\begingroup$

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.

$\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.