Can you solve the halting problem for a single, non-universal Turing machine?

Question

So, I'm familiar with the halting problem and its proof. However, I also understand that the proof is for any universal machine $U$; that is, the set $\{(x,y)\in\{0,1\}^{<\omega}\times\{0,1\}^{<\omega}: U(x,y)\downarrow\}$ is not computable. Specifically, I've seen the proof by contradiction that the set's complement is not semicomputable.

However, given a specific, non-universal machine $M$ with alphabet, say, $\{0,1\}$, could you define a machine $M^\prime$ such that, say, $M^\prime(w)=M(w)$ if and only if $M(w)$ halts, and $M^\prime(w)=0$ if $M$ does not halt on input $w$? Or would this, in some way, solve the halting problem, so such a machine $M^\prime$ cannot exist?

Sorry, in advance, if this seems like too basic a question or if it's been asked before. I can't really think of a way to phrase the question simply to look up whether or not it's been answered before. Thank you!

Answer 1

The standard proof that the halting problem is unsolvable gives a machine $M$ such that there is no total machine $M'$ can determine correctly the set of $n$ for which $M(n)$ halts.

This machine $M$ is not universal in the sense of computability theory. Rather $M(e)$ attempts to compute $\phi_e(e)$; if $U(e,e)$ halts and returns a number greater than $0$ then $M(e)$ does not halt, while if $U(e,e)$ halts and returns $0$ then $M(e)$ halts and returns $1$. If $U(e,e)$ does not halt then neither does $M(e)$. You can check that this gives a sound definition of a machine $M$, and that no machine $M'$ can solve the halting problem for $M$ in the sense given in the question.

Answer 2

First, a remark. As I understand the concept, "universal Turing machine" describes a machine's functionality rather rigidly: the machine has to take inputs in a certain format, and then behave in a very specific way. It's not a robust concept for the sort of question you're asking; you could just take a universal machine and modify it in some trivial way so that it is essentially the same, but isn't technically a "universal machine."

That said, I'll say a bit about what I think is really behind your question. You're asking about when it is possible to make an algorithm to solve the halting problem for particular machines. You can ask this more generally: given a particular set of natural numbers, is there an algorithm to decide which numbers are in the set, and which numbers are not in? In your case, the set is the set of inputs for which the machine halts. Only some sets arise like that; they are called, by definition, the "computably enumerable" sets. On the other hand, sets for which it is possible to make an algorithm to decide which elements are in and which are out are, by definition, "computable sets." The halting problem argument shows that there is a computably enumerable set that is not computable.

What I believe you observed is that a universal Turing machine is fairly powerful in that it can do everything any other Turing machine can. It is a natural question to ask if there are "less powerful" sets that are still not computable. That may seem a bit nebulous, but we're in luck: there is a good way to compare the power of two sets, called Turing degree. The basic idea is that a set A is "stronger" than another set B (has a higher degree) if you can build a machine to compute B (i.e. decide which elements are in and which are out), if that machine can consult A as an "oracle." This turns out to be a rich and robust concept.

Anyway, the answer to my version of your question is yes. There is a rich variety of sets that are computably enumerable (i.e. are the halting set of some machine), not computable, and are strictly weaker than the halting set of any universal machine (in terms of Turing degree). I don't know of any simple constructions, but I hope I've given you some ideas to try and learn about.