automata-theory
A few years ago it was announced that a 2-state symbol Turing machine was proven to be universal. However, Vaughn Pratt disputed the proof, and I gather he still disputes it. Wolfram's prize committee seems to be satisfied.
Is there anyone not on team Wolfram who believes the proof is correct?
I gave a sequential machine computing the 3n+1/n:2 function in base 2 in several courses
since 1990, but of course I am not claiming any originality here, since it is just an easy
exercise.
Anyway, if you want to see in more details how this sequential machine can be computed in a systematic way, you can look at http://www.liafa.univ-paris-diderot.fr/~jep/PDF/Exposes/Sequential.pdf, slide 59.
Let me try to answer the actual question that was asked. The Wikipedia page defines inductive Turing machines as follows:
An inductive Turing machine is a definite list of well-defined instructions for completing a task which, when given an initial state, will proceed through a well-defined series of successive states, eventually giving the final result. The difference between an inductive Turing machine and an ordinary Turing machine is that an ordinary Turing machine must stop when it has obtained its result, while in some cases an inductive Turing machine can continue to compute after obtaining the result, without stopping.
Two remarks.
I assume that when the description says "eventually giving the final result," what is meant is that there is a stage after which the computation is always displaying that result as output. This makes the concept identical to what has also been known by the term computability-in-the-limit, as well as other terminology. One naturally extends the concept to partial functions, by insisting that for inputs not in the domain, what we want is for the outputs not to converge or stabilize. This is evidently the simple model of inductive machine; the wikipedia page makes references to a hierarchy of more powerful machines.
Although the Wikipedia page makes numerous references to Mark Burgin — his name appears 24 times in the linked article — to my understanding of the history of the subject, the particular concept of computability-in-the-limit has been well understood and analyzed by computability theorists much earlier than Burgin's writings.
To my way of thinking, the main thing to say about this notion of computability is the following, which is commonly given as an exercise in computability theory courses.
Theorem. For any function $f$, the following are equivalent.
$f$ is computable by an inductive Turing machine; that is, $f$ is computable in the limit.
$f$ is computable (in the usual sense) by a Turing machine equipped with an oracle for the halting problem.
The graph of $f$ is $\Sigma_2$-definable.
Proof. ($1\to 3$). If $f$ is computable by an inductive Turing machine, then $f(a)=b$ if and only if there is some stage of the inductive computation on input $a$ such that at any later stage, the output is still $b$. This is a $\Sigma_2$ definition of the graph of $f$.
($3\to 2$) If the graph of $f$ is $\Sigma_2$-definable, then $f(a)=b$ just in case $\exists x\forall y\ B(x,y,a,b)$, where $B$ is $\Delta_0$. With an oracle for the halting problem and any particular $x$, $a$ and $b$, we can ask the oracle if the $\forall y$ condition holds. In this way, on input $a$, we can search for an $x$ and $b$ that fulfill the condition. When found, output $b$.
($2\to 1$) If $f$ is computable with respect to an oracle for the halting problem, then it is computable by an inductive Turing machine: just compute better and better approximations to the halting problem, and for each of them, use that approximation as an oracle for the computation of $f$. This process eventually stabilizes, because for any given input, the approximation to the halting problem will be accurate for a long enough time to support the correct computation of $f$. $\Box$
Note that the argument in the implication ($2\to 1$) exhibits the feature that is central to some of the commentary about these machines, namely, that although we can compute better and better approximations to the halting problem, in a way that will eventually be correct on any given instance, nevertheless we are typically not able to recognize computably when our approximation is correct. Thus, although we may be computing the function $f$ accurately by using that approximation, we have no way of knowing for sure that we have the final answer.
Corollary. For any set $A$, the following are equivalent.
$A$ is decidable by an inductive Turing machine.
$A$ is Turing computable from the halting problem.
$A$ has complexity $\Delta_2$ in the arithmetic hierarchy.
Proof. The characteristic function of $A$ is a total function, and so its graph is $\Sigma_2$ if and only if $A$ has complexity $\Delta_2$. $\Box$
In this sense, yes, the so-called inductive Turing machines can compute the halting problem and therefore Hilbert's 10th problem, since that problem is equivalent to the halting problem.
But to be clear, I don't take this to show that the inductive Turing machine model refutes the Church-Turing thesis.
Unfortunately, it seems that much of the commentary and literature surrounding the claim that it does is of poor quality and in some cases mathematically empty. The discussion seems to have become distracted in the literature and gotten off track in a way; it is a pity.
One of the central achievements of computability theory is the recognition of the subtle distinction between the concept of a set being computably enumerable and it being computably decidable. The recognition that these two aspects of computability are not the same has clarified so many issues in computability. We have known since Turing that the halting problem is computably enumerable but not decidable. Meanwhile, the main arguments for inductive computability violating the Church-Turing thesis seem to my way of understanding things to amount to an attempt to erase this important distinction. After all, the halting problem itself is computable in the limit, since we can say that a program does not halt until we see that it does, and then say from that point on that it does halt. Does this show that the halting problem is computably decidable? No, I don't think so, not in any satisfactory way. And similarly I reject that claim that functions computable-in-the-limit are computable. Since these kinds of simple observations seem to resolve essentially all of the issues on this topic, I cannot recommend following much of the literature surrounding this supposed debate.
Best Answer
See the discussion on FOM mailing list. As far as I remember, according to some members of the prize committee, Wolfram announced it without proper contact with them. There was also discussion about what was Pratt's objection to the proof. See this:
http://cs.nyu.edu/pipermail/fom/2007-October/012132.html
and the other posts in that thread.