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

On 2025-05-19 16:52:29 +0000, Mr Flibble said:

On Mon, 19 May 2025 11:53:30 +0300, Mikko wrote:
 

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).

 Every single one of your points is either wrong or not a counter-
argument: you've got nothing.

Some of them are obviously counter arguments. Saying that they are
wrong without finding any error does not convince wnyone whose
opinion matters.
--
Mikko