Path: ...!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: Wed, 5 Jun 2024 10:08:12 +0300
Organization: -
Lines: 176
Message-ID: <v3p2ss$s8bi$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>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 05 Jun 2024 09:08:13 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="f59ac17d296a13bc5d3841a994cc1bf4";
	logging-data="926066"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18Qgm/vLdJNvpPFNXL9No5C"
User-Agent: Unison/2.2
Cancel-Lock: sha1:K1lZHe46TCvCM1BdZ7aTfVH+8ps=
Bytes: 10325

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.

-- 
Mikko