It has been shown of course that the halting problem is undecidable. That is, we cannot formulate a Turing machine that will decide for any arbitrary turing machine whether it will halt or not.

However, I'm wondering, if we want to decide for the set of Turing machines $T$, whether a turing machine $t$ halts, and we somehow have access to "infinite Turing machines" $I$, which have the property $P$: "They can calculate an infinite amount of steps in finite time", would it then be possible to grab a $i$ from $I$ that decides the halting problem for all $t\in T$?

The proof of the undecidability of the halting problem no longer applies here, because it would require one of the $t\in T$ to contain $i$, but then we might possibly have that $t\in I$ (since $t$ now simulates $i$, which is in $I$).

So my question is, can we prove that in this case, the halting problem is decidable? If not, are there other constructions of $I$ than the one I came up with that would make it possible?

(is there a name for what I've called "infinite turing machines"?)

  • 2
    $\begingroup$ I think you have to (or someone has to) do some work to make clear what the result of an infinite number of steps is: how do we know what state the components of the machine are in? Also, can we travel an infinite distance along the tape? and if so, is it indexed by the ordinal numbers? otherwise, what do we do about programmes that would to do so? If we allow an infinite number of states (which you do not specify), perhaps you can naively make a state for each partial or complete description of a TM and end in the state describing a given machine and emit a valid answer, if that makes sense. $\endgroup$
    – PJTraill
    Dec 9 '17 at 18:13
  • $\begingroup$ This may be related: cs.stackexchange.com/questions/90288/… $\endgroup$
    – SK19
    Apr 6 '18 at 22:26
  • $\begingroup$ and from there: arxiv.org/pdf/math/9808093.pdf $\endgroup$
    – SK19
    Apr 6 '18 at 22:28

It is true that infinite Turing Machines as you have defined them can solve the halting problem for regular Turing Machines. That is, there exists an infinite TM, $I(t,x)$, that returns $1$ iff $t(x)$ halts. To see this, just have your first step be “run t(x) for infinitely many steps” and the rest is easy after that. Yes, there are some issues formalizing this idea, but it can be done. This is called a “Hyper Turing machine”

There’s an interesting question lurking here though... is there an infinite TM that solves the halting problem for infinite Turing Machines? The answer to that is no, and if you know the diagonalization proof of the incomputability of the halting problem that applies here too.

  • $\begingroup$ Could you point me to any resource that discusses infinite Turing Machines as well as the Halting Problem applying to them? $\endgroup$
    – Leo
    Jun 13 at 19:41

There... might just be a way. But it is going away far from what is known to be a Turing Machine.

As PJTraill wrote, we have to get some idea of "infinite steps". I propose our special machine $S$ has (countably) infinite tapes. Given a TM $T$ and input $x$ our infinite steps $S$ would do in finite steps would be that on tape $i$ the content of the tape of $T$ and its state on input $x$ after $i$ simulated steps of $T$ are encoded. We further should allow $S$ to have at least countably infinite many states. After each tape $i$ has been finished being constructed (which, as we remember basically happens in the traditional TM way), $S$ assumes a special tape state $0.a_1\ldots a_i$ with $a_i=1$ if the tape $i$ does not differ from tape $i-1$ and else $0$. When we now allow some mechanism that, after doing all the infinite steps in finite time, changes from our always finitely digited $0.a_1\ldots a_i$ to some infinite sequence $0.a_1\ldots$ - or in more mathematical terms, allow our machine to calculate the limit of the (in general uncomputationable) sequence of special tape stape states $q_i$ when $i\rightarrow\infty$ - then we could be finished, when the state $0.0000\ldots$ returns "TM halts" and all others with infinite digits return "TM does not hold".

I would like to add two things. First, this machine $S$, while halting after a finite number of steps by definition, could not be used to prove that it or machines with the same generalizations would halt. We are using the fact that a TM only has a finite number of states, so it can be encoded on each tape of $S$ using only finite space. Only using finite space on a tape is important so the tape itself can be traversed in finite steps. $S$ is so close to a TM as possible and as long as no infinite steps are done by it, its evaluation to a certain fixed point can be simulated by a normal TM. We were also using that the simulated TM only has (one or) finitely many tapes. We can simulate any such TM by a 1-tape TM, but with countable finite tapes, I don't know but doubt that's possible.

The second thing to mention is that this machine $S$ is by far not the thing Turing and like-wise minds of the time envisioned. They thought about what would be possible for a computator, e.g. a human with instructions, to calculate. It does not seem like this constructed machine $S$ would fall into this category.


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.