Deutsch English Français Italiano |
<v4piea$l7le$5@dont-email.me> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!news.nobody.at!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: "Fred. Zwarts" <F.Zwarts@HetNet.nl> Newsgroups: comp.theory,sci.logic Subject: Re: Simulating termination analyzers for dummies Date: Mon, 17 Jun 2024 16:49:45 +0200 Organization: A noiseless patient Spider Lines: 105 Message-ID: <v4piea$l7le$5@dont-email.me> References: <v4oaqu$f9p5$1@dont-email.me> <v4os9e$i70m$1@dont-email.me> <v4p9mb$lavj$1@dont-email.me> <v4pdph$l7lf$1@dont-email.me> <v4pepj$ln46$15@dont-email.me> <v4pgk3$l7le$2@dont-email.me> <v4phhl$mub6$2@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 17 Jun 2024 16:49:47 +0200 (CEST) Injection-Info: dont-email.me; posting-host="fee104aae69170b4ce923c38ec4c77c3"; logging-data="695982"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+vyK7sv26r5ZJSAB7CrWN0" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:uldegc5zjw0HeUlrqaSjmG5Fs1U= Content-Language: en-GB In-Reply-To: <v4phhl$mub6$2@dont-email.me> Bytes: 5091 Op 17.jun.2024 om 16:34 schreef olcott: > On 6/17/2024 9:18 AM, Fred. Zwarts wrote: >> Op 17.jun.2024 om 15:47 schreef olcott: >>> On 6/17/2024 8:30 AM, Fred. Zwarts wrote: >>>> Op 17.jun.2024 om 14:20 schreef olcott: >>>>> On 6/17/2024 3:31 AM, Fred. Zwarts wrote: >>>>>> Op 17.jun.2024 om 05:33 schreef olcott: >>>>>>> To understand this analysis requires a sufficient knowledge of >>>>>>> the C programming language and what an x86 emulator does. >>>>>>> >>>>>>> Unless every single detail is made 100% explicit false assumptions >>>>>>> always slip though the cracks. This is why it must be examined at >>>>>>> the C level before it is examined at the Turing Machine level. >>>>>>> >>>>>>> typedef void (*ptr)(); >>>>>>> int H0(ptr P); >>>>>>> >>>>>>> void Infinite_Loop() >>>>>>> { >>>>>>> HERE: goto HERE; >>>>>>> } >>>>>>> >>>>>>> void Infinite_Recursion() >>>>>>> { >>>>>>> Infinite_Recursion(); >>>>>>> } >>>>>>> >>>>>>> void DDD() >>>>>>> { >>>>>>> H0(DDD); >>>>>>> return; >>>>>>> } >>>>>>> >>>>>>> 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. >>>>>>> >>>>>>> When this is construed as non-halting criteria then simulating >>>>>>> termination analyzer H0 is correct to reject these inputs as non- >>>>>>> halting. >>>>>>> >>>>>> >>>>>> For Infinite_Loop and Infinite_Recursion that might be true, >>>>>> because there the simulator processes the whole input. >>>>>> >>>>>> The H0 case is very different. For H0 there is indeed a false >>>>>> assumption, as you mentioned. Here H0 needs to simulate itself, >>>>>> but the simulation is never able to reach the final state of the >>>>>> simulated self. The abort is always one cycle too early, so that >>>>>> the simulating H0 misses the abort. Therefore this results in a >>>>>> false negative. >>>>>> (Note that H0 should process its input, which includes the H0 that >>>>>> aborts, not a non-input with an H that does not abort.) >>>>>> >>>>>> This results in a impossible dilemma for the programmer. It he >>>>>> creates a H that does not abort, it will not terminate. >>>>> >>>>> *Therefore what I said is correct* >>>> >>>> No, that is not a logical conclusion. >>> >>> 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. >> >> That might be correct. >>> >>> When this is construed as non-halting criteria then simulating >>> termination analyzer H0 is correct to reject these inputs as non- >>> halting. >> >> That is wrong. It only shows that H0 is unable to simulate itself. It >> tells nothing about the halting of the input. >> >>> >>> *Too late you have already affirmed the words above* >>> Affirming the first part necessitates the second part. >>> >> That is not logical. If a non-aborting program is wrong, it does not >> follow that a program that aborts is correct. >> Please, think before you reply. >> >> So, I repeat: >> The logical conclusion if both aborting and not aborting result in >> errors, is: a halt-decider cannot be based on such a simulation. > > Your view here is merely ignorant of the fact that deciders > must report on the behavior specified by their inputs. > It is incorrect to assume that a failing simulation is able to report about its input. The simulation fails, because H0 is unable to simulate itself.