How to make an undecidable Turing Machine decidable?

Question

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]

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.