Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Newsgroups: comp.theory
Subject: Re: Why Peter Olcott is correct
Date: Sun, 18 May 2025 03:06:42 +0100
Organization: A noiseless patient Spider
Lines: 65
Message-ID: <100bfbj$povu$1@dont-email.me>
References: <KA9WP.124192$vK4b.46873@fx09.ams4> <100bbr4$le1d$1@dont-email.me>
 <SraWP.289779$o31.223364@fx04.ams4> <100bdv2$loat$1@dont-email.me>
 <x2bWP.289780$o31.145882@fx04.ams4>
MIME-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 18 May 2025 04:06:43 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="c3ad77e4affc0adff3e4fa64d33d561b";
	logging-data="844798"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19RmVll6z/rLUwQZKWUA66x2exSTOs+Jzs="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.18.2
Cancel-Lock: sha1:y8QQxaYDHIem632VMgbEEOJN8/o=
In-Reply-To: <x2bWP.289780$o31.145882@fx04.ams4>
Bytes: 4241

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.  This isn't about "IDEAL" 
simulations having unbounded resources or anything like that.  The simulation of DD completes with 
DD returning really quickly, using very modest resources.  I'd say "try it for yourself", but you'd 
have to build PO's x86utm first.  It's not about resources - DD /really does halt/!

Mike.