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,sci.logic,comp.ai.philosophy
Subject: Re: Annotated Breakdown: "computing the mapping from an input"
Date: Sun, 20 Apr 2025 19:20:23 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <cc550ea854a2304b02fd12a0dfdd13d072a9ffb6@i2pn2.org>
References: <_cdNP.1582076$Xb1.667097@fx05.ams4> <vu3rqa$nqp4$1@dont-email.me>
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:38 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="1196511"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
X-Spam-Checker-Version: SpamAssassin 4.0.0
Content-Language: en-US
In-Reply-To: <vu3rqa$nqp4$1@dont-email.me>
Bytes: 6355
Lines: 123

On 4/20/25 6:17 PM, olcott wrote:
> 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.

But there is no category error of categories actuallyu in the problem.

D is built by VALID methods from the program H.

Thus is D is invalid, so was H, and thus the claims break.

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

But the input isn't erroneous, unless the decider was first.

This of course is part of your problem, your decider fails to meet the 
requireemts of actually being a decider that can be given the 
representation of any program, and you constructon of D fails to meet 
the requirements, and actually just fails to build the requried program 
because you omit key steps, like making a copy of the decider to put 
into the program D.

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

Nope, as explained elsewhere.

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

Yes, but a predicate that indicated this can't be made, because some 
Truth is just unknowable.

Your problem is you just don't understand what you are talking about and 
get lost when the system gets too big for you to see.