Path: ...!feed.opticnetworks.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory Subject: Re: Simulating termination analyzers by dummies --- What does halting mean? Date: Tue, 18 Jun 2024 16:54:31 -0500 Organization: A noiseless patient Spider Lines: 82 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Tue, 18 Jun 2024 23:54:32 +0200 (CEST) Injection-Info: dont-email.me; posting-host="817dd47f58e869d78494e0bf13c00909"; logging-data="1640647"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/Z/cLQRF9RFKZlWdq57R9x" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:utHdQgVcvwk3Yb9RU+90vO88Svk= In-Reply-To: Content-Language: en-US Bytes: 4309 On 6/18/2024 4:36 PM, Alan Mackenzie wrote: > [ Followup-To: set ] > > In comp.theory olcott wrote: >> On 6/18/2024 12:57 PM, joes wrote: >>> Am Tue, 18 Jun 2024 12:25:44 -0500 schrieb olcott: >>>> On 6/18/2024 12:06 PM, joes wrote: >>>> void DDD() >>>> { >>>> H0(DDD); >>>> } >>>> DDD correctly simulated by any H0 cannot possibly halt. >>>>> DDD halts iff H0 halts. > >>> So H0 returns "doesn't halt" to DDD, which then stops running, >>> so H0 should have returned "halts". > >> This was three messages ago. >> I had to make sure that you understood that halting >> does not mean stopping for any reason and only includes >> the equivalent of terminating normally. > > No. You're wrong, here. A turing machine is either running or it's > halted. There's no third alternative. If your C programs are not in one > of these two states, they're not equivalent to turing machines. > Although I agree with this there seems to be nuances of disagreement across the experts. >> DDD correctly emulated by H0 DOES NOT TERMINATE NORMALLY. > > There is no concept of "normal" termination in a turing machine. The > thing is either running or it's halted. > I develop one within the conventional notions below. >>>> Some TM's loop and thus never stop running, this is classical >>>> non-halting behavior. UTM's simulate Turing machine descriptions. >>>> This is the same thing as an interpreter interpreting the source-code of >>>> a program. >>> Some TMs do not loop and do not halt. > >>>> A UTM can be adapted so that it only simulates a fixed number of >>>> iterations of an input that loops. > > As has often been said, it is then no longer a universal turing machine. > None-the-less it does derive the notion of abnormal termination as applied to Turing Machines. >>>> When this UTM stops simulating this Turing machine description we >>>> cannot correctly say that this looping input halted. > > Yes, we can. It has been designed to count to 42 then halt. It is then > in the halted state. > Two different machines. (a) The TM description of a looping machine. (b) A UTM that has been adapted to count to five repeating states before it aborts its simulation of the looping machine. >>> Yes. We also cannot say that that input was simulated correctly. > > Indeed, not. > It is a mistake for a simulating termination analyzer to simulate infinite repeating states. >> -- >> Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius >> hits a target no one else can see." Arthur Schopenhauer > -- Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer