Re: Annotated Breakdown: "computing the mapping from an input"

On 4/20/2025 3:57 PM, Mr Flibble wrote:

This is a step-by-step outline of Linz's classical proof of the
undecidability of the Halting Problem, with commentary from the
perspective of a category-theoretic critique. This perspective suggests
that certain steps in the proof involve category errors, where roles and
types of entities are improperly mixed — for example, treating a program
and a meta-level decider as interchangeable.
1. Assume a Halting Decider Exists
Linz begins by assuming the existence of a function H(P, x) that can
determine whether program P halts on input x.
 Category-Theoretic View: This assumption does not yet involve any category
error. It describes a standard computational decider working over ordinary
program-input pairs.
2. Define a Contradictory Program D(P)
Construct a new program D such that:
     if H(P, P) reports 'halts', then D(P) loops forever;
     if H(P, P) reports 'loops', then D(P) halts.
 Category-Theoretic View: This step begins to introduce potential category
confusion. The function D is now being constructed specifically to act in
contradiction to H's analysis of P on itself, blending the role of program
and predicate. This blurs the boundary between object-level and meta-level
semantics.
3. Invoke D on Itself
Evaluate D(D), which leads to the contradiction:
     - If H(D, D) says D halts → D(D) loops
     - If H(D, D) says D loops → D(D) halts
 Category-Theoretic View: Here the category error is fully exposed. The
object D is passed into H and simultaneously defined in terms of H’s
result on itself. This self-referential construct crosses semantic layers:
a program is both subject and evaluator. In type-theoretic terms, this is
akin to an ill-formed expression — a form of circular logic not grounded
in a well-defined semantic domain.

Yes we perfectly agree on this, when the input
can possibly do the opposite of whatever value
that its decider returns the question posed to
H is self-contradictory: H(D) Does your input halt?
D cannot actually do the opposite of whatever H returns
when H is a simulating termination analyzer. Instead D
keeps calling H in recursive simulation until H aborts
its simulation of D. Thus mapping THE ACTUAL INPUT STRING
(not any damn thing else) to the behavior that it species
(including D simulating itself simulating D) conclusively
proves that H is correct to reject D as non-halting.
Woefully ignorant people that have no idea what the Hell
"computing the mapping from an input" is, how it works, or
why it is required may disagree.

4. Conclude H Cannot Exist
The contradiction implies that no such universal halting decider H can
exist.
 Category-Theoretic View: From this perspective, the contradiction arises
not from an inherent limitation of deciders per se, but from allowing
semantically invalid constructs. D(D) is seen as undefined or outside the
valid domain of discourse — not a legitimate program-input pair, but a
malformed self-referential statement.

Yes, good job you have quickly gained deep insight.

5. Interpretation
The standard interpretation is that the Halting Problem is undecidable —
there is no algorithm that can determine for all programs and inputs
whether the program halts.
 Category-Theoretic View: The undecidability arises only when the system
permits semantically malformed constructions. If the language of

Yes and all undecidability seems to be from failing to reject
erroneous input.

computation is refined to exclude category errors — such as programs that
attempt to reference or reason about their own evaluation in this way —
then within that well-formed subset, halting may be decidable or at least
non-contradictory.

This same thing equally applies to the Tarski Undefinability Theorem.
https://liarparadox.org/Tarski_275_276.
Truth is a necessary consequence to applying the truth
preserving operation of semantic entailment to the set
of basic facts (cannot be derived from other facts)
expressed in language.
All of undecidability comes from breaking the above rules.
--
Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer