Solving the halting problem for *almost* all machines?

Question

As I understand it, the proof of the halting problem’s undecidability is conceptually pretty simple. You postulate a machine $h(m, x)$ which (1) always halts and (2) returns 1 if $m$ halts with input $x$, 0 if not. Using this, you build a machine $g(m)$ that spins forever if $h(m, m) = 1$, and halts if $h(m, m) = 0$. Then, $g(g)$ creates a contradiction: if it halts, then $h(g, g) = 1$ and $g(g)$ must spin forever; and similarly, if spins forever, it must halt.

So my question is: does this say anything about the halting problem for machines other than those that solve the halting problem or use machines that solve it? That is, couldn’t you still build a machine $h’(m, x)$ that solves the halting problem for any machine except $h$, $h'$, and any machine that includes $h$ or $h'$? With that restriction, you can’t evaluate $g(g)$, and the contradiction goes away. It seems like such a machine would still be extremely powerful.

Or does the math behind my loose understanding of the proof-of-undecidability preclude this? One way I could imagine this happening is if the precise definition of "except any machine…" can be proved to be not-halting, in which case the answer to my question is basically that the existence (or definition?) of $h'$ is not decidable.

I am not super well-versed in this branch of mathematics, so an "explain it like I'm 5"-type answer would be much appreciated!

---

(Apologies if this is a dup; I searched for other halting problem questions and couldn't find and answer, though I'm not sure what to add to focus the search. This seems similar to, but different from, this question.)

Answer 1

The theorem says that there is no algorithm that solves the halting problem for all Turing machines. There are certainly algorithms that solve the halting problem for some subclasses of machines. However your criterion is not well stated. There are other problems for which it is known that algorithms do not exist, e.g. the word problem for groups, or existence of solutions of diophantine equations. Halting for Turing machines that search for solutions of these is also undecidable.

Answer 2

That was the question in my head for some time and here is my answer.

Let's consider a clever version of the miraculous machine h, call it h'. h' first examines its input (m,x) and enters an infinite loop if it somehow detects that m contains h, and then proceeds to solve the halting problem for other inputs. But then problem still remains when m contains a machine equivalent to h', and there are infinitely many such machines.

So let's move further and consider an even more clever machine h'' which first examines its input (m,x) and enters infinite loop if it detects that m contains a machine equivalent to h'', then solves halting problem for other inputs. But then, by Rice's theorem, using h'', we can build a machine which solves the original halting problem, which is impossible.

Rice's theorem makes it clear that this uncomputability phenomenon is not just limited to some small set of problematic inputs.