Re: Final Statement on the Halting Problem

On 2025-06-15 19:21:09 +0000, Mr Flibble said:

On Sun, 15 Jun 2025 14:23:36 -0400, Richard Damon wrote:
 

On 6/15/25 9:55 AM, Mr Flibble wrote:

The halting problem as defined ignores recursive self reference
focusing on the paradox instead, I would argue the recursive self
reference leads to infinite regress in the definition of the problem
thus creating a category error making the problem definition itself
ill-formed.
 /Flibble

 But there is no recursive self-reference in the halting problem.
 You only get that recursion when you assume that there exists a program
that can solve it, which is what shows that there is not computation
that can solve the halting problem.
 You have just fallen for Peter Olcotts deceptive strawman definition of
the halting problem, because you don't really understand what you are
talking about.

 Damon's response is defensive, dismissive, and slightly aggressive in
tone. But setting tone aside for a moment, let's analyze the *technical
content* of his reply point by point.
 ---
 ### 🔍 **Claim-by-Claim Analysis**
 #### **1. "But there is no recursive self-reference in the halting
problem."**
 This is partially true, depending on what one means by "the halting
problem."

Unless otherwise specified, one means the halting problem of Turing
machines.

* The *general formulation* of the halting problem does **not** involve
self-reference:
   > “Given a program $P$ and input $x$, determine whether $P(x)$ halts.”

The halting problem is to construct a Turing machine that can answer
every question of the above pattern.

That’s just a predicate over two arguments—no recursion or self-reference
is involved here *yet*.
 * However, **self-reference is absolutely introduced** in the *proof of
undecidability*, specifically in Turing's diagonal argument using $H(P, P)
$ and the construction of a paradoxical program $D$ such that $D(D)$ leads
to contradiction.

There is no self-reference in Turing's construction of $D$. If $H$ is any
Turing machine it is possible to construct the corresponding $D$. Then
one can run $D(D)$ and see whether it halts or enters a loop that can easily
be seen as non-halting. Turing's $D$ does not do anything else. If is
also possible to run $H(D, D)$ and then compare its answer to the
observed behaviour of $D(D)$. There is nothing paradoxcal there, the
answer is simply wrong.
--
Mikko