Given a turing machine $T$ that receives an encoding of another turing machine and a word $<M><w>$, can $T$ 'run' through the encoding and 'mark' specific transitions/states?

For example, if I want to show that the language $L = \{<M><w>\}$ such that when we run $w$ in $M$ we will visit at least two unique states different than the starting state.

Now for this, I suggested this algorithm, but I am not sure it is even compuatable:

Given the encoding $<M><w>$, we will run through the encoding and 'mark' all states that can be reached from the starting state of $M$, if two or more states have been marked after finishing, accept, else, reject.

I know that since this an encoding of a turing machine and a word, we indeed -can- run through the encoding. But can we really do the 'marking' operation? if so, how?


A quick answer: if the tape alphabet is large enough ($\geq 18$ symbols), then $L = \{\langle M,w\rangle \mid $ M on w visits at least two unique states different than the starting state $\}$ is undecidable; indeed for every $M$ with $n$ states there is an equivalent $M'$ with only 2 states such that for all $x$ $M(x)$ halts if and only if $M'(x)$ halts. To prove that L is undecidable, you can use the following reduction from the halting problem: given $\langle M\rangle$ build the equivalent two states machine $M'$ (the starting state plus another one), and add an additional final and accepting third state that can be reached only if $M'$ halts when run on the empty tape. Clearly $\langle M',w\rangle \in L$ (i.e. visit the second and the third accepting state) if and only if $M$ halts ($w$ is irrelevant), so if $L$ is decidable you can solve the halting problem which is a contradiction.

Reducing the number of symbols, doesn't help too much, indeed you can encounter Turing machines that behaves like the Collatz function (e.g enter the third state only when the sequence reaches 1) ... and it is an open problem if for all $n$ the Collatz function reaches 1.

For a proof that you can build an Universal Turing machine (using 2-tag simulation) with only 2-states and 18 symbols see:

Y. Rogozhin. Small universal Turing machines. Theoretical Computer Science, 168(2):215–240, Nov. 1996.

Finally, as an exercise, you should be able to easily prove that the following language is undecidable:

$L' = \{ \langle M,w,k \rangle \mid$ when run on w the Turing machine M visits at least $k$ different states $\}$

  • $\begingroup$ Thank you for the thorough explanation, that answered a part of my question. What about the first part? 'Marking'? $\endgroup$ – TheNotMe Jan 7 '14 at 20:13
  • $\begingroup$ What I mean is, is it really do-able in a turing machine, given its' encoding? $\endgroup$ – TheNotMe Jan 7 '14 at 20:20
  • $\begingroup$ Yes, you can decode it (i.e. get the explicit description of M) and then simulate it (using a "customized" Universal Turing machine ) and mark every state visited by M during its computation (but if it doesn't halt also your simulation will never halt). $\endgroup$ – Vor Jan 7 '14 at 20:23
  • $\begingroup$ So, if that's doable, then the langauge is recognizable, just not decidable. Am I correct? $\endgroup$ – TheNotMe Jan 7 '14 at 20:25
  • $\begingroup$ @TheNotMe: yes it is recognizable; just run the simulation, and accept when M visits at least 2 different states (other than the starting state). $\endgroup$ – Vor Jan 7 '14 at 20:26

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.