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?

Thanks for your input.

  • 4
    $\begingroup$ not to put too fine a point on it, but I believe the term is Turing machine, not Turning machine! $\endgroup$ Commented Sep 4, 2013 at 21:16
  • 1
    $\begingroup$ "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. $\endgroup$ Commented Sep 4, 2013 at 21:29
  • $\begingroup$ Yes, I meant Tk(n). Are my assumptions agreed upon that it's uncertain whether the machine will or will-not stop without knowing both the inputs and the workings of the Turing machines function? $\endgroup$
    – Ryde91s
    Commented Sep 4, 2013 at 21:54
  • $\begingroup$ @RydeStar But we do know the input; the question asks about the particular input $n=k$. This is enough information to solve the problem. $\endgroup$ Commented Sep 4, 2013 at 22:00
  • $\begingroup$ @ChrisCulter But how can we know whether the machine will halt without knowing what the actual machine accomplishes? $\endgroup$
    – Ryde91s
    Commented Sep 4, 2013 at 22:03

1 Answer 1


Suppose that it does halt. Then $T_k(k) = 1 + T_k(k)$. I think you should be able to take it from there...

  • $\begingroup$ Which is an impossibility. It would be equivalent to saying 0=1 which is false. Man, theory racks my brain. $\endgroup$
    – Ryde91s
    Commented Sep 4, 2013 at 22:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .