XPost: comp.lang.c
Op 25.mei.2024 om 13:22 schreef olcott:
On 5/25/2024 2:32 AM, Fred. Zwarts wrote:
Op 23.mei.2024 om 18:52 schreef olcott:
typedef int (*ptr)(); // ptr is pointer to int function in C
00 int H(ptr p, ptr i);
01 int D(ptr p)
02 {
03 int Halt_Status = H(p, p);
04 if (Halt_Status)
05 HERE: goto HERE;
06 return Halt_Status;
07 }
08
09 int main()
10 {
11 H(D,D);
12 return 0;
13 }
The above template refers to an infinite set of H/D pairs where D is
correctly simulated by pure function H. This was done because many
reviewers used the shell game ploy to endlessly switch which H/D was
being referred to.
*Correct Simulation Defined*
This is provided because every reviewer had a different notion of
correct simulation that diverges from this notion.
In the above case a simulator is an x86 emulator that correctly emulates >>> at least one of the x86 instructions of D in the order specified by the
x86 instructions of D.
This may include correctly emulating the x86 instructions of H in the
order specified by the x86 instructions of H thus calling H(D,D) in
recursive simulation.
*Execution Trace*
Line 11: main() invokes H(D,D); H(D,D) simulates lines 01, 02, and 03 of >>> D. This invokes H(D,D) again to repeat the process in endless recursive
simulation.
Olcott's own words are that the simulation of D never reaches past
line 03. So the lines following line 03 do not play a role and,
therefore, can be removed without changing the claim. This leads to:
typedef int (*ptr)(); // ptr is pointer to int function in C
00 int H(ptr p, ptr i);
01 int D(ptr p)
02 {
03 return H(p, p);
04 }
05
06 int main()
07 {
08 H(D,D);
09 return 0;
10 }
What we see is that the only property of D that is used is that it is
a parameter duplicator. (Is that why it is called D?). H needs 2
parameters, but it can be given only one input parameter, so the
parameter duplicator is required to allow H to decide about itself.
Of the infinite set of H that simulate at least one step, none of
them, when simulated by H, halts, because none of them reaches its
final state. Olcott's claim is equivalent to the claim of non-halting
behaviour of H.
This means that a simulating halt-decider is a bad idea, because the
decider itself does not halt.
The simplification is valid.
01 int D(ptr p)
02 {
03 H(p, p);
04 return 0;
05 }
This is a better simplification because it now has an actual
identifiable final state that can be separately referred to.
It is not true that H never halts. H is required to be a pure
function. https://en.wikipedia.org/wiki/Pure_function
If H finds that H never halts and a non-halting H is not allowed, that
it is clear that the set of H that satisfy the requirements is empty.
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)