Path: ...!Xl.tags.giganews.com!local-1.nntp.ord.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Wed, 05 Jun 2024 15:55:28 +0000
Subject: Re: How Partial Simulations correctly determine non-halting ---Mike
 Terry Error
Newsgroups: comp.theory,sci.logic
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>
From: Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Date: Wed, 5 Jun 2024 16:55:19 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.17
MIME-Version: 1.0
In-Reply-To: <87frtr6867.fsf@bsb.me.uk>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <p5ydnbxV2pHtF_37nZ2dnZfqn_WdnZ2d@brightview.co.uk>
Lines: 36
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-7tuj8WqO4Da5RpTxSen6gFUlhNO0VZt9daC8ezqFoM7A7IsHzi8qK/HT/gqGQKC1w4eJX8PJdVpkN/l!CuPQtgNTuX6kjL5bDLZhXJFcnx2Y+PVymkacVq08EzKjt2sXK7IGlSYNCPw4Yjr4WC73o/3tTY0i!zx3+TSn+iVAHFjft73ih4arAOXwB
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
Bytes: 3602

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.