Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory,sci.logic
Subject: Re: How Partial Simulations correctly determine non-halting ---Mike
 Terry Error
Date: Wed, 5 Jun 2024 11:49:31 -0500
Organization: A noiseless patient Spider
Lines: 79
Message-ID: <v3q4ut$11tp3$1@dont-email.me>
References: <v3j20v$3gm10$2@dont-email.me>
 <J_CdnTaA96jxpcD7nZ2dnZfqnPudnZ2d@brightview.co.uk>
 <87h6eamkgf.fsf@bsb.me.uk> <v3kcdj$3stk9$1@dont-email.me>
 <v3l7uo$13cp$8@dont-email.me> <v3lcat$228t$3@dont-email.me>
 <v3mq9j$chc3$1@dont-email.me> <v3mrli$chc4$1@dont-email.me>
 <_gWdnbwuZPJP2sL7nZ2dnZfqn_GdnZ2d@brightview.co.uk>
 <v3nkqr$h7f9$3@dont-email.me> <v3oeh5$jthg$2@dont-email.me>
 <v3of8e$lirl$1@dont-email.me> <v3ofld$jthh$1@dont-email.me>
 <v3oh8l$pi6u$3@dont-email.me> <v3ohkh$jthg$4@dont-email.me>
 <87frtr6867.fsf@bsb.me.uk>
 <p5ydnbxV2pHtF_37nZ2dnZfqn_WdnZ2d@brightview.co.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 05 Jun 2024 18:49:33 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="dbcb5a2e000d59c1dda264f94a647a93";
	logging-data="1111843"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19jXRrf+ViHhRherdVE2N8x"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:8v+4JT8CAGoRZZ7/6VS8VQN8ruM=
Content-Language: en-US
In-Reply-To: <p5ydnbxV2pHtF_37nZ2dnZfqn_WdnZ2d@brightview.co.uk>
Bytes: 5178

On 6/5/2024 10:55 AM, Mike Terry wrote:
> On 05/06/2024 10:38, Ben Bacarisse wrote:
>> John Smith <news2@immibis.com> writes:
>>
>>> Then increase the stack space until it doesn't run out. Turing machines
>>> can't run out of stack space unless you programmed them wrong.
>>
>> A Turing machine can't run out of stack space because there is no stack.
>> That's like saying a polynomial has limited precision if you evaluate it
>> badly.  It's the evaluation that's wrong, not the polynomial.  I know
>> what you mean, but having talked to maths crank on Usenet for years, one
>> thing I would caution against is being slowly sucked into the cranks bad
>> use of technical terms.
>>
> 
> Wandering slightly : also, PO's H/HH/etc. (running under x86utm) 
> requires minimal stack space to run - probably just a few KB would 
> suffice, /regardless of recursion depth/.  Given that PO allocates 64KB 
> for the stack, this is not going to be a problem.
> 
> The reason recusion depth is not a factor is that H /simulates/ D rather 
> than calling it.  The simulation does not consume H's stack space, and 
> neither do nested simulations - they all have their own separately 
> allocated stacks.
> 
> PO's design uses a single 32-bit address space which must hold ALL 
> levels of nested recursion, so obviously something has to fail as 
> nesting levels grow.  That would be an "out of memory" failure when 
> trying to acquire resource to create a new simulation level.  I.e. a 
> /heap/ error rather than "out of stack".
> 
> In practice his system would become unusable long before then due to CPU 
> requirements in simulating instructions for each recursion level - that 
> grows exponentially with a factor of (something like) 200 between each 
> level.  So at a recursive simulation depth of just 10, a single 
> instruction would take something like 100,000,000,000,000,000,000,000 
> outer level instructions to simulate, which is just impractical.
> 
> 
> Mike.
> 

Thank you very much for being the voice of correct reasoning here.
I just figured out how to handle your objection to my HH code.

My idea was to have the executed HH pass a portion of what is
essentially its own Turing Machine tape down to the simulated
instances of HH. It does do this now.

The key objection that you seemed to have is that it can't pass
any information to its simulated instance that they can use in
their own halt status decision.

None of the simulated instances ever did this, yet I can make
this more clear. As soon as they are initialized they can store
their own first location of this tape and never look at any
location before their own first location. In this case they
would never get a chance to look any data from the outer
simulations that they can use to change their own behavior.

I will implement this in code sometime later today and publish
this code to my repository.

The only issue left that seems to not matter is that each simulated
HH needs to see if it must initialize its own tape. Since this
has no effect on its halt status decision I don't think it makes
any difference.

I will double check everything to make sure there is no data passed
from the outer simulations to the inner simulations that can possibly
be used for any halt status decision by these inner simulated
instances of HH.

I really appreciate your help on this.

-- 
Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer