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: Tue, 04 Jun 2024 02:57:37 +0000
Subject: Re: Why does Olcott care about simulation, anyway? --- Mikes Review
Newsgroups: comp.theory,sci.logic
References: <v3j20v$3gm10$2@dont-email.me>
 <J_CdnTaA96jxpcD7nZ2dnZfqnPudnZ2d@brightview.co.uk>
 <v3jei1$3o3a7$1@dont-email.me>
 <0xqdnd8ktrnsc8D7nZ2dnZfqnPqdnZ2d@brightview.co.uk>
 <v3l002$5d3$1@dont-email.me>
 <lZadnYLpbtuB7cP7nZ2dnZfqn_udnZ2d@brightview.co.uk>
 <v3lrm2$4h2j$1@dont-email.me> <v3lsd6$2uv04$17@i2pn2.org>
 <v3ltij$8gjv$3@dont-email.me>
From: Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Date: Tue, 4 Jun 2024 03:57:36 +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: <v3ltij$8gjv$3@dont-email.me>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <7MadnQlevYc8H8P7nZ2dnZfqnPSdnZ2d@brightview.co.uk>
Lines: 158
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-LGP72u1rqyewFMerogNPCzaRLjGu6JmOgbP0cdyLvnO8C+l4NT9ZvIsioNRJkDev+HvLcpGaV8s8xH3!WVr1KAT+AgOPG8bo0or6ypLfJRrV+gzRIj/fD1jkqa/8i5puTAN5Y/VYUhZiqcL7/B+xZRY2qNGj!LR5PhHWG5kGEFQOMOe5kvP8k7PKs
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: 10332

On 04/06/2024 03:18, olcott wrote:
> On 6/3/2024 8:59 PM, Richard Damon wrote:
>> On 6/3/24 9:46 PM, olcott wrote:
>>> On 6/3/2024 8:38 PM, Mike Terry wrote:
>>>> On 03/06/2024 18:54, olcott wrote:
>>>>> On 6/3/2024 11:25 AM, Mike Terry wrote:
>>>>>> On 03/06/2024 04:50, olcott wrote:
>>>>>>> On 6/2/2024 10:28 PM, Mike Terry wrote:
>>>>>>>> On 03/06/2024 01:16, immibis wrote:
>>>>>>>>> The halting problem says you can't find a Turing machine that tells whether executing each 
>>>>>>>>> other Turing machine will halt. Simulation has nothing to do with the question.
>>>>>>>>
>>>>>>>> Background:
>>>>>>>>
>>>>>>>> PO claims to have refuted the common HP proof, e.g. as covered in the Linz book "An 
>>>>>>>> Introduction to Formal Languages and Automata". PO occasionally posts a link to a PDF 
>>>>>>>> containing an extract of the 5 or so pages of the book containing the proof, but I expect 
>>>>>>>> you have access to this or equivalent.
>>>>>>>>
>>>>>>>> In a nutshell, the proof goes:
>>>>>>>> -  Suppose H is a TM Halt decider that decides for any input <P><I> whether
>>>>>>>>     TM P run with input I on its input tape halts.
>>>>>>>>     [<P> is the string representation of the actual TM P, and
>>>>>>>>      <I> is the string representation of input tape I]
>>>>>>>> -  Construct from H a new TM H^ using the mechanical process described in the proof.
>>>>>>>>     If H exists, then its corresponding H^ also exists.
>>>>>>>> -  Show that the construction of H^ ensures that:
>>>>>>>>     -  if H decides input <H^><H^> (representing H^ running with input <H^>) halts,
>>>>>>>>        then that implies that H^ running with input <H^> never halts
>>>>>>>>     -  if H decides input <H^><H^> never halts,
>>>>>>>>        then that implies H^ running with input <H^> halts
>>>>>>>>     I.e. either way, H decides the specific input <H^><H^> incorrectly, contradicting
>>>>>>>>     the initial assumption that H is a halt decider.
>>>>>>>> -  So no halt decider exists.  (Every proposed halt decider decides at least one input case
>>>>>>>>     incorrectly, viz input <H^><H^>.)
>>>>>>>>
>>>>>>>> PO basically claimed he had a fully coded TM H, which CORRECTLY decides its "nemesis" input 
>>>>>>>> <H^><H^>, contradicting the logic of the Linz proof [without pointing out any actual mistake 
>>>>>>>> in the Linz proof].  Given most people here understand the Linz proof well enough to see it 
>>>>>>>> is basically sound, people were sceptical!
>>>>>>>>
>>>>>>>> It turned out PO was lying about the fully coded TM, and in fact what he actually had was 
>>>>>>>> the idea behind a C program which would "prove" his idea.  A couple of years(?) later he 
>>>>>>>> actually completed his C program and his x86utm.exe which would simulate the x86 code of his 
>>>>>>>> H and H^ to "prove" his claim.  His equivalent of Linz H is his C function H or HH, and his 
>>>>>>>> equivalent of Linz H^ is his D or DD respectively.  (They run under x86utm.exe and are not 
>>>>>>>> Windows/Unix executables.)
>>>>>>>>
>>>>>>>> H/HH use PARTIAL simulation of their input to decide halting/non-halting, returning
>>>>>>>> 0 or 1 to communicate their decision.  As you correctly point out, to the HP proof 
>>>>>>>> simulation is quite irrelevant, being just one kind of data manipulation that H may perform 
>>>>>>>> on its input string <P><I> before it decides the halting status.  So the Linz HP proof 
>>>>>>>> covers such H, no problem.
>>>>>>>> [I put PARTIAL in caps, just because there seems to be some confusion in recent threads as 
>>>>>>>> to what PO means by "simulation". He doesn't say it explicitly, despite suggestions to this 
>>>>>>>> effect, but he always means what might be called /partial/ simulation.]
>>>>>>>>
>>>>>>>> PO believes that by (partially) simulating the computation corresponding to the input <P><I> 
>>>>>>>> [i.e. calculating the successive x86 instruction steps of the computation P(I)] and 
>>>>>>>> monitoring the progress of virtual x86 state changes (like instruction address and op-code 
>>>>>>>> and so on) H could spot some pattern that reveals whether computation P(I) halts or not.  At 
>>>>>>>> this point in the partial simulation, his H would stop simulating (aka "abort" the 
>>>>>>>> simulation) and return the appropriate halt status for input <P><I>.
>>>>>>>>
>>>>>>>> Nothing remarkable so far!  Clearly a tight-loop in P /can/ be detected in this fashion, so 
>>>>>>>> /some/ <P><I> inputs /can/ be correctly determined like this.  The PO claim however is that 
>>>>>>>> the specific input <H^><H^> is correctly decided by his H.  In C terms those correspond to 
>>>>>>>> H(D,D) correctly returning the halt status of computation D(D).  [PO would probably dispute 
>>>>>>>> this, because he doesn't properly understand halting or the HP generally, or in fact pretty 
>>>>>>>> much /any abstract concept/ ]
>>>>>>>>
>>>>>>>
>>>>>>> Introduction to the Theory of Computation, by Michael Sipser
>>>>>>> https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X/
>>>>>>>
>>>>>>> On 10/13/2022 11:29:23 AM
>>>>>>> MIT Professor Michael Sipser agreed this verbatim paragraph is correct
>>>>>>> (He has neither reviewed nor agreed to anything else in this paper)
>>>>>>>
>>>>>>> <Professor Sipser agreed>
>>>>>>> If simulating halt decider H correctly simulates its input D until H
>>>>>>> correctly determines that its simulated D would never stop running
>>>>>>> unless aborted then
>>>>>>>
>>>>>>> H can abort its simulation of D and correctly report that D specifies a
>>>>>>> non-halting sequence of configurations.
>>>>>>> </Professor Sipser agreed>
>>>>>>>
>>>>>>> I have started working on what seem to be some computability issues
>>>>>>> that you pointed out with my HH. I found that they are isolated to
>>>>>>> one single element of HH. Essentially the details of how the master
>>>>>>> UTM directly executed HH passes a portion of its tape to its slaves.
>>>>>>>
>>>>>>> Nothing else seems to have any computability issues by the measure
>>>>>>> that I am using.
>>>>>>>
>>>>>>> Message-ID: <rLmcnQQ3-N_tvH_4nZ2dnZfqnPGdnZ2d@brightview.co.uk>
>>>>>>> On 3/1/2024 12:41 PM, Mike Terry wrote:
>>>>>>>  >
>>>>>>>  > Obviously a simulator has access to the internal state
>>>>>>>  > (tape contents etc.) of the simulated machine. No problem there.
>>>>>>>
>>>>>>> Because of your above comment it seems that correcting this
>>>>>>> tiny computability issue with HH is my best path forward.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> You have given the following a blatantly false review when I
>>>>>>> said the same thing another way:
>>>>>>
>>>>>> I have no idea what you're talking about.  I did not write any of what follows below.
>>>>>>
>>>>>> Also I don't believe I said anything "blatantly false".  You're incapable of judging what 
>>>>>> other people say or are thinking - you're often telling people that they'er lying to you and 
>>>>>> denying
>>>>>> "previously verified facts" etc. but its all rubbish - you're in no position to make such 
>>>>>> judgements.
>>>>>>
>>>>>>
>>>>>> Mike.
>>>>>>
>>>>>
>>>>> You said that the execution trace that I proved is correct is
>>>>> incorrect because you didn't like the way that HH was written.
>>>>> You said this without looking at my proof as you are doing
>>>>> here again.
>>>>
>>>> An execution trace that is produced by a program that is incorrect /proves/ nothing whatsoever.  
>>>> I don't need to look at your proof, as I was commenting on the value of your program output AS 
>>>> PROOF.
>>>>
>>>
>>> I provided the execution trace that HH derives
>>> *AND THE X86 SOURCE-CODE OF DD THAT PROVES THIS TRACE IS CORRECT*
>>> *AND THE X86 SOURCE-CODE OF DD THAT PROVES THIS TRACE IS CORRECT*
>>> *AND THE X86 SOURCE-CODE OF DD THAT PROVES THIS TRACE IS CORRECT*
>>
>> Then why did the trace not follow the call to H?
>>
> 
> HH(DD,DD) the trace does follow the call to HH(DD,DD)
> and fully simulates itself simulating DD.

Yes HH does simulate the call to HH(DD,DD) and certain instructions within HH, although because you 
filter those trace entries out, nobody can check that.

The point is it simulates THE WRONG INSTRUCTIONS within HH as discussed in other posts.

When HH simulates itself, the instructions simulated must be the actual instructions that "outer" HH 
would execute, because that's what simulation means.  What your HH does is simulate completely 
different instructions inside a conditional branch that asks "Am I being simulated?".  That is 
Simply Wrong, in a way that should be obvious without repeated explanation.  Trace output from a 
Simply Wrong program is not evidence for your claims.


Mike.