Path: ...!weretis.net!feeder9.news.weretis.net!i2pn.org!i2pn2.org!.POSTED!not-for-mail From: Richard Damon 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: References: 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: 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

>> whether >>     TM P run with input I on its input tape halts. >>     [

is the string representation of the actual TM P, and >>      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 (representing H^ running with input >> ) halts, >>        then that implies that H^ running with input never halts >>     -  if H decides input never halts, >>        then that implies H^ running with input halts >>     I.e. either way, H decides the specific input >> 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 .) >> >> PO basically claimed he had a fully coded TM H, which CORRECTLY >> decides its "nemesis" input , 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

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

[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

. >> >> Nothing remarkable so far!  Clearly a tight-loop in P /can/ be >> detected in this fashion, so /some/

inputs /can/ be correctly >> determined like this.  The PO claim however is that the specific input >> 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) > > > 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. > 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: > 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 ==========