Is the halting problem decidable by an "infinite Turing machine"?

Question

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"?)

Answer 1

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.

Answer 2

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.