Re: Annotated Breakdown: Linz's Halting Problem Proof and the Category Error Perspective

On 4/20/25 5:56 PM, Mr Flibble wrote:

On Sun, 20 Apr 2025 17:44:07 -0400, Richard Damon wrote:
 

On 4/20/25 4: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.

>
And what is the "Category" of your Category-Theoretic critique?
>
THe only category of possible application, is does the input represents
the representation of a program and its input, as that is the domain of
the input in the problem.
>
>

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.

>
No "Role" as far as the problem has occured. The PROGRAM D has been
constructed from an previously defined program H.
>

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.

>
One program using a copy of another program within it is a fundamental
property of Turing Complete programs.
>
If you want to object to that capability, you need to show why it can't
be logically done in the Turing Complete logical programming system
being discussed.
>
Then, "D" isn't passed to D, but the representation of D is passed to D.
Olcotts notation is just bad and obscures the actual activity, and in
fact, totally breaks the required model.
>

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.

>
No, the proof shows that the given H will just fail to give the right
answer for that particual input.
>
The proof also points out that no details about the decider where used,
other than it was claimed to be a correct decider.
>
Thus, the same proof can be applied to ANY such decider, and thus we can
find for ANY decider an input that it will not get the right answer to,
and thus NO decider can answer all inputs correctly.
>
There was nothing "illegal" about the formation of D(D) when done by the
actual Linz method, so there is nothing illegal in the proof.
>
>

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
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.

>
>
No, all you are doing is claiming a category that doesn't actualy exist
based on logic in a framework that fails to meet the requirements of the
problem.
>
Sorry, all you are doing is showing how little you understand what you
are talking about.

 Linz's classical proof of the undecidability of the Halting Problem
involves category errors—semantic violations where roles of computational
constructs are mixed across abstraction layers. The argument identifies
specific steps in the proof where these semantic boundaries are crossed,
leading not merely to contradiction, but to a breakdown of role integrity.
1. Definition of Decider H
Linz begins with a hypothetical decider H(P, x) which takes as input the
encoding of a program P and an input x, and returns whether P halts on x.

No it doesn't.
Olcotts implementation may, but not the original proof.
There is a Halt Decider H defined as a Turing Machine, which takes as an input the description of some machine and its input, and then, to be correct, answers whether said machine/input described to it will halt or not when it is run.
There is a second machine "P" defined based on that Halt Decider H, using valid construction methods that uses a copy of that Decider to decide on its input (duplicated) and then does the opposite of the decision.
This second machine has its description made including it getting copy of that description as its input.
This description is given to the decider H, thus H is, by the definition, being asked if the Turing Machine D, when given its desciption <P> will Halt or not. Since H is defined to be a decider, it will always give an answer.
If H <P><P> says its input will halt, then when we look at that actual operation of the program P appllid to <P> we see that it will also use its copy of H and applying it to <P><P> and see what answer it WILL give.

 This decider exists at the meta-level—it analyzes objects (programs)
rather than participating as an object in computation.

????
The presumption is that the decider exists as a PROGRAM, which is the category it always was.

2. Construction of Contradictory Program D
A program D is constructed such that it uses H to decide the behavior of a
program P on input P, and then behaves in contradiction:
     - If H(P, P) = halts, then D(P) loops
     - If H(P, P) = loops, then D(P) halts
 

And thus D is also a PROGRAM.
Note, the normal proof has P as a program that takes as an input the description of SOME program, <M> and asks H if M applied to <M> will halt by giving it the input <M> <M>, and then do the opposite.
The claimed "self-reference" is merely that applying of the input that just happens to be a description of the program D to the program D, which is a perfectly valid operation. Since H was claimed to be a decider that meets the requirements, it should be able to be given as an input *ANY* valid program and input.

This construction embeds the decider's logic within a program, which
conceptually inverts the role of analyzer and subject. The program D is no
longer merely an object, but a meta-level entity that acts upon itself,
crossing semantic boundaries.

But the "role" of analyser and subject isn't a part of the system. It creates A PROGRAM from another PROGRAM, a step completely allowed and doesn't need to refer to any concept like "analyser" or "subject".
There is no "semantic" boundry crossed that is actually in the domain of operation.

3. Evaluation of D(D)
To complete the proof, D is evaluated on itself: D(D). This involves
passing the encoding of D into H, and then acting based on H's evaluation
of D on D.
 This is the precise point of category error: D attempts to use the decider
H to evaluate its own behavior, and then alters its own behavior based on
that evaluation. A single construct is simultaneously a subject of
analysis and an analyst of itself. This is not a well-formed construction
in semantic type logic.

And what is the error in that?
There is nothing in the definition of the problem that says that "analyser" programs can not be made to be the "subject" input of a decider. It is quite reasonable to say we want to check that a given analyzer will actually halt on a given input. And thus a program being both of the category "analyzer" and "subject" is not a category error, as both are of the domain category "Program"

4. The Contradiction
The contradiction arises:
     - If H(D, D) = halts → D(D) loops
     - If H(D, D) = loops → D(D) halts
 This is interpreted in standard logic as proof that H cannot exist.

WHich it does.

 However, from a semantic modeling perspective, this contradiction is the
result of allowing an invalid construction—akin to a type error in logic—
where role boundaries between levels of computation were not respected.

And what was "Invalid" about the construction.
The construction took ONE PROGRAM, and embedded it within another, and this composition operation is a fundamental operation allowed in programming theory.

5. Conclusion
Therefore, Linz's proof permits category errors by implicitly treating a
program as both subject and analyzer. Such constructions violate the
stratified semantics that prevent contradictions in typed or hierarchical
logics. From this view, the proof demonstrates not the nonexistence of H
in general, but the unsoundness of permitting self-referential analysis
across abstraction boundaries.

But it doesn't of any category actually present in the actual problem.
Your attempt to make a distinction between "analyser" and "subject' is just an admittion that you theory can't handle the giving of a arbitrary program to a decider on program behavior.
This means you concept of a program is less than Turing Complete.
Sorry, your "proof" is debunked.