Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: =?utf-8?Q?Re:_Analysis_of_Flibble=E2=80=99s_Latest:_Detecting_vs._Simulating_Infinite_Recursion_ZFC?=
Date: Sun, 25 May 2025 13:18:25 +0300
Organization: -
Lines: 219
Message-ID: <100uqph$1aq9a$1@dont-email.me>
References: <Ms4XP.801347$BFJ.668081@fx13.ams4> <100l1ov$2ul3j$1@dont-email.me> <100l3jh$2v0e9$1@dont-email.me> <100l5c8$2ul3j$2@dont-email.me> <100l75g$2vpq3$1@dont-email.me> <100l887$2ul3i$2@dont-email.me> <100l9gh$30aak$1@dont-email.me> <100lc4o$30pgm$1@dont-email.me> <100ld1u$312c9$1@dont-email.me> <100lg4g$31jt3$1@dont-email.me> <100lkdv$32ib3$1@dont-email.me> <100lmif$32v06$1@dont-email.me> <100lmp3$32ven$1@dont-email.me> <100m319$38k55$2@dont-email.me> <87jz69xlpx.fsf@nosuchdomain.example.com> <100mder$39slu$2@dont-email.me> <100oipb$3oge1$1@dont-email.me> <87a573xz0s.fsf@bsb.me.uk> <875xhrtbpr.fsf@nosuchdomain.example.com> <100r2mb$b2b1$1@dont-email.me> <100r4oq$b650$1@dont-email.me> <100r5bf$b5vm$4@dont-email.me> <100r5hn$b650$2@dont-email.me> <100r648$bhcu$1@dont-email.me> <100r68v$b650$3@dont-email.me> <100sn6a$p071$1@dont-email.me> <100snl3$nvac$1@dont-email.me> <100sr6o$ppn2$3@dont-email.me> <ZomYP.327366$JJT6.124333@fx16.ams4> <100ssn2$q5nm$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 25 May 2025 12:18:25 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="fde75ab023af628ce89d55dd04a64d94";
	logging-data="1403178"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19jNu/lchFJL2xCZ8r5r3QA"
User-Agent: Unison/2.2
Cancel-Lock: sha1:S4esDt8EYCcCapwtFkb43QeY93M=
Bytes: 11304

On 2025-05-24 16:38:58 +0000, olcott said:

> On 5/24/2025 11:24 AM, Mr Flibble wrote:
>> On Sat, 24 May 2025 11:13:12 -0500, olcott wrote:
>> 
>>> On 5/24/2025 10:12 AM, dbush wrote:
>>>> On 5/24/2025 11:04 AM, olcott wrote:
>>>>> On 5/23/2025 8:09 PM, dbush wrote:
>>>>>> On 5/23/2025 9:07 PM, olcott wrote:
>>>>>>> On 5/23/2025 7:57 PM, dbush wrote:
>>>>>>>> On 5/23/2025 8:54 PM, olcott wrote:
>>>>>>>>> On 5/23/2025 7:44 PM, dbush wrote:
>>>>>>>>>> On 5/23/2025 8:08 PM, Mike Terry wrote:
>>>>>>>>>>> I suppose Ben quoted PO saying this, because PO /uses/ it to
>>>>>>>>>>> justify that a particular /halting/ computation will never halt,
>>>>>>>>>>> PO's HHH simulates DDD (which halts) but before DDD halts it
>>>>>>>>>>> spots a pattern in the simulation, and announces non-halting.
>>>>>>>>>>> "Eh?" I hear you say! PO claims HHH has "correctly determined
>>>>>>>>>>> that DDD would never halt" and so is correct to decide non-
>>>>>>>>>>> halting.  His "proof" that it is right to decide non-halting is
>>>>>>>>>>> his "when-so- ever.." quote, which broadly matches the Sipser
>>>>>>>>>>> quote.
>>>>>>>>>>> 
>>>>>>>>>>> So the problem is not so much the "when-so-ever.." words
>>>>>>>>>>> themselves [or the words of Sipser's quote], but understanding
>>>>>>>>>>> how PO is so thoroughly misinterpreting/misapplying them.  How
>>>>>>>>>>> can PO believe HHH has "correctly determined the DDD will never
>>>>>>>>>>> halt" when DDD demonstrably halts?
>>>>>>>>>> 
>>>>>>>>>> PO is working in a different model than the rest of us, though he
>>>>>>>>>> doesn't seem to understand that.
>>>>>>>>>> 
>>>>>>>>>> To him, when function H is deciding on something, the
>>>>>>>>>> implementation of H is allowed to vary.  This results in
>>>>>>>>>> functions that call H to vary as a result.  To him, "DDD" is the
>>>>>>>>>> same computation *regardless of the implementation of HHH*, in
>>>>>>>>>> cases where HHH is simulating DDD.
>>>>>>>>>> 
>>>>>>>>>> This is essentially the mapping he's operating with:
>>>>>>>>>> 
>>>>>>>>>> -----------------
>>>>>>>>>> For a function X with input Y and a function H which simulates X:
>>>>>>>>>> POH(H,X,Y)==1 if and only if there exists an implementation of H
>>>>>>>>>> that can simulate X(Y) to completion POH(H,X,Y)==0 if and only if
>>>>>>>>>> there does not exist an implementation of H that can simulate
>>>>>>>>>> X(Y) to completion ----------------
>>>>>>>>>> 
>>>>>>>>>> And a "decider" in his case maps the following subset:
>>>>>>>>>> 
>>>>>>>>>> ----------------
>>>>>>>>>> Hx is a PO-halt decider if and only if Hx(X,Y) == POH(Hx,X,Y)
>>>>>>>>>> ----------------
>>>>>>>>>> 
>>>>>>>>>> So given his rules, HHH1(DDD) is deciding on a algorithm while
>>>>>>>>>> HHH(DDD) is deciding on a C function whose subfunctions vary.
>>>>>>>>>> 
>>>>>>>>>> This of course has nothing to do with the halting problem but he
>>>>>>>>>> doesn't get this.  After having spent 22 years on this, he'll
>>>>>>>>>> come up with any crazy justification to avoid admitting to
>>>>>>>>>> himself that he misunderstood the problem all this time.  He once
>>>>>>>>>> said (and I don't recall the exact wording) that "the directly
>>>>>>>>>> executed D doesn't halt even though it appears to".
>>>>>>>>> 
>>>>>>>>> The problem is that people here are too stupid to notice that HHH
>>>>>>>>> cannot report on the behavior of its caller.
>>>>>>>>> 
>>>>>>>>> int min()
>>>>>>>>> {
>>>>>>>>>    DD(); // HHH cannot report on the behavior of its caller.
>>>>>>>>> }
>>>>>>>>> 
>>>>>>>>> 
>>>>>>>> What about this?
>>>>>>>> 
>>>>>>>> 
>>>>>>> If you can't stay exactly on topic I am going to ignore everything
>>>>>>> that you say.
>>>>>>> 
>>>>>>> HHH cannot report on the behavior of its caller AKA the direct
>>>>>>> execution of DD().
>>>>>>> 
>>>>>>> 
>>>>>> 
>>>>>> In other words, you again agree with Linz and others that no H exists
>>>>>> that can perform the following mapping:
>>>>>> 
>>>>>> 
>>>>>> Given any algorithm (i.e. a fixed immutable sequence of instructions)
>>>>>> X described as <X> with input Y:
>>>>>> 
>>>>>> A solution to the halting problem is an algorithm H that computes the
>>>>>> following mapping:
>>>>>> 
>>>>>> (<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
>>>>>> (<X>,Y) maps to 0 if and only if X(Y) does not halt when executed
>>>>>> directly
>>>>>> 
>>>>>> 
>>>>> int main()
>>>>> {
>>>>>    DD(); // The HHH called by DD cannot report on the behavior
>>>>> }       // of its caller. Is this OVER-YOUR-HEAD ?
>>>>> 
>>>>> 
>>>> 
>>>> Which means that no HHH exists that meets the below requirements, as
>>>> Linz and others proved and as you have *explicitly* agreed is correct:
>>>> 
>>>> 
>>> You are a damned liar when you say that I said that HHH must report on
>>> the behavior of its caller.
>>> 
>>> No HHH can report on the behavior of its caller for the same reason that
>>> no function can report on the value of the square-root of a dead cat.
>> 
>> Analysis: Olcott’s SHD vs Classical Halting Problem (Thread on 2025-05-24)
>> =========================================================================
>> 
>> Overview:
>> ---------
>> This thread features a debate between Peter Olcott and dbush over the
>> validity and interpretation of Olcott’s SHD (Simulating Halt Decider). The
>> discussion parallels Flibble’s ideas about semantic stratification and
>> simulation-based detection of infinite behavior.
>> 
>> Core Disagreement:
>> ------------------
>> Classical Model:
>> - The Halting Problem asks if a universal decider H can determine whether
>> any program P(x) halts when executed directly.
>> 
>> Olcott’s SHD View:
>> - HHH simulates P(x) and detects infinite behavior.
>> - If infinite recursion is observed during simulation, it reports “non-
>> halting.”
>> - HHH cannot determine the behavior of its caller (e.g., DD()).
>> 
>> Philosophical Analysis:
>> -----------------------
>> 1. Semantic Stratification:
>> - Olcott: A decider cannot report on its caller. This enforces a semantic
>> barrier (like Flibble’s model).
>> - Classical theory treats the program as a fixed object, regardless of how
>> or where it is called.
>> 
>> 2. Simulation-Based Detection:
>> - Olcott’s SHD works by observing simulation patterns.
>> - Like Flibble, Olcott allows early detection of infinite behavior without
>> full execution.
>> - This results in a partial decider — useful but not universal.
>> 
>> 3. Context Misunderstanding:
>> - Olcott sees DD() calling HHH and assumes HHH must reason about DD’s
>> outer frame.
>> - Classical theory ignores runtime context: it analyzes the semantics of
>> the program as a whole.
>> 
>> Meta-Level Behavior:
>> --------------------
>> Olcott:
>> - Asserts that self-reference leads to non-determinism or ill-formed
>> questions.
>> - Treats his SHD as correct for many real-world inputs.
>> - Undermines his position with poor rhetoric and personal insults.
>> 
>> dbush:
>> - Correctly applies classical theory.
>> - Dismisses Olcott's model as a misunderstanding without acknowledging
>> alternative interpretations.
>> 
>> Comparison to Flibble’s Model:
>> ------------------------------
>> | Feature                    | Olcott's SHD             | Flibble's Typed
>> SHD         |
>> |---------------------------|--------------------------|-----------------------------| 
>> 
>> | Simulation-based?         | ✅ Yes                   | ✅
>> Yes                      |
>> | Infinite detection?       | ✅ Runtime-based         | ✅ Structural-
>> based         |
>> | Caller access?            | ❌ No                    | ❌ No (via
========== REMAINDER OF ARTICLE TRUNCATED ==========