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: Thu, 06 Jun 2024 21:55:27 +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>
 <sYqdnVoAec4XV_37nZ2dnZfqn_ednZ2d@brightview.co.uk>
 <v3qnip$152b5$1@dont-email.me>
From: Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Date: Thu, 6 Jun 2024 22:55:25 +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: <v3qnip$152b5$1@dont-email.me>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <wEKdnZMVNMfSrf_7nZ2dnZfqn_WdnZ2d@brightview.co.uk>
Lines: 451
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-qGqvi4LGo2EYf4zg0Ilh0SGQqMXLYPH2MrN1bawue/DoHvMLTzZADS4g+cef1uOdY1THeDoNjwHJQ7Q!5n9osW0mOtgAkeVqHNC2NdpVIrAKZtcP6Uuwrqo3ABg0WmJYY7rF/jAqZ+BdJcSlPSFHX6KAPy/e!6NekrJ+mYpQKNMptXtcuMii4z2pT
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: 24609

On 05/06/2024 23:07, olcott wrote:
> On 6/5/2024 3:28 PM, Mike Terry wrote:
>> 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:

tldr;
1) UTMs /aren't/ allowed to share a portion of their input tape with what they're simulating.  (In 
the sense you mean.)
2) At some point below I realised you were probably thinking that because you suppress trace entries 
for everything but D/DD/.. code, that means that inner simulations won't see trace entries from 
outer simulations [i.e. because they've been suppresed from the table].  That would be correct but I 
didn't go back and re-edit earlier comments I'd made.
3) Your proposal will still be breaking basic simulation rules.
4) I started to answer your question on how HH would do it properly, but I would need more info on 
what exactly is needed.  So I'll wait for your reply on that.

Most of all, I'd question whether it's worthwhile for you to expend much of your remaining time on 
this issue.  The whole x86utm thing does not really add to your argument, and certainly does not 
"prove" the things you think it proves.  That won't change if you spend your time fixing it. 
Instead you could just forget the traces etc. and argue your case in words.

>>>>>
>>>>>> 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 
> YES
> 
>> and can read array entries written by other simulation levels. 
> 
> NO they have not been doing this and I will encode it so that this is
> impossible. I knew about this issue about two years before you recently
> raised it. I only found out abut this issue from comp.theory
> respondents.
> 
>> That fundamentally breaks the concept of a simulation exactly matching the behaviour of the outer 
>> (unsimulated) computation.  More details below...
>>
> I have known this for at least two years.
> 
>> [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...]
>>
> I was emulating a UTM passing a portion of its own tape down to its simulated instances of itself. 
> That aspect always seemed legit.

No it's not legit.

There is no UTM tape in your x86utm and you've just picked on this wording because in your mind it 
seems to validate something people point out is wrong in your code.  Actually I've spelled this out 
in much more detail before and I'm not going through it again.  If you didn't understand before I'd 
be wasting my time.

> 
>> 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.
>>
> 
> Not if the simulated instances never access the data from the
> outer-simulations. I will encode this to make it impossible.

The only legit way of doing this (without breaking simulation-compatibility behaviour rules 
somewhere below from an earlier post) is for each simulation to have its own trace table.  Obviously 
all levels of simulated HH must initialise and maintain that table themselves, and code paths etc. 
are exactly the same for outer execution and all inner simulations.

> 
> I will encode u32 start_tape_address to the position in
> execution_trace where the simulated HH begins so that it
> will not ever look further back.
> 
> typedef struct Decoded
> {
>    u32 Address;
>    u32 ESP;          // Current value of ESP
>    u32 TOS;          // Current value of Top of Stack
>    u32 NumBytes;
>    u32 Simplified_Opcode;
>    u32 Decode_Target;
> } Decoded_Line_Of_Code;
> 
> execution_trace is essentially a std::vector of Decoded_Line_Of_Code
> 

That's exactly what I imagined.  But OUTER traces will write their trace data into the vector BEYOND 
your start_tape_address.  In fact, 99% (or more) of entries beyond your start_tape_address will be 
for outer simulation instructions.

>>>
>>> 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.
>>
> 
> Either the simulated instances must some how know not to
> allocate memory for what is essentially a portion of the
> master UTM tape that is passed down to them, or the master
> UTM must some how find the UTM tape of these simulated instances.
> 
By now you must have realised the problem is the "master UTM tape", which is not part of any 
computation model you're using.  Even TMs, which do have a (personal) tape, cannot have a shared 
read/write portion of tape that is global to all simulations.

I see Joes has summed it up succinctly:  The TM /uses/ its tape to /implement/ the virtual machine 
where simulation is occuring.  That's not a read/write backchannel between the simulator and simulated.

>> 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.
>>
> 
> I am having you analyze the details. I was basically gobsmacked
> that A TM cannot do any damn thing that any C program can do.
> It has been at least three years since then.
>>
>> More specifically, the behaviour of a simulated HH must exactly[*] match the behaviour of the 
>> outer (unsimulated) HH.
>>
>> Behaviour means all of the following:
>>
========== REMAINDER OF ARTICLE TRUNCATED ==========