Path: ...!weretis.net!feeder9.news.weretis.net!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory,sci.logic
Subject: Re: Why does Olcott care about simulation, anyway? --- Mikes Review
Date: Mon, 3 Jun 2024 07:14:37 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <v3k8it$2scls$1@i2pn2.org>
References: <v3j20v$3gm10$2@dont-email.me>
 <J_CdnTaA96jxpcD7nZ2dnZfqnPudnZ2d@brightview.co.uk>
 <v3jei1$3o3a7$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 3 Jun 2024 11:14:37 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="3027644"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
Content-Language: en-US
In-Reply-To: <v3jei1$3o3a7$1@dont-email.me>
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 9579
Lines: 184

On 6/2/24 11:50 PM, 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>

Right, so if can show that IF H can show that CORRECTLY SIMULTED D WOULD 
NEVER STOP RUNNING UNLESS ABORTED.

THe ONLY definition of "Correctly SImulated" that Professir Sipser would 
use here is that of a UTM, which would be a simulation that never stops, 
so, since D, by definition, uses the actual H that is being used, which 
if it avails itself of your last clause, WILL return 0 to ALL callers of 
H(D,D), the correct (which is complete) simulation of D will see that 
return 0 happen and D halt, so H can NEVER have "corrrectly decided" 
that something that doesn't happen will happen.

This has been explained to you many times, so it can't be an "honest 
mistake" so must be a reckless disregard for the truth, or you just have 
a mental inability to understand the truth, either of which just makes 
you a Pathological Liar.

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

Which shows part of your issue, there need not be a "master UTM" present 
at all, and a UTM can't effect the behavior of "its inputs" because the 
definition of a UTM is that it exactly recreates what the machines 
described by its inputs would do when they are just run.

> 
> 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:
> 
> *We can see that the following DD cannot possibly halt when*
> *correctly simulated by every HH that can possibly exist*

Because the statements are different.

And thus you are shown to be LYING.

> 
> typedef int (*ptr)();  // ptr is pointer to int function in C
> 00       int HH(ptr p, ptr i);
> 01       int DD(ptr p)
> 02       {
> 03         int Halt_Status = HH(p, p);
> 04         if (Halt_Status)
> 05           HERE: goto HERE;
> 06         return Halt_Status;
> 07       }
> 
> _DD()
> [00001c22] 55         push ebp
> [00001c23] 8bec       mov ebp,esp
> [00001c25] 51         push ecx
> [00001c26] 8b4508     mov eax,[ebp+08]
> [00001c29] 50         push eax        ; push DD 1c22
> [00001c2a] 8b4d08     mov ecx,[ebp+08]
> [00001c2d] 51         push ecx        ; push DD 1c22
> [00001c2e] e80ff7ffff call 00001342   ; call HH
> [00001c33] 83c408     add esp,+08
> [00001c36] 8945fc     mov [ebp-04],eax
> [00001c39] 837dfc00   cmp dword [ebp-04],+00
> [00001c3d] 7402       jz 00001c41
========== REMAINDER OF ARTICLE TRUNCATED ==========