| Deutsch English Français Italiano |
|
<usfjin$1r7ap$1@dont-email.me> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: immibis <news@immibis.com> Newsgroups: comp.theory,sci.logic Subject: Re: Refutation of the Peter Linz Halting Problem proof 2024-03-05 --partial agreement-- Date: Fri, 8 Mar 2024 18:57:43 +0100 Organization: A noiseless patient Spider Lines: 148 Message-ID: <usfjin$1r7ap$1@dont-email.me> References: <us8shn$7g2d$1@dont-email.me> <us92f0$uvql$4@i2pn2.org> <us931e$8gmr$1@dont-email.me> <usa4rk$10ek4$3@i2pn2.org> <usa5to$gp0j$1@dont-email.me> <usa8lp$10ek5$5@i2pn2.org> <usa9o9$ho7b$1@dont-email.me> <usag21$118jg$1@i2pn2.org> <usanbu$klu7$1@dont-email.me> <usas0v$11q96$2@i2pn2.org> <usavq1$m7mn$1@dont-email.me> <usb01q$m897$1@dont-email.me> <usb0q0$m7mn$5@dont-email.me> <usb8d4$nksq$1@dont-email.me> <usb9e9$nkt8$4@dont-email.me> <usck1s$13k1e$2@dont-email.me> <uscs49$15f45$1@dont-email.me> <usdq1r$1be15$3@dont-email.me> <usdrjq$1bkg1$2@dont-email.me> <usdteu$15q44$1@i2pn2.org> <use0nb$1ga79$1@dont-email.me> <use249$15q44$6@i2pn2.org> <use899$1hhbj$1@dont-email.me> <usea2m$167tc$4@i2pn2.org> <useb9n$1i1ob$1@dont-email.me> <usecb8$167tc$5@i2pn2.org> <useep5$1ie34$3@dont-email.me> <usefpn$167kp$3@i2pn2.org> <usfhmm$1qkfn$3@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Fri, 8 Mar 2024 17:57:43 -0000 (UTC) Injection-Info: dont-email.me; posting-host="3f1efc9d2316cfb35da63e79af4f81c5"; logging-data="1940825"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+cdAwijCLRg5tDb6wplK+C" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:3p0j90cqzEWGh5krS7/FtGJGF6E= Content-Language: en-US In-Reply-To: <usfhmm$1qkfn$3@dont-email.me> Bytes: 8737 On 8/03/24 18:25, olcott wrote: > On 3/8/2024 1:47 AM, Richard Damon wrote: >> On 3/7/24 11:29 PM, olcott wrote: >>> On 3/8/2024 12:48 AM, Richard Damon wrote: >>>> On 3/7/24 10:30 PM, olcott wrote: >>>>> On 3/8/2024 12:09 AM, Richard Damon wrote: >>>>>> On 3/7/24 9:38 PM, olcott wrote: >>>>>>> On 3/7/2024 9:53 PM, Richard Damon wrote: >>>>>>>> On 3/7/24 7:29 PM, olcott wrote: >>>>>>>>> On 3/7/2024 8:34 PM, Richard Damon wrote: >>>>>>>>>> On 3/7/24 6:02 PM, olcott wrote: >>>>>>>>>>> On 3/7/2024 7:35 PM, immibis wrote: >>>>>>>>>>>> On 7/03/24 18:05, olcott wrote: >>>>>>>>>>>>> On 3/7/2024 8:47 AM, immibis wrote: >>>>>>>>>>>>>> On 7/03/24 03:40, olcott wrote: >>>>>>>>>>>>>>> On 3/6/2024 8:22 PM, immibis wrote: >>>>>>>>>>>>>>>> On 7/03/24 01:12, olcott wrote: >>>>>>>>>>>>>>>>> On 3/6/2024 5:59 PM, immibis wrote: >>>>>>>>>>>>>>>>>> On 7/03/24 00:55, olcott wrote: >>>>>>>>>>>>>>>>>>> Ĥ.H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.Hqn >>>>>>>>>>>>>>>>>>> Correctly reports that Ĥ.H ⟨Ĥ⟩ ⟨Ĥ⟩ must abort its >>>>>>>>>>>>>>>>>>> simulation. >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* H.qy >>>>>>>>>>>>>>>>>>> Correctly reports that H ⟨Ĥ⟩ ⟨Ĥ⟩ need not abort its >>>>>>>>>>>>>>>>>>> simulation. >>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>> What are the exact steps which the exact same program >>>>>>>>>>>>>>>>>> with the exact same input uses to get two different >>>>>>>>>>>>>>>>>> results? >>>>>>>>>>>>>>>>>> I saw x86utm. In x86utm there is a mistake because Ĥ.H >>>>>>>>>>>>>>>>>> is not defined to do exactly the same steps as H, >>>>>>>>>>>>>>>>>> which means you failed to do the Linz procedure. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> Both H(D,D) and H1(D,D) answer the exact same question: >>>>>>>>>>>>>>>>> Can I continue to simulate my input without ever >>>>>>>>>>>>>>>>> aborting it? >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> Both H(D,D) and H1(D,D) are computer programs (or Turing >>>>>>>>>>>>>>>> machines). They execute instructions (or transitions) in >>>>>>>>>>>>>>>> sequence, determined by their programming and their input. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> Yet because they both know their own machine address >>>>>>>>>>>>>>> they can both correctly determine whether or not they >>>>>>>>>>>>>>> themselves are called in recursive simulation. >>>>>>>>>>>>>> >>>>>>>>>>>>>> They cannot do anything except for exactly what they are >>>>>>>>>>>>>> programmed to do. >>>>>>>>>>>>> >>>>>>>>>>>>> H1(D,D) and H(D,D) are programmed to do this. >>>>>>>>>>>>> Because H1(D,D) simulates D(D) that calls H(D,D) that >>>>>>>>>>>>> aborts its simulation of D(D). H1 can see that its >>>>>>>>>>>>> own simulated D(D) returns from its call to H(D,D). >>>>>>>>>>>>> >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> An Olcott machine can perform an equivalent operation. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> Because Olcott machines are essentially nothing more than >>>>>>>>>>>>>>> conventional UTM's combined with Conventional Turing machine >>>>>>>>>>>>>>> descriptions their essence is already fully understood. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> The input to Olcott machines can simply be the conventional >>>>>>>>>>>>>>> space delimited Turing Machine input followed by four >>>>>>>>>>>>>>> spaces. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> This is followed by the machine description of the machine >>>>>>>>>>>>>>> that the UTM is simulating followed by four more spaces. >>>>>>>>>>>>>> >>>>>>>>>>>>>> To make the Linz proof work properly with Olcott machines, >>>>>>>>>>>>>> Ĥ should search for 4 spaces, delete its own machine >>>>>>>>>>>>>> description, and then insert the description of the >>>>>>>>>>>>>> original H. Then the Linz proof works for Olcott machines. >>>>>>>>>>>>> >>>>>>>>>>>>> That someone can intentionally break an otherwise correct >>>>>>>>>>>>> halt decider >>>>>>>>>>>> >>>>>>>>>>>> It always gives exactly the same answer as the working one, >>>>>>>>>>>> so how is it possibly broken? >>>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.Hq0 ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.Hqy ∞ // Ĥ applied to ⟨Ĥ⟩ halts >>>>>>>>>>> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.Hq0 ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.Hqn // Ĥ applied to ⟨Ĥ⟩ does >>>>>>>>>>> not halt >>>>>>>>>>> >>>>>>>>>>> When this is executed in an Olcott machine then >>>>>>>>>>> Ĥ.H ⟨Ĥ⟩ ⟨Ĥ⟩ <Ĥ> is a different computation than H ⟨Ĥ⟩ ⟨Ĥ⟩ <H> >>>>>>>>>> >>>>>>>>>> WHY? >>>>>>>>>> >>>>>>>>>> The Master UTM will not change the usage at H^.H, because that >>>>>>>>>> is just an internal state of the Machine H^ >>>>>>>>>> >>>>>>>>> >>>>>>>>> The ONLY thing that the master UTM does differently is append >>>>>>>>> the TMD to the TMD's own tape. >>>>>>>> >>>>>>>> Right, so it gives H and H^ that input. >>>>>>>> >>>>>>>> H^ can erase that input and replace it. >>>>>>>> >>>>>>>>> >>>>>>>>>> At that point we have the IDENTICAL set of transitions (with >>>>>>>>>> just an equivalence mapping of state numbers) as H will have, >>>>>>>>>> and the EXACT same input as H >>>>>>>>> >>>>>>>>> it is stipulated by the definition of Olcott machines >>>>>>>>> Ĥ.H ⟨Ĥ⟩ ⟨Ĥ⟩ <Ĥ> // last element is <Ĥ> (not H) >>>>>>>> >>>>>>>> Nope. >>>>>>>> >>>>>>>> H^.H isn't a "Olcott Machine" it is a sub-machine of H^ >>>>>>> >>>>>>> You already know that there is no such thing as sub-machines of >>>>>>> Turing machines. Turing machines have a set of states and a tape. >>>>>>> They have no sub-machines. >>>>>> >>>>>> A "Sub-Machine" of a Turing Machine is where you put a copy of >>>>>> another Turing Machine into the state space of the overall/parent >>>>>> machine, >>>>>> >>>>>> When the machine H^ reaches the state H^.H, then it encounters the >>>>>> EXACT sequence of states (after the eqivalence mapping generated >>>>>> when inserting them H's q0 -> H^.Hqo and so on) >>>>>> >>>>>> It is called a sub-machine because it acts largely as if that >>>>>> Turing Machihe "called" the equivalent Turing Machine as a >>>>>> subroutine, only the machine code was expanded "inline". >>>>> >>>>> There is no way that any conventional Turing machine can tell >>>>> that the states of another Turing machine are embedded withing it. >>>> >>>> It doesn't need to "KNOW", but it HAS THEM there. >>>> >>>> It was DESIGNED that way, so the programmer knows what he did. >>>> >>> >>> immibis thought that Ĥ could copy external <H> on top of internal <Ĥ> >>> Your words seemed to agree with this. >> >> It can't get the <H> from an external source, but can have a copy of >> that inside of it and use that to replace it. >> > > Not unless it is yet another parameter, thus diverges > too far from the original Linz. Why can't a Turing machine write the finite string <H> onto its own tape?