Re: Why Peter Olcott is correct

On 2025-05-18 03:09:44 +0000, olcott said:

On 5/17/2025 9:06 PM, Mike Terry wrote:

On 18/05/2025 02:51, Mr Flibble wrote:

On Sun, 18 May 2025 02:42:58 +0100, Mike Terry wrote:
 

On 18/05/2025 02:10, Mr Flibble wrote:

On Sun, 18 May 2025 02:06:43 +0100, Mike Terry wrote:
 

On 18/05/2025 01:11, Mr Flibble wrote:

Hi!
 In the case of pathological input, Peter's SHD only needs to report a
correct halting result *as if* the simulation was run to completion:

 Right.  If the simulation is run to completion, that's like a UTM
simulating the input, and equivalent to asking whether the input
halts. This is the case for all inputs, not just "pathological" ones,
whatever they are exactly.
 PO's DD() calls an "embedded HHH" which aborts its simulation.  If
that DD is simulated to completion it halts, so that is what his SHD
needs to report.  PO has verified this directly, and has published the
traces showing DD halting when simulated to completion.
 

whether we abort, or continue until we run out of stack space makes
no difference: we are detecting INFINITE recursion which can be
viewed as non-
halting.

 Eh?  PO does have a couple of SHDs that simulate his DD to completion,
and they all show DD halting!
    There's no infinite recursion, only some level of finite recursive
    simulation.
 PO gets confused, because his SHD HHH simply /doesn't/ simulate DD to
completion.  It aborts, and then decides non-halting.  That's the
reverse of what you said in the first paragraph.  So your thread title
is misleading - PO is actually *incorrect*.  I've corrected the title
to avoid confusion.

 No, halting the simulation is NOT THE SAME as a halting result of
HALTING for what is being simulated.  I have changed the subject title
back, you jackass.

 Where did I say it was the same?  /YOU/ said above that PO's SHD should
decide *as if* the simulation was run to completion.  [your
highlighting].  If DD is simulated to completion it halts,
so by your logic his SHD should decide halting.  Instead it decides
neverhalts.

 No, if an IDEAL simulation runs to completion it NEVER completes as the
recursion is INFINITE however a practical simulator has finite resources
(and a valid decider must decide in finite time) so cannot run forever so
instead we abort the simulation early if we detect infinite recursion with
a correct halting result of NON-HALTING.  This is in accordance with
Flibble's Law.
 /Flibble
 

 As I said above, the recursion in the case of PO's DD is NOT INFINITE.

 void DDD()
{
   HHH(DDD);
   return;
}

That program obviously halts if HHH is a decider. If you put any other
decider in place of HHH (e.g., with a #define line at the top) you get
a program that halts, too. You may get a non-haltng program if HHH is
not a decider or you put a non-decider in place of HHH.
--
Mikko