I came across the following question in my revision. I would like to know how to solve this and in general what are the techniques I can use to make an undecidable TM decidable by changing inputs?

Suppose that there is a Turing Machine T when, starting with an empty tape, will generate an infinite sequence of programs C1, C2 .... Let L denote this set of programs.

Note that L can be recognizable by a Turing Machine M, which, given any program C, runs T until it has an output Ci equal to C. If C is in L, M will halt and accept C; otherwise M will not halt.

Show how to modify each program Ci in L to another program Ci' such that Ci and Ci' have the same functions and the set L' of all the modified programs C1', C2', ... is decidable. Justify your answer. [Hint. Make C1', C2', ... strictly increasing in size]

  • 4
    $\begingroup$ I don't understand your question. There's no such thing as an "undecidable Turing machine". Undecidability is a property of problems, meaning loosely that no Turing machine solves that problem. $\endgroup$ Dec 13, 2015 at 8:10
  • $\begingroup$ It's early for me and I've not fully woken up yet, but this problem seems unsolvable. See also here. (cc @DavidRicherby) $\endgroup$
    – Raphael
    Dec 13, 2015 at 10:01
  • $\begingroup$ Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. $\endgroup$
    – D.W.
    Dec 14, 2015 at 1:42

1 Answer 1


First of all, as David mentioned, undecidability is a property of a language, not a Turing machine.

As for your question, the hint kind of gives it up. Note that we only need to recognize the programs $C_i$, not programs who are equivalent (which would be undecidable), so were only dealing with syntax, not semantics.

Let $C_i'$ be the Turing machine which on input $x$ operates the same way as $C_i$, but with enough additional states (which were not going to use, i.e. they will be unreachable from the initial state), such that the length of the encoding $|C_i|$ will satisfy $\forall j<i : |C_j|<|C_i|$. In that case, to decide $L'$, given an encoding of a Turing machine $\langle M \rangle$, run the machine $T'$ which generates $C_i'$. If you meet the program $\langle M \rangle$ accept, if you pass the length of the encoding of $M$ (i.e. you reached $i$ such that $|C_i|>|\langle M \rangle|$) halt and reject. The difference here is that if we reject, we can be sure we will never meet the encoding of $M$, since $C_i$ is a series of programs with strictly increasing encoding length.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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