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$ – Robert Lewis Sep 4 '13 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$ – Thomas Andrews Sep 4 '13 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 Sep 4 '13 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$ – Chris Culter Sep 4 '13 at 22:00
  • $\begingroup$ @ChrisCulter But how can we know whether the machine will halt without knowing what the actual machine accomplishes? $\endgroup$ – Ryde91s Sep 4 '13 at 22:03

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

| cite | improve this answer | |
  • $\begingroup$ Which is an impossibility. It would be equivalent to saying 0=1 which is false. Man, theory racks my brain. $\endgroup$ – Ryde91s Sep 4 '13 at 22:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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