Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!news.quux.org!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: Position Paper: Why Simulating Halt Deciders (SHDs) Require a
 Reframing of the Halting Problem
Date: Sat, 24 May 2025 18:33:41 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <d81bdcd6499bf5d1de58e344ab12897b77838c32@i2pn2.org>
References: <binYP.412288$6Qab.7156@fx07.ams4> <100t06c$r01g$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 24 May 2025 22:34:33 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="1787438"; 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: <100t06c$r01g$2@dont-email.me>

On 5/24/25 1:38 PM, olcott wrote:
> On 5/24/2025 12:25 PM, Mr Flibble wrote:
>> Position Paper: Why Simulating Halt Deciders (SHDs) Require a 
>> Reframing of
>> the Halting Problem
>> ==============================================================================================
>>
>> Thesis:
>> -------
>> Simulating Halt Deciders (SHDs), such as those proposed by Flibble and
>> Olcott, do not disprove the classical Halting Problem but instead operate
>> in a distinct computational framework. Therefore, they require a 
>> reframing
>> of the Halting Problem to accurately describe what is being solved.
>>
>> 1. The Classical Halting Problem
>> --------------------------------
>> Definition:
>> Given a program P and input x, determine whether P(x) halts when 
>> executed.
>>
>> Requirements:
>> - The decider H must work for *all* valid programs P and inputs x.
>> - H must be total: it must give a correct answer for every input pair.
>> - The construction of D() = if H(D) then loop leads to contradiction.
>>
>> Implication:
>> - No universal halting decider exists.
>>
>> 2. What SHDs Do Differently
>> ---------------------------
>> SHDs simulate the behavior of P(x), often with the following properties:
>> - They detect infinite recursion or looping patterns *during simulation*.
>> - They may abort early when a loop is structurally recognized.
>> - They return a result based on runtime behavior, not semantic 
>> derivation.
>>
>> In some models:
>> - SHDs may crash or refuse to decide on inputs that involve self- 
>> reference.
>> - They avoid the contradiction by forbidding or failing on such cases.
>>
>> 3. Why This Requires Reframing
>> ------------------------------
>> The classical Halting Problem assumes:
>> - All programs are valid analyzable inputs.
>> - The decider exists *outside* the execution environment.
>> - Deciders can analyze any encoded program as data.
>>
>> SHDs violate or restrict these assumptions:
>> - Some inputs are semantically ill-formed (e.g. self-referential
>> constructions).
>> - Deciders may exist *within* the runtime framework (e.g. as part of a
>> simulation).
>> - Programs are not just strings—they may include or exclude semantic
>> permissions.
>>
>> Reframed Problem:
>> "Given a well-formed, non-self-referential program P and input x, can an
>> SHD determine whether P(x) halts by simulation, within finite time?"
>>
>> This version:
>> - Recognizes semantic boundaries.
>> - Accepts partiality (SHDs may refuse to decide some inputs).
>> - Avoids contradiction by rejecting paradox-generating constructions.
>>
>> 4. Analogy to Type Theory
>> --------------------------
>> In modern logic systems:
>> - Self-reference is blocked by stratified types or universe hierarchies.
>> - Proof assistants like Coq, Agda enforce termination through typing.
>>
>> Similarly, SHDs operate with:
>> - Semantic filters (not all programs are valid inputs).
>> - Safety over completeness.
>>
>> This makes them useful, but outside classical universality.
>>
>> 5. Practical Implication
>> ------------------------
>> Reframing the Halting Problem to fit SHDs allows:
>> - Simulation-based analyzers to be judged on their actual utility.
>> - SHDs to be integrated into verification pipelines (e.g. compilers,
>> interpreters).
>> - Clear boundaries between theoretical impossibility and practical
>> feasibility.
>>
>> Conclusion:
>> -----------
>> SHDs do not contradict the Halting Problem—they bypass it by refusing to
>> evaluate semantically ill-formed or reflexive inputs. This makes them
>> partial deciders operating in a semantically filtered domain.
>>
>> To evaluate them fairly, the Halting Problem must be reframed: not as a
>> universal challenge, but as a scoped analysis tool within a stratified or
>> simulation-based semantic model.
> 
> My SHD refutes the classical halting problem proof
> that same way that ZFC refutes Russell's Paradox.

No, it doesn't as ZFC doesn't "refute" Russell's Paradox, just creates 
an alternate system where it can't be formed.


If you want to form an alternate computation theory, you need to stop 
claiming you are doing anything in that theory (and thus have any 
implication on the theory) and do the work to fully define your new 
alternate theory,

Of course, since that doesn't negate the actual Halting Theory that is 
in the field that other proofs use, you haven't acheived your goal of 
putting those other theories into question.

> 
> Instead of requiring a termination analyzer to report
> on the behavior of its caller it reports on the actual
> behavior actually specified by its actual input.

But since the "actual behavior" of the input is DEFINED to be what turns 
out to be the behavior of its caller, that is impossible.

> 
> *This was probably the actual intent all along*
> It merely took 90 years before anyone really
> studied how pathological inputs actually do
> change their own behavior by their pathology.
> 

No, it just shows that you haven't learned anything about the works 
presented, and are making the same mistakes that the people tried to 
raise those 90 years ago, and eventually dropped their objections when 
they saw the truth (or died uninformed).

Sorry, you are just showing that you are almost a century behind in your 
knowledge.