Liste des Groupes | Revenir à theory |
🧠 Simulation vs. Execution in the Halting ProblemTo the best of my knowledge a simulated input
In the classical framework of computation theory (Turing machines),
simulation is not equivalent to execution, though they can approximate one
another.
✅ What’s True:HHH never rejects any input unless it has proven:
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
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.
🔄 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.
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
🧩 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.
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).
Les messages affichés proviennent d'usenet.