Path: ...!weretis.net!feeder9.news.weretis.net!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: Annotated Breakdown: Linz's Halting Problem Proof and the
 Category Error Perspective
Date: Sun, 20 Apr 2025 19:35:29 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <7fabb7a98ac1b4de5b06119465e8d1552f9f8eff@i2pn2.org>
References: <_cdNP.1582076$Xb1.667097@fx05.ams4>
 <0c9559d9ef7eec83e90fd227c3d579c05b55f089@i2pn2.org>
 <p4eNP.1421125$cgs7.1323242@fx14.ams4>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 20 Apr 2025 23:35:43 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="1196511"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
In-Reply-To: <p4eNP.1421125$cgs7.1323242@fx14.ams4>
Content-Language: en-US
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 11840
Lines: 234

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 
========== REMAINDER OF ARTICLE TRUNCATED ==========