How to make an undecidable Turing Machine decidable? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T14:55:14Z https://cs.stackexchange.com/feeds/question/50677 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/50677 -1 How to make an undecidable Turing Machine decidable? Divine https://cs.stackexchange.com/users/43629 2015-12-13T04:24:32Z 2015-12-13T10:36:29Z <p>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?</p> <blockquote> <p>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. </p> <p>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.</p> <p>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]</p> </blockquote> https://cs.stackexchange.com/questions/50677/-/50683#50683 5 Answer by Ariel for How to make an undecidable Turing Machine decidable? Ariel https://cs.stackexchange.com/users/27055 2015-12-13T10:36:29Z 2015-12-13T10:36:29Z <p>First of all, as David mentioned, undecidability is a property of a language, not a Turing machine. </p> <p>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. </p> <p>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&lt;i : |C_j|&lt;|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|&gt;|\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.</p>