Path: nntp.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: "Fred. Zwarts" Newsgroups: comp.theory,sci.logic Subject: Re: How do simulating termination analyzers work? ---Truth Maker Maximalism FULL_TRACE Date: Fri, 18 Jul 2025 13:13:13 +0200 Organization: A noiseless patient Spider Lines: 138 Message-ID: <105da89$2asb4$5@dont-email.me> References: <102sjg5$2k3e9$1@dont-email.me> <104e164$2852a$1@dont-email.me> <104e6nd$12ua$1@news.muc.de> <104e93k$29rpg$1@dont-email.me> <104ed4k$223c$1@news.muc.de> <104ehua$2c91h$1@dont-email.me> <104epfu$nqi$1@news.muc.de> <104fdma$2n8gq$1@dont-email.me> <104gkad$2f8e$1@news.muc.de> <10515pj$2v547$1@dont-email.me> <1051r18$36s16$3@dont-email.me> <105394s$3ev5b$15@dont-email.me> <1054he7$3s0eq$6@dont-email.me> <5erdQ.67036$r61e.50840@fx11.ams4> <1058fss$pn5l$3@dont-email.me> <49480dece30605ff692baac78083722e2a25b7cf@i2pn2.org> <1058hht$q07u$2@dont-email.me> <1058onb$raqa$1@dont-email.me> <105ac8p$25t70$2@dont-email.me> <105aut4$1bk0p$4@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Fri, 18 Jul 2025 11:13:14 +0000 (UTC) Injection-Info: dont-email.me; posting-host="56eebd65a3e7f2d8098d3b9bf50a1deb"; logging-data="2453860"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/03x7aGV7TBv5My30L2YEl" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:kJk38rpOcIaj2Lq6fnZK8uvBxvs= Content-Language: nl, en-GB In-Reply-To: <105aut4$1bk0p$4@dont-email.me> Op 17.jul.2025 om 15:47 schreef olcott: > On 7/17/2025 3:29 AM, Fred. Zwarts wrote: >> Op 16.jul.2025 om 19:49 schreef olcott: >>> >>> _DDD() >>> [00002192] 55             push ebp >>> [00002193] 8bec           mov ebp,esp >>> [00002195] 6892210000     push 00002192  // push DDD >>> [0000219a] e833f4ffff     call 000015d2  // call HHH >>> [0000219f] 83c404         add esp,+04 >>> [000021a2] 5d             pop ebp >>> [000021a3] c3             ret >>> Size in bytes:(0018) [000021a3] >>> >>> Each element of the infinite set of functions >>> at machine address 000015d2 that emulates 0 to ∞ >>> instructions of the above machine code never >>> reaches its emulated "ret" instruction final >>> halt state BECAUSE DDD CALLS EACH EMULATOR IN >>> RECURSIVE EMULATION. > >> And because HHH would simulate DDD in recursive simulation. >> HHH cooperates with DDD to create a recursion. Without HHH starting a >> new simulation, there would not be a recursion. > The input to HHH(DDD) specifies recursive emulation. Only because HHH performs a recursive simulation. But, the input specifies a finite recursion, because DDD calls an aborting HHH that returns the value 0. > >> This is already evidence that simulation is not the right tool to >> analyse the input. >> > > In other words you disagree that a simulation by a UTM > is a correct measure of behavior. (A simulation by a UTM > is defined to be a correct measure of behavior). Apparently you have a problem with reading. An UTM can be used to determine halting behaviour only if it completes and reaches the final halt state. It can determine halting behaviour, but it cannot detect non-halting behaviour. If an UTM does not reach the final halt state, we need other means to determine the halting behaviour. > >> But HHH does abort. So, there is no infinite recursion. So, there is a >> final halt state. But the abort does not help to reach that final halt >> state. HHH still fails to reach it. Further only irrelevant repeated claims without evidence: > > _DDD() > [00002192] 55             push ebp > [00002193] 8bec           mov ebp,esp > [00002195] 6892210000     push 00002192  // push DDD > [0000219a] e833f4ffff     call 000015d2  // call HHH > [0000219f] 83c404         add esp,+04 > [000021a2] 5d             pop ebp > [000021a3] c3             ret > Size in bytes:(0018) [000021a3] You have been corrected many times that these 18 bytes cannot be the full input. The call at 0000219a refers to an address 000015d2 outside this region. The input for a simulator includes DDD and all functions called by it, directly or indirectly, in this case including the HHH, of which you claim that it returns a value 0. Using this fact, we see that a correct simulation, following the semantics of the x86 language, will continue at 0000219f with this value and reach the final halt state at 000021a3. That HHH cannot reach that final halt state is a failure of HHH: it cannot do a correct simulation up to the end. > > Each element of the infinite set of functions > at machine address 000015d2 that emulates 0 to ∞ > instructions of the above machine code never > reaches its emulated "ret" instruction final > halt state BECAUSE DDD CALLS EACH EMULATOR IN > RECURSIVE EMULATION. Irrelevant, because there is only a finite recursion for aborting simulators. Yes, all aborting simulators fail to reach the final halt state, illustrating the fact that for any input that includes HHH, HHH is not the correct tool to analyse the behaviour specified in the input. > > *ChatGPT agrees and provides the reasoning why it agrees* > https://chatgpt.com/share/6877f09c-7b18-8011-b075-ea3671e57886 > >> This illustrates that simulation is not the right tool for this input. > > Disagreeing with the definition of a UTM is incorrect. But applying the definition of an UTM to an aborting simulator is not honest. An aborting simulator is not a pure UTM. > >> Each element in the infinite set fails to reach the final halt state. > > Because it remains stuck in recursive emulation. > > void Infinite_Recursion() > { >   Infinite_Recursion(); >   return; > } > > Infinite_Recursion() correctly simulated bu HHH also > cannot possibly reach its own simulated "return" > statement final halt state. Not possibly reaching > final halt state is the correct measure on non-halting > for both HHH(Infinite_Recursion) and HHH(DDD). But aborting at some point is not a sufficient proof for non-termination. Other logic is needed to prove non-termination. void Finite_Recursion (int N) { if (N > 0) Finite_Recursion (N - 1); printf ("Olcott thinks this is never printed.\n"); } When HHH would conclude that there is non-termination behaviour, because it sees recursion, it is in error. So, it is important to see the difference between finite recursion and infinite recursion. In the case of DDD based on an aborting HHH, there is only a finite recursion. Even if HHH cannot see that, the specification of a halting program does not change. > >> There is a final halt state for each of them, but the all fail to >> reach it. (Of course the very different HHH that does not abort at >> all, has no final halt state, so it fails as well.) > >