A proof of the insolubility of the halting problem is a diagonalization, which I'm sure most of you have seen. I am not very familiar with set theory, but it strikes me as similar to Cantor's proof of the lack of bijection between the real and natural numbers.

Can this analogy be stretched? If we could design a machine which accepted "more" inputs, could it solve the halting problem (for countable TMs)?

If so, why do we allow TMs with countable inputs to define what is computable?

  • 4
    $\begingroup$ The definition of Turing Machine is meant to mirror the idea of "algorithm" (that it matches perfectly is called 'Church's Thesis'). While we don't have a precise notion of what an "algorithm" is, a set of instructions that requires you to begin by reading an infinite number of inputs (countable or uncountable) is certainly not an "algorithm". You can create "more powerful" Turing Machines by introducing oracles, but you can diagonalize TMs with oracles as well. $\endgroup$ – Arturo Magidin Jun 11 '11 at 2:50

You asked two questions. The first is whether a machine with "more inputs" might be able to solve the halting problem for classical Turing machines. That's somewhat vague, but the correspondingly vague answer is no. To "solve" the halting problem means to compute a certain function from $\mathbb{N}$ to $\mathbb{N}$. Only the behavior of the solver on these inputs is relevant; if the solver could also accept other inputs, it's hard to see how that would affect anything. In order to solve the halting problem in a finite number of steps, a solver needs, in an informal sense, to have an infinite amount of information stored inside it. The inputs, being natural numbers, informally only carry a finite amount of information each. You could change the system to allow an infinite number of steps. Then you could solve the halting problem, but non-natural-number inputs would still not be relevant.

The second question is why we use Turing machines to define computability instead of defining it more broadly. On one hand, we only use Turing machines to define what I would call classical computability: computability on $\mathbb{N}$. The fact that we use Turing machines to define classical computability is just tautologous. It's like asking why we use the word "German" to refer to the language in Germany.

But there are many reasons to study computability on $\mathbb{N}$, just like there are many reasons to study other properties of the natural numbers even though larger number systems exist. One main reason is that classical computability matches exactly what an actual person could do, in principle, given unlimited time, pens, and paper.


Actually all kinds of people have tried to develop models of computation that can do more than a Turing Machine can. Just one little problem: you can't build them.

If you figure out how to build one, and you're really good with patent litigation, NDAs and building businesses generally, you'll be a rich man. If you figure out how to build one, and you're not really good with those things, someone else will be a rich man.

But either way, the trick isn't in the imagining part. The trick is in the doing part.

There is no 'proof' that there isn't a more powerful computational model, but, in agreement with the above, its the Church-Turing Thesis that claims there isn't. The Church-Turing Thesis is called a 'thesis' because its not something that can possibly be proven. But people have been trying to find an exception for a long time, and haven't managed. All of the proposals involve things like 'infinitely fast computation', and 'computing over the reals', 'oracles -- which just happen to know the answers to some key incomputable results', etc. All of which involve non-physical phenomena, aka magic (hence by the way, the term oracle).

It is modestly surprising that the Turing model of computation is so powerful, and there is a natural tendency to 'want to do better'. If you're already rich, have at it. If you have to work for a living... probably best to find an easier problem.


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.