Skip to main content
1 of 4
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

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. 1. Let me 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. Also, for partial functions, let me say that on inputs not in the domain, what we want is for these outputs not to converge in that way. This is evidently the simple model of inductive machine; references are made to a hierarchy of more powerful machines. 2. Although the Wikipedia page makes numerous references to Mark Burgin — his name appears 24 times in the article — to my way of understanding the history of the subject, this concept of computability had been well understood by computability theorists much earlier than Burgin's writings.)

The main thing to say is the following:

Theorem. For any function $f$, the following are equivalent.

  1. $f$ is computable by an inductive Turing machine.

  2. $f$ is computable (in the usual sense) by a Turing machine equipped with an oracle for the halting problem.

  3. 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.

  1. $A$ is decidable by an inductive Turing machine.

  2. $A$ is Turing computable from the halting problem.

  3. $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.

Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k