Path: ...!news.nobody.at!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Mikko Newsgroups: comp.theory Subject: Re: Simulating termination analyzers by dummies --- What does halting mean? Date: Thu, 20 Jun 2024 08:29:14 +0300 Organization: - Lines: 48 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Thu, 20 Jun 2024 07:29:15 +0200 (CEST) Injection-Info: dont-email.me; posting-host="f2c5be32a8e18ed9d3dcb1608f59dff0"; logging-data="2569081"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/zSm8YNhkfyPyvqDI6NWGT" User-Agent: Unison/2.2 Cancel-Lock: sha1:n6bnztplfjjdAo2ChxEdz69VZoY= Bytes: 3313 On 2024-06-19 14:05:29 +0000, olcott said: > On 6/19/2024 4:29 AM, Alan Mackenzie wrote: >> olcott wrote: >>> 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. >> >> I doubt that very much. The whole point of turing machines is to remove >> ambiguity and unneeded features from the theory of computation. A third >> alternative state is unneeded. >> > > Some people say that a TM can halt in a non-final state. People may use different words to express the same facts. What some people call "halting in a non-final state" is called "rejecting" by some other people. But the facts are what they are independently of the words used to express them. -- Mikko