# Will this Turing machine ever halt?

Consider the following Turing Machine, $T_k(n)$, defined in terms of: $$T_k(n) = 1 + T_n(n)$$

At a high level, this expression indiviates that we have a Turing machine (with instructions represented by $k$) that takes as input any arbitrary long number $n$. This Turing Machine will basically emulate another Turing machine $T_n$ that has input that is the same as its instructions encoding AND adds one to its result. If you let $n=k$, will this Turing machine ever halt? Please support your answer.

Now, in my opinion there isn't nearly enough information to know whether or not the Turing machine will or will not halt. Without knowing the function that $T_n$ is performing, adding a $1$ may or may not be arbitrary. For some value $n$, the Turing machine $T_n$ could never halt, meaning that $T_k$ wouldn't either.

Am I incorrect to come to this conclusion? Sure, there is tons of examples that it may halt but is there not equally as many answers supporting the contrary?

• "Meaning that $T_k$ wouldn't either" seems to be an error. We don't ask, "Does $T_k$ halt, we ask, does $T_k(n)$ halt. You can't ask whether a program halts without giving the input to the program. – Thomas Andrews Sep 4 '13 at 21:29
• @RydeStar But we do know the input; the question asks about the particular input $n=k$. This is enough information to solve the problem. – Chris Culter Sep 4 '13 at 22:00
Suppose that it does halt. Then $T_k(k) = 1 + T_k(k)$. I think you should be able to take it from there...