Sujet : Re: No one can correctly refute that simulating abort decider A(D,D) is correct
De : F.Zwarts (at) *nospam* HetNet.nl (Fred. Zwarts)
Groupes : comp.theory sci.logicDate : 27. Mar 2024, 21:57:13
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <uu1tmp$31mm4$2@dont-email.me>
References : 1
User-Agent : Mozilla Thunderbird
Op 27.mrt.2024 om 20:04 schreef olcott:
01 void B(ptr x) // ptr is pointer to void function
02 {
03 A(x, x);
04 return;
05 }
06
07 void main()
08 {
09 A(B,B);
10 }
*Execution Trace*
Line 09: main() invokes A(B,B);
*keeps repeating* (unless aborted)
That is a premature conclusion when A is not specified. It holds if A does not halt. If A returns, then B will halt (unless aborted).
So, the problem of not halting is not in B but in the unspecified A. If A halts, B will halt. If A does not halt, B will not halt.
Even a beginner will see it.
Line 03: simulated B(B) invokes simulated A(B,B) that simulates B(B)
but not completely, because A aborts the simulation and halts, which makes that B halts too (unless aborted).
*Simulation invariant*
B correctly simulated by A cannot possibly reach past its own line 03.
Except if A aborts and halts, because then also B halts (unless aborted).
The whole class of every A(B,B) that simulates its input
is divided into two sub-classes:
(a) A(B,B) that DOES NOT abort its simulation is incorrect
(ABOUT THIS ABORT DECISION)
because it would never halt and all deciders must always halt.
(b) A(B,N) that DOES abort its simulation is correct
(ABOUT THIS ABORT DECISION)
because it would halt and all deciders must always halt.
It would be correct if A would not halt. Only in that case B would not halt and an abort is needed. But not halting and aborting is not possible for the same A, so A is wrong, because it aborts prematurely.
Date | Sujet | # | | Auteur |
27 Mar 24 | No one can correctly refute that simulating abort decider A(D,D) is correct | 39 | | olcott |
27 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 38 | | Fred. Zwarts |
27 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 37 | | olcott |
28 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 36 | | Richard Damon |
28 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 35 | | olcott |
28 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 34 | | Richard Damon |
28 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 33 | | olcott |
28 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 32 | | Richard Damon |
28 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 31 | | olcott |
28 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 30 | | Richard Damon |
28 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 29 | | olcott |
28 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 28 | | Richard Damon |
28 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 27 | | olcott |
28 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 13 | | Fred. Zwarts |
28 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 12 | | olcott |
28 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 2 | | Fred. Zwarts |
28 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 1 | | olcott |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 9 | | Richard Damon |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 8 | | olcott |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 7 | | Richard Damon |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 6 | | olcott |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 5 | | Richard Damon |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 4 | | olcott |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 3 | | Richard Damon |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 2 | | olcott |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 1 | | Richard Damon |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 13 | | Richard Damon |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 12 | | olcott |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 11 | | Richard Damon |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 10 | | olcott |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 9 | | Richard Damon |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 8 | | olcott |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 7 | | Richard Damon |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 6 | | olcott |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 5 | | Richard Damon |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 4 | | olcott |
29 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 1 | | Richard Damon |
30 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 2 | | olcott |
30 Mar 24 | Re: No one can correctly refute that simulating abort decider A(D,D) is correct | 1 | | Richard Damon |