Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Mikko Newsgroups: comp.theory Subject: Re: DDD correctly emulated by HHH is Correctly rejected as non-halting V2 Date: Sat, 27 Jul 2024 10:21:05 +0300 Organization: - Lines: 147 Message-ID: References: <34Ocnd4voeWlDAn7nZ2dnZfqnPudnZ2d@brightview.co.uk> <056325e336f81a50f4fb9e60f90934eaac823d22@i2pn2.org> <210383b2ee318f68a96d94aec314ee8b93f79b7f@i2pn2.org> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sat, 27 Jul 2024 09:21:06 +0200 (CEST) Injection-Info: dont-email.me; posting-host="c9d45fc3af5a1949f530b625013a7212"; logging-data="3467668"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18LC7DL2aoG/+mJURVIOhbI" User-Agent: Unison/2.2 Cancel-Lock: sha1:gjUo/HtlhoKPKQb/NSqm9nYQw/8= Bytes: 7702 On 2024-07-26 14:08:11 +0000, olcott said: > On 7/26/2024 3:45 AM, Mikko wrote: >> On 2024-07-24 13:33:55 +0000, olcott said: >> >>> On 7/24/2024 3:57 AM, Mikko wrote: >>>> On 2024-07-23 13:31:35 +0000, olcott said: >>>> >>>>> On 7/23/2024 1:32 AM, 0 wrote: >>>>>> On 2024-07-22 13:46:21 +0000, olcott said: >>>>>> >>>>>>> On 7/22/2024 2:57 AM, Mikko wrote: >>>>>>>> On 2024-07-21 13:34:40 +0000, olcott said: >>>>>>>> >>>>>>>>> On 7/21/2024 4:34 AM, Mikko wrote: >>>>>>>>>> On 2024-07-20 13:11:03 +0000, olcott said: >>>>>>>>>> >>>>>>>>>>> On 7/20/2024 3:21 AM, Mikko wrote: >>>>>>>>>>>> On 2024-07-19 14:08:24 +0000, olcott said: >>>>>>>>>>>> >>>>>>>>>>>>> When we use your incorrect reasoning we would conclude >>>>>>>>>>>>> that Infinite_Loop() is not an infinite loop because it >>>>>>>>>>>>> only repeats until aborted and is aborted. >>>>>>>>>>>> >>>>>>>>>>>> You and your HHH can reason or at least conclude correctly about >>>>>>>>>>>> Infinite_Loop but not about DDD. Possibly because it prefers to >>>>>>>>>>>> say "no", which is correct about Infinte_loop but not about DDD. >>>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> *Because this is true I don't understand how you are not simply lying* >>>>>>>>>>> int main >>>>>>>>>>> { >>>>>>>>>>>    DDD(); >>>>>>>>>>> } >>>>>>>>>>> >>>>>>>>>>> Calls HHH(DDD) that must abort the emulation of its input >>>>>>>>>>> or {HHH, emulated DDD and executed DDD} never stop running. >>>>>>>>>> >>>>>>>>>> You are the lying one. >>>>>>>>>> >>>>>>>>>> If HHH(DDD) abrots its simulation and returns true it is correct as a >>>>>>>>>> halt decider for DDD really halts. >>>>>>>>>> >>>>>>>>> >>>>>>>>> (b) We know that a decider is not allowed to report on the behavior >>>>>>>>> computation that itself is contained within. >>>>>>>> >>>>>>>> No, we don't. There is no such prohibition. >>>>>>>> >>>>>>> >>>>>>> Turing machines never take actual Turing machines as inputs. >>>>>>> They only take finite strings as inputs and an actual executing >>>>>>> Turing machine is not itself a finite string. >>>>>> >>>>>> The definition of a Turing machine does not say that a Turing machine >>>>>> is not a finite string. It is an abstract mathematical object without >>>>>> a specification of its exact nature. It could be a set or a finite >>>>>> string. Its exact nature is not relevant to the theory of computation, >>>>>> which only cares about certain properties of Turing machines. >>>>>> >>>>>>> Therefore It is not allowed to report on its own behavior. >>>>>> >>>>>> Anyway, that does not follow. The theory of Turing machines does not >>>>>> prohibit anything. >>>>>> >>>>>>> Another different TM can take the TM description of this >>>>>>> machine and thus accurately report on its actual behavior. >>>>>> >>>>>> If a Turing machine can take a description of a TM as its input >>>>>> or as a part of its input it can also take its own description. >>>>>> Every Turing machine can be given its own description as input >>>>>> but a Turing machine may interprete it as something else. >>>>>> >>>>> In this case we have two x86utm machines that are identical >>>>> except that DDD calls HHH and DDD does not call HHH1. >>>> >>>> That DDD calls HHH and DDD does not call HHH1 is not a difference >>>> between two unnamed turing machines. >>>> >>> >>> The same thing happens at the Peter Linz Turing Machine level >>> I will provide that more difficult example if and only if you >>> prove that you understand this one. >> >> However, Peter Linz does not call taht same thing a difference. > > We can call everything "late for dinner" with a unique integer > index and the properties that I assert exist still exist. That you can say all sorts stupid things does not mean that it be a good idea to do so. Some of the properties you assert exsit actually do exist, some don't. > When Ĥ is applied to ⟨Ĥ⟩ > Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞ > Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn That does not specify a time or a situation. > (a) Ĥ copies its input ⟨Ĥ⟩ > (b) Ĥ invokes embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ Its not really an invocation. Ĥ imitates H with ⟨Ĥ⟩ ⟨Ĥ⟩. > (c) embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩ Imitating H, Ĥ simulates ⟨Ĥ⟩ ⟨Ĥ⟩. > (d) simulated ⟨Ĥ⟩ copies its input ⟨Ĥ⟩ Ĥ, as a part of the simulation of what its input specifecs, simulates the specifiec copying of the simulated input ⟨Ĥ⟩. > (e) simulated ⟨Ĥ⟩ invokes simulated embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ Again, this is not really an invocation. Imitating H, Ĥ simulates the simulation of H with ⟨Ĥ⟩ ⟨Ĥ⟩. > (f) simulated embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩ > (g) goto (d) with one more level of simulation > > Two complete simulations show a pair of identical TMD's are > simulating a pair of identical inputs. We can see this thus > proving recursive simulation. Detection that the simulated simulation is identical to the simulating simulation is not trivial. In particular, it requires that the simulator is able to identify a part of the simulated process as a simulation. > When embedded_H is accountable for the behavior of its > input and not accountable for the behavior of the > computation that it is contained within then embedded_H > is necessarily correct to transition to its own Ĥ.qn state. Embedded_H is not accountable for anything. It just is there and does whatever it does. There is no requirements on Ĥ so whatever it does it can do no wrong. H is required to predict whether Ĥ ⟨Ĥ⟩, it executed, will terminate. H is not a halt decider if it says "yes" and Ĥ ⟨Ĥ⟩ does not terminate, nor if it says "no" and terminates. -- Mikko