Re: Analysis of Flibble’s New Take on Simulating Halt Deciders and Pathological Input

On 2025-05-18 00:27:29 +0000, Mr Flibble said:

Analysis of Flibble’s New Take on Simulating Halt Deciders and
Pathological Input
==================================================================================   1. Summary of Flibble’s New Take
--------------------------------
Flibble introduces a refined stance on the treatment of pathological input
within simulating halt deciders (SHDs), asserting:
 - It's sufficient for an SHD to detect *infinite recursion*, rather than
run a simulation to its literal end.

Detection of an infinite recursion is neither sufficent or necessary. A
halt decider is required to determine whether a computation halts. It
need not determine what kind of non-terminating behaviour the computation
has. As a SHD is a halt detector that applies to every SHD.

- Aborting due to stack overflow or continuing infinitely are semantically
equivalent — both signify non-halting behavior.

Aborting doe to a stack overflow indicates an insufficient stack size. It
does not prove that the computation cannot be simulated to comletion with
a bigger stack.

- This leads to the articulation of "Flibble's Law":

i.e., these errors

    If a problem permits infinite behavior in its formulation, it permits
    infinite analysis of that behavior in its decidability scope.
 2. Interpretation of Flibble’s Law
----------------------------------
This law suggests that:
- Any problem involving potentially infinite computation inherently
requires the ability to analyze such infinite behavior.

But only tho the extent that a solution to the problem can be found.
For example, the sequence of the Fibonacci numbers is infinite but
with a finite effort it is possible to determine that none of those
numbers is negative (or that a backwards extension of the sequence
does contain negative numbers9:

- Deciders are not invalidated by their inability to simulate forever —
they are validated by their ability to detect structural infinity.

A decider is invaidated by one input that the decides incorrectly.

3. Shift in Position
--------------------
Earlier, Flibble emphasized that:
- Pathological inputs are ill-formed due to a category error (program
conflated with its own representation).
- Therefore, halting cannot even be meaningfully questioned for such
inputs.
 Now, Flibble acknowledges:
- SHDs can still offer meaningful answers by detecting recursion patterns
without needing infinite runtime.
- A decider may *abort* simulation upon detecting such patterns and still
be semantically correct.

The only correctness applicable to a decider is the correctness of its
output: a decider is correct if it gives the correct output for every
input and incorrect if it gives the wrong answer to at least one input.
A partial decider is correct if it gives the wrong answer for no input.

4. Contrast with Turing’s View
------------------------------
| Aspect                      | Turing                            |
Flibble                             |
|-----------------------------|------------------------------------|--------------------------------------|  | Infinite recursion          | Undecidable behavior               |
Signal of ill-formed input           |
| Decider responsibilities    | Must decide all valid inputs       | Must
exclude ill-formed inputs       |
| Simulation abort (overflow) | Not semantically significant       | Valid
detection of non-halting input |

There is no undecidable behoviour in Turing's Turing machines. All
definitions, including Turing's, require that the behaviour is
fully specified.
According to Flibble's cireteria using a stack too small to even start a
simulation is sufficient to for a valid detection of non-halting.
Consequently every computation is non-thalting.

Turing treats infinite simulation as a symptom of undecidability.

No, he does not. His main focus was in computations that produce an
infinite sequence of output symbols (typically digits of an irrational
number).
--
Mikko