Deutsch English Français Italiano |
<v4us79$21810$3@dont-email.me> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: olcott <polcott333@gmail.com> Newsgroups: comp.theory,sci.logic Subject: Re: Simulating termination analyzers by dummies --- What does halting mean? Date: Wed, 19 Jun 2024 10:07:21 -0500 Organization: A noiseless patient Spider Lines: 105 Message-ID: <v4us79$21810$3@dont-email.me> References: <v4oaqu$f9p5$1@dont-email.me> <v4os9e$i70m$1@dont-email.me> <v4p9mb$lavj$1@dont-email.me> <v4qe53$a0nm$1@i2pn2.org> <v4qn65$10qh6$1@dont-email.me> <v4qnkf$a0nm$5@i2pn2.org> <v4qpvo$10qh6$2@dont-email.me> <v4qrmd$a0nm$6@i2pn2.org> <v4qrr8$15beg$1@dont-email.me> <v4qsav$a0nn$3@i2pn2.org> <v4qtaa$15gc5$1@dont-email.me> <v4qu3p$a0nm$7@i2pn2.org> <v4quti$15nn8$1@dont-email.me> <v4rrge$bivn$1@i2pn2.org> <v4s1l0$1boeu$6@dont-email.me> <v4seq5$cbcu$1@i2pn2.org> <v4sfuo$1enie$1@dont-email.me> <v4u48g$1rrod$3@dont-email.me> <v4ulde$1vpm0$3@dont-email.me> <v4uou1$1vtc8$3@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Wed, 19 Jun 2024 17:07:22 +0200 (CEST) Injection-Info: dont-email.me; posting-host="c0498080d6b8a2710b4ab7de903a0762"; logging-data="2138144"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/nTlbGGT7FZAiSBvtuyYNm" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:zCluLbYuYKhVtncrnDsolMAWLEA= In-Reply-To: <v4uou1$1vtc8$3@dont-email.me> Content-Language: en-US Bytes: 5333 On 6/19/2024 9:11 AM, Fred. Zwarts wrote: > Op 19.jun.2024 om 15:11 schreef olcott: >> On 6/19/2024 3:18 AM, Fred. Zwarts wrote: >>> Op 18.jun.2024 om 19:25 schreef 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. >>>> >>>> Halting is a technical term-of-the-art that corresponds >>>> to terminates normally. Because Turing machines are >>>> abstract mathematical objects there has been no notion >>>> of abnormal termination for a Turing machine. >>>> >>>> We can derive a notion of abnormal termination for Turing >>>> machines from the standard terms-of-the-art. >>>> >>>> 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. >>>> >>>> A UTM can be adapted so that it only simulates a fixed number >>>> of iterations of an input that loops. When this UTM stops >>>> simulating this Turing machine description we cannot correctly >>>> say that this looping input halted. >>>> >>> >>> If the code specifies 5 iterations and the simulator simulates only 3 >>> iterations, it is incorrect to conclude that the repetition show >>> non-halting behaviour. >> >> It is correct do say that the simulated input did not terminate >> normally, thus defining the notion of abnormal termination >> within Turing machines. >> >>> Similarly, when your H, H0, or other H simulates itself, its >>> simulation aborts one cycle too early and therefore the non-halting >>> conclusion is incorrect. >> >> I was confused bout this for three days four years ago and then I >> got over it. No simulating termination analyzer can wait for an >> inner instance of itself to abort the simulation or it waits forever. >> >> Whenever the outer directly executed simulating termination analyzer >> waits for any fixed number of repeating states it remains permanently >> ahead of the next inner instance by exactly one repeating state. If >> this is going to be permanently over your head then we need to stop >> talking. > > No, I understand it perfectly, but it seems to be over your head. We > agree that H needs to stop to prevent infinite recursion, but it is over > your head to see that when it stops, it misses the part of itself where > its simulation also stops, one repeating state further. So, the > non-halting conclusion is wrong, because the abort is premature. typedef void (*ptr)(); int H0(ptr P); void Infinite_Loop() { HERE: goto HERE; } void Infinite_Recursion() { Infinite_Recursion(); } void DDD() { H0(DDD); } int main() { H0(Infinite_Loop); H0(Infinite_Recursion); H0(DDD); } Every C programmer that knows what an x86 emulator is knows that when H0 emulates the machine language of Infinite_Loop, Infinite_Recursion, and DDD that it must abort these emulations so that itself can terminate normally. Every C programmer has agreed thus you simply don't know these things well enough. > So, your reasoning must lead to the only possible conclusion that a > simulator is unable to simulate itself properly, which causes false > negatives if its return value must be interpreted as a non-halting > behaviour. Instead, a return value of 'false' indicates an 'unable to > simulate' state of the simulator, which is not equivalent to 'non-halting'. -- Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer