Return to Answer

The Wikipedia page defines inductive Turing machines as follows:

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. This makes the concept identical to what has also been known by the term limit computation or computability-in-the-limit and many other terms. 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.

2. Although the Wikipedia page makes numerous references to Mark Burgin — his name appears 24 times in the article — to my understanding of the history of the subject, this concept of computability had been well understood and analyzed by computability theorists much earlier than Burgin's writings.

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 surrounding the claim that it does is of poor quality and in cases mathematically empty.

Let me try to answer the actual question that was asked. The Wikipedia page defines inductive Turing machines as follows:

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

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

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.

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 makes the concept identical to what has also been known by the term limit computation or computability-in-the-limit and many other terms. This is evidently the simple model of inductive machine; the wikipedia page makes references 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 understanding of the history of the subject, this concept of computability had been well understood and analyzed by computability theorists much earlier than Burgin's writings.

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.

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. This makes the concept identical to what has also been known by the term limit computation or computability-in-the-limit and many other terms. 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.

2. Although the Wikipedia page makes numerous references to Mark Burgin — his name appears 24 times in the article — to my understanding of the history of the subject, this concept of computability had been well understood and analyzed by computability theorists much earlier than Burgin's writings.

1. $f$ is computable by an inductive Turing machine; that is, $f$ is computable in the limit.

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.

(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:

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.

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 makes the concept identical to what has also been known by the term limit computation or computability-in-the-limit and many other terms. This is evidently the simple model of inductive machine; the wikipedia page makes references 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 understanding of the history of the subject, this concept of computability had 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.

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 surrounding the claim that it does is of poor quality and in cases mathematically empty.