Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  Arturo Magidin Jun 11 '11 at 2:50

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.