An "uncountable" Turing Machine?

1.1k Views Asked by At

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?

1

There are 1 best solutions below

0
On BEST ANSWER

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.