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 20:28:58 +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>
 <p5ydnbxV2pHtF_37nZ2dnZfqn_WdnZ2d@brightview.co.uk>
 <v3q4ut$11tp3$1@dont-email.me>
From: Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Date: Wed, 5 Jun 2024 21:28:55 +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: <v3q4ut$11tp3$1@dont-email.me>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <sYqdnVoAec4XV_37nZ2dnZfqn_ednZ2d@brightview.co.uk>
Lines: 184
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-kjD4J1OAfe8qV9Qz6E5mxVmX3buKo8Z+EYHt45Tse5UdC855wrSOnRtrc8QN5GjxMEh4tKeDdl1af+H!YZf2iVjrwu8W4owAkrppzJWxoWKkyfhSwr4IStQlu3oKoFb2TrxdO1oW/KoDoPXTicrQY9kjOYSk!QxZM4MQ2uqyGOgjCbtJfLkzoXJJ1
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: 11761

On 05/06/2024 17:49, olcott wrote:
> 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.

What happens now is that there is one single trace array in global memory, and all simulations 
appends simulated instructions to that one array and can read array entries written by other 
simulation levels.  That fundamentally breaks the concept of a simulation exactly matching the 
behaviour of the outer (unsimulated) computation.  More details below...

[but the problem is I don't believe you really understand what the requirements of simulation are, 
because if you did you simply wouldn't have written code like that in the first place...]

And calling it "a portion of what is essentially its own TM tape" is just obfuscation to try to hide 
the obvious breaking of rules.

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

Partly right but woefully incomplete.  If you added "...or to modify its logical behaviour in any 
way" that would be a good summing up.

Your specific focus on just "their own halt status decision" is only one part of the picture - my 
guess would be you know "the rules" but for whatever reason the only solution you can come up with 
breaks the rules, so you try to convince yourself that that's ok by changing the rules.


More specifically, the behaviour of a simulated HH must exactly[*] match the behaviour of the outer 
(unsimulated) HH.

Behaviour means all of the following:

-  the instruction path of simulated HH exactly matches the instruction path
    of the outer HH.  [Currently HH has different code paths for simulated/
    outer execution!  It is not enough that you /believe/ this will not affect "the result".]

-  registers and all data and data locations used by the simulation must match the registers
    and data and data addresses used by the outer HH. [*]

-  no backdoor channels where a nested simulation feeds data to a nesting simulation or vice versa. 
Obviously an outer simulation can "scrape" data from it's directly simulated computation.


[*] exactly match??  A big headache is that you've chosen a model where all the simulations share 
one 32-bit address space.  So simulation working data will be at different locations to the outer 
working data.  IF your code acts "responsibly" this can be catered for.  E.g. simulated data on 
stacks will be at different addresses for each simulation - but still the location of the data 
within the stack and their values should /exactly/ [*] match across all simulations.  Similarly a 
call to Allocate() will return different results in each simulation, but the location of all data 
used by the simulation relative to that allocation address should match, and the value of the data 
should match [* allowing for pointer mismatches etc.].  Near the end of this post I give some rules 
for code that acts "responsibly" - those rules try to ensure these address relocation problems don't 
affect arguments you make.

> 
> None of the simulated instances ever did this, 

The inner simulations examined a succession of trace entries written by other simulation levels. 
That is wrong.  I think you've convinced yourself they didn't do anything wrong, because you've 
decided to focus only on "affect their own halt status decision", but that's not the requirement.

> 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 think I understand what you're thinking, and
a)  you are just trying to replace one Wrong with another Wrong that you
     hope will be given a tick by someone, rather than looking at what
     a simulation needs to be, and implementing it logically
b)  it won't work

As for (a):  What I think you're proposing is to still have the global trace table, initialised by 
the outer HH, and still have different code paths followed by inner and outer simulations.  That's 
all No Good.

As for (b): I think you intend each inner simulation to be told where it is starting in the global 
trace, so that when it inspects it, it can start from its own starting point.  The problem is that 
all simulations append to the table beyond that point, so a given simulation will /still/ be seeing 
entries directly added by other simulation levels.

In effect you're still trying to keep the shared mutable static data idea that breaks all 3 of the 
"proper simulation" requirements I laid out above.

Why would you want to do that rather than fix the obvious design flaw itself?  I even explained some 
time ago how to do that properly, but you're presenting yourself as some kind of master "Software 
Engineer" and yet you can't work that out for yourself?  I'd guess it should be perhaps a days 
programming effort...

Anyway, the correct approach should obviously be for each simulation to maintain its own trace table 
which is only written to and read by itself.  [Obviously, outer simulations could work out where 
that virtual table was implemented and /scrape/ data out of it if they wanted to.  But those outer 
simulations would have their own trace tables with the data relevant for their processing.  What's 
more, the code paths and behaviours of HH in each simulation level would be identical which is a 
basic simulation requirement.

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

That's wrong thinking.  Each simulation level must be exactly the same as the outer one.  Not just 
in terms of "their halt status decision" but in terms of code paths, data values accessed  [* 
qualified as explained above due to data relocation issues in your environment].

Look - if the outer HH has to initialise a variable, the inner HHs have to initialise that same 
variable, because it is THEIR implementation of that variable, within THEIR virtual address space 
provided by their simulator.  Your problem comes because you insist on trying to SHARE DATA ACROSS 
SIMULATIONS.

Just follow the simple and rather obvious rules like:

-  no mutable static data.  All mutable data should be anchored within the
    simulations stack.
-  when pointers are involved, the pointer values should only be used
    within code to be dereferenced and access the "actual" data stored
    at that location.  [and apply this rule recursively if required!]
========== REMAINDER OF ARTICLE TRUNCATED ==========