Re: Simulation vs. Execution in the Halting Problem

Liste des GroupesRevenir à theory 
Sujet : Re: Simulation vs. Execution in the Halting Problem
De : richard (at) *nospam* damon-family.org (Richard Damon)
Groupes : comp.theory
Date : 30. May 2025, 00:31:50
Autres entêtes
Organisation : i2pn2 (i2pn.org)
Message-ID : <6ad44f068fbfa3afe6385efaf703ba9307721b27@i2pn2.org>
References : 1
User-Agent : Mozilla Thunderbird
On 5/29/25 1:34 PM, Mr Flibble wrote:
 🧠 Simulation vs. Execution in the Halting Problem
 In the classical framework of computation theory (Turing machines),
simulation is not equivalent to execution, though they can approximate one
another.
 ✅ What’s True:
Running a simulation of a program—even partially—is meant to reflect its
execution behavior.
Simulators, emulators, or analyzers aim to predict how a program would
behave if actually run.
 ⚠️ Where the Divergence Happens:
 1. Simulation May Not Be Complete
Even if the simulator detects what it believes to be infinite recursion,
it:
- Has not observed it to infinity
- Has inferred it based on structure or partial behavior
And the key is that in needs to CORRECTLY predict that the behavior *IS* non-halting. This CAN be done for some inputs, as we can detect patterns for which we can PROVE that the complete simulation of this exact input will never halt.

 2. Execution Is Definitive, Simulation Is Predictive
- Execution is actual: the program runs on hardware (real or virtual) and
either halts or doesn’t.
- Simulation is analytic: a model tries to deduce the result without fully
committing to it.
Right/

 🔄 What SHDs Claim (Flibble/Olcott):
If the SHD halts its simulation due to detecting a provable infinite
recursion, then that should be considered a correct determination of non-
halting for the input program.
The key issue that is forgotten is that the SHD must be a definite program, and not some nebulous contruct that somehow changes its programing in responce to what it sees.
Also, the input must also be a definite program, that in this proof case is built on the exact code of the decider that is being claimed to get the answer right.

 This leads to their argument:
- SHD's halting ≠ the program’s halting
- But SHD's halting due to detection of infinite recursion ⇒ program’s
non-halting
But, the proof program, because it *IS* based on the actual SHD code, sees the answer the SHD *WILL* give, and does the opposite, so the SHD is just wrong.
Thus, if the SHD *WILL* eventually decide to abort and return 0, that decisions MUST HAVE BEEN based on a false pattern that it saw.

 🧩 The Problem:
In classical computability theory:
- You can’t always know that a structure will cause non-halting.
- Many programs appear recursive but halt (e.g., bounded recursion).
- There’s no general algorithm that can always correctly detect infinite
recursion in all programs.
Right, the nature of how Programs work in a "Turing Complete" computation system (which is the most powerful system we know) generate complexity faster than can be analyized, and thus there are question of behavior that can not be computed.

 Thus:
Simulation that halts does not conclusively determine that the simulated
program would or would not halt — unless the simulation is exhaustive and
faithful, which isn't always possible.
 ✅ Conclusion:
Partial simulation provides strong hints but not definitive proof of
halting or non-halting — unless the analysis itself is provably sound and
complete within a restricted system (e.g., total languages).
Right, PARTIAL deciders are possible. In the domain of partial deciders, the normal requirement is that the partial decider can not give a wrong answer, ideally it can give an "I don't know" answer, sometimes we allow it to just not answer. But what is generally unuseful is for it to return a wrong answer, because then we can't trust ANY of its answers, unless we already knew the answer, and what good is a program that can only give relable answers to problems you already know the answer.
This puts Olcotts SHD out of the picture, because he claims it is ok for it to give a wrong answer.
For partial deciders, the key metric is how well can we define the cases that it WILL be able to answer, and what are the (limited) conditions that it might not answer.

Date Sujet#  Auteur
30 May 25 o Re: Simulation vs. Execution in the Halting Problem1Richard Damon

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal