Path: ...!2.eu.feeder.erje.net!3.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Why does Olcott care about simulation, anyway? --- Mikes Review
Date: Thu, 6 Jun 2024 18:18:12 +0300
Organization: -
Lines: 201
Message-ID: <v3sjvk$1ibni$1@dont-email.me>
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> <v3lvc6$2uv03$6@i2pn2.org> <v3nhuh$gatu$4@dont-email.me> <v3p2ss$s8bi$1@dont-email.me> <v3po03$v133$5@dont-email.me> <v3rrq9$1e763$1@dont-email.me> <v3scm6$1gra7$5@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 06 Jun 2024 17:18:13 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="2c3efa56d70eb2a475af8055aec55f19";
	logging-data="1650418"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+sKA4D3thwx0gzJ1J1IeLm"
User-Agent: Unison/2.2
Cancel-Lock: sha1:ZQK9/f5JETz6dVEZw9Vika3k+DQ=
Bytes: 11979

On 2024-06-06 13:13:42 +0000, olcott said:

> On 6/6/2024 3:25 AM, Mikko wrote:
>> On 2024-06-05 13:08:19 +0000, olcott said:
>> 
>>> On 6/5/2024 2:08 AM, Mikko wrote:
>>>> On 2024-06-04 17:12:49 +0000, olcott said:
>>>> 
>>>>> On 6/3/2024 9:49 PM, Richard Damon wrote:
>>>>>> On 6/3/24 10:18 PM, 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.
>>>>>> 
>>>>>> So, where are the instuctions of HH shown?
>>>>>> 
>>>>>> I guess you are just a LIAR.
>>>>>> 
>>>>> 
>>>>> It might be good for you to quit calling me a liar, everyone here
>>>>> knows that I am not a liar.
>>>> 
>>>> Most people here don't care whether you are a liar or a fool.
>>>> 
>>> 
>>> Richard understands that:
========== REMAINDER OF ARTICLE TRUNCATED ==========