The common proof of the undecidability of the halting problem using a hypothesized halting-decider HALTS and constructs a pathological Turing machine $M$ that halts on a string $w$ exactly when HALTS($M,w$) rejects.
This common proof relies on constructing an $M$ that has implicit knowledge of the algorithm HALTS. My question is, are these the only such Turing machines where the halting problem cannot be solved? That is, would it be possible to construct a Turing machine HALTS$^\prime$ that solves the halting problem on all Turing machines, except machines that use HALTS$^\prime$ as a subroutine?
I suppose there are a few possibilities related to this I am unsure of:
- Is there a proof of the undecidability of the halting problem that does not rely on self-reference? I think such a proof would also imply the non-existence of HALTS$^\prime$.
- Is the phrase "Turing machines that use HALTS$^\prime$ as a subroutine" well-defined? I intuitively picture the machine $M$ as somehow containing a full encoding of HALTS, but I'm not fully clear on the specifics. Is it possible, for Turing machines $P$, $R$, to define a relation along the line of "$P$ uses $R$ as a subroutine"?
- Supposing such a relation can be defined, is it possible to compute this relation?