Re: Position Paper: Why Simulating Halt Deciders (SHDs) Require a Reframing of the Halting Problem

Liste des GroupesRevenir à theory 
Sujet : Re: Position Paper: Why Simulating Halt Deciders (SHDs) Require a Reframing of the Halting Problem
De : richard (at) *nospam* damon-family.org (Richard Damon)
Groupes : comp.theory
Date : 24. May 2025, 23:33:41
Autres entêtes
Organisation : i2pn2 (i2pn.org)
Message-ID : <d81bdcd6499bf5d1de58e344ab12897b77838c32@i2pn2.org>
References : 1 2
User-Agent : Mozilla Thunderbird
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.

Date Sujet#  Auteur
24 May 25 * Re: Position Paper: Why Simulating Halt Deciders (SHDs) Require a Reframing of the Halting Problem8olcott
24 May 25 +* Re: Position Paper: Why Simulating Halt Deciders (SHDs) Require a Reframing of the Halting Problem5olcott
24 May 25 i+* Re: Position Paper: Why Simulating Halt Deciders (SHDs) Require a Reframing of the Halting Problem3olcott
24 May 25 ii+- Re: Position Paper: Why Simulating Halt Deciders (SHDs) Require a Reframing of the Halting Problem1olcott
25 May 25 ii`- Re: Position Paper: Why Simulating Halt Deciders (SHDs) Require a Reframing of the Halting Problem1Mikko
25 May 25 i`- Re: Position Paper: Why Simulating Halt Deciders (SHDs) Require a Reframing of the Halting Problem1Mikko
24 May 25 +- Re: Position Paper: Why Simulating Halt Deciders (SHDs) Require a Reframing of the Halting Problem1Richard Damon
25 May 25 `- Re: Position Paper: Why Simulating Halt Deciders (SHDs) Require a Reframing of the Halting Problem1Mikko

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal