| olcott <NoOne@NoWhere.com>: Mar 09 05:03PM -0600 Eliminating pathological self-reference error from the halting problem The pathological self reference error occurs whenever a question or decision problem cannot be correctly answered because both of the yes/no or true/false answers are contradicted. If we ask Jack[1] this question: Will your answer to this question be no? Neither answer of yes or no is correct because they are both contradicted. When an input program is defined to do opposite of whatever the halt decider decides about its halt status then we have the same pathological self-reference error as Jack's question. If the halt decider Halts() returns a value of true to H_Hat() then H_Hat() would go into an infinite loop and never halt. If the halt decider Halts() returns a value of false to H_Hat() then H_Hat would immediately stop running. The simplest way to define a halt decider is to make a program that simply runs its input to see what it does. In technical terms this would be a universal Turing machine (UTM) that has been adapted to become a halt decider. This UTM would simply simulate the execution of its input until its input halts on its own or the halt decider determines that its input would never halt on its own and stops simulating it. In order for the UTM to see what its input does it must keep track of an execution trace of its input. Every (at least partial) halt decider that decides the halting status of its input on the basis of its examination of the execution trace of its own simulation of this input would correctly decide the conventional halting problem counter-examples as not halting. The x86utm operating system was created so that halt deciders written in the C programming language would be computationally equivalent to the execution of actual Turing machines. These (at least partial) halt deciders base their halting decision on examining the execution trace of the x86 machine language of their input. The input is the COFF object file output of a C compiler and is directly executed by the x86 emulator. The halt decider Halts() determines that H_Hat() called it in infinite recursion, on the basis of the x86 machine language execution trace shown below, stop simulating its input, and decide not halting on the basis that its input would not halt. void H_Hat(u32 P) { u32 Input_Would_Halt = Halts(P, P); if (Input_Would_Halt) HERE: goto HERE; } int main() { u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat); Output("Input_Would_Halt = ", Input_Would_Halt); } _H_Hat() [0000088f](01) 55 push ebp [00000890](02) 8bec mov ebp,esp [00000892](01) 51 push ecx [00000893](03) 8b4508 mov eax,[ebp+08] [00000896](01) 50 push eax [00000897](03) 8b4d08 mov ecx,[ebp+08] [0000089a](01) 51 push ecx [0000089b](05) e87ffeffff call 0000071f [000008a0](03) 83c408 add esp,+08 [000008a3](03) 8945fc mov [ebp-04],eax [000008a6](04) 837dfc00 cmp dword [ebp-04],+00 [000008aa](02) 7402 jz 000008ae [000008ac](02) ebfe jmp 000008ac [000008ae](02) 8be5 mov esp,ebp [000008b0](01) 5d pop ebp [000008b1](01) c3 ret _main() [000008bf](01) 55 push ebp [000008c0](02) 8bec mov ebp,esp [000008c2](01) 51 push ecx [000008c3](05) 688f080000 push 0000088f [000008c8](05) 688f080000 push 0000088f [000008cd](05) e84dfeffff call 0000071f [000008d2](03) 83c408 add esp,+08 [000008d5](03) 8945fc mov [ebp-04],eax [000008d8](03) 8b45fc mov eax,[ebp-04] [000008db](01) 50 push eax [000008dc](05) 680b030000 push 0000030b [000008e1](05) e869faffff call 0000034f [000008e6](03) 83c408 add esp,+08 [000008e9](02) 33c0 xor eax,eax [000008eb](02) 8be5 mov esp,ebp [000008ed](01) 5d pop ebp [000008ee](01) c3 ret Columns (1) Execution trace sequence number (2) Machine address of instruction (3) Machine address of top of stack (4) Value of top of stack after instruction executed (5) Number of bytes of machine code (6) Machine language bytes (7) Assembly language text (01)[000008bf][00011208][00000000](01) 55 push ebp (02)[000008c0][00011208][00000000](02) 8bec mov ebp,esp (03)[000008c2][00011204][00000000](01) 51 push ecx (04)[000008c3][00011200][0000088f](05) 688f080000 push 0000088f (05)[000008c8][000111fc][0000088f](05) 688f080000 push 0000088f (06)[000008cd][000111f8][000008d2](05) e84dfeffff call 0000071f (07)[0000088f][00031288][0003128c](01) 55 push ebp (08)[00000890][00031288][0003128c](02) 8bec mov ebp,esp (09)[00000892][00031284][00021258](01) 51 push ecx (10)[00000893][00031284][00021258](03) 8b4508 mov eax,[ebp+08] (11)[00000896][00031280][0000088f](01) 50 push eax (12)[00000897][00031280][0000088f](03) 8b4d08 mov ecx,[ebp+08] (13)[0000089a][0003127c][0000088f](01) 51 push ecx (14)[0000089b][00031278][000008a0](05) e87ffeffff call 0000071f Line(11) Push second parameter value: 0000088f to Halts() Line(13) Push first parameter value: 0000088f to Halts() Line(14) H_Halt() calls Halts(0000088f, 0000088f) (15)[0000088f][00042430][00042434](01) 55 push ebp (16)[00000890][00042430][00042434](02) 8bec mov ebp,esp (17)[00000892][0004242c][00032400](01) 51 push ecx (18)[00000893][0004242c][00032400](03) 8b4508 mov eax,[ebp+08] (19)[00000896][00042428][0000088f](01) 50 push eax (20)[00000897][00042428][0000088f](03) 8b4d08 mov ecx,[ebp+08] (21)[0000089a][00042424][0000088f](01) 51 push ecx (22)[0000089b][00042420][000008a0](05) e87ffeffff call 0000071f Line(19) Push second parameter value: 0000088f to Halts() Line(21) Push first parameter value: 0000088f to Halts() Line(22) H_Halt() calls Halts(0000088f, 0000088f) Infinite Recursion Detected Simulation Stopped on the basis that H_Hat() calls Halts() with the same data a second time in sequence from the same machine address. (23)[000008d2][00011204][00000000](03) 83c408 add esp,+08 (24)[000008d5][00011204][00000000](03) 8945fc mov [ebp-04],eax (25)[000008d8][00011204][00000000](03) 8b45fc mov eax,[ebp-04] (26)[000008db][00011200][00000000](01) 50 push eax (27)[000008dc][000111fc][0000030b](05) 680b030000 push 0000030b (28)[000008e1][000111f8][000008e6](05) e869faffff call 0000034f Input_Would_Halt = 0 (29)[000008e6][00011204][00000000](03) 83c408 add esp,+08 (30)[000008e9][00011204][00000000](02) 33c0 xor eax,eax (31)[000008eb][00011208][00000000](02) 8be5 mov esp,ebp (32)[000008ed][0001120c][00010000](01) 5d pop ebp (33)[000008ee][00011210][00000080](01) c3 ret Number_of_User_Instructions(33) Copyright 2021 PL Olcott [1] sci.logic --- Daryl McCullough --- Jun 25, 2004, 6:30:39 PM [The Psychology of Self-Reference] https://groups.google.com/g/sci.logic/c/4kIXI1kxmsI/m/hRroMoQZx2IJ http://www.liarparadox.org/Eliminating_pathological_self_reference_error_from_the_halting_problem.pdf -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| olcott <NoOne@NoWhere.com>: Mar 09 10:26AM -0600 On 3/9/2021 10:16 AM, R Kym Horsell wrote: > simulator. > Whether O has himself been in a loop on this problem the last few years > is the same as the HP and a meta joke. You can read the updated paper, I just added much more in depth analysis of exactly why the halting problem was previuosly considered unsolvable and why this never actually was the case. I provide an actual execution trace of fully operational code to prove my point. http://www.liarparadox.org/Eliminating_pathological_self_reference_error_from_the_halting_problem.pdf -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| olcott <NoOne@NoWhere.com>: Mar 09 11:54AM -0600 On 3/9/2021 11:35 AM, Kaz Kylheku wrote: > That is your problem. > When we say that a function "would" be something else, that is > precisely the same thing as "isn't". If X does not do Y then Z If X does do Y then not Z proving that not Z depends on X doing Y Think of the halt decider as a UTM that simply simulates its input until its input halts on its own or the halt decider determines that its input would never halt on its own thus stops simulating it. It cannot be answering the question: Does the input halt on its input? because both inputs that halt on their own and halt because the halt decider stops simulating them halt. When we remove the pathological self-reference error we correct this question so that it can discern the halting behavior of its inputs then the question becomes: Would the input program have infinite execution if the halt decider did not stop simulating it? -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| olcott <NoOne@NoWhere.com>: Mar 09 04:56PM -0600 Eliminating pathological self-reference error from the halting problem The pathological self reference error occurs whenever a question or decision problem cannot be correctly answered because both of the yes/no or true/false answers are contradicted. If we ask Jack[1] this question: Will your answer to this question be no? Neither answer of yes or no is correct because they are both contradicted. When an input program is defined to do opposite of whatever the halt decider decides about its halt status then we have the same pathological self-reference error as Jack's question. If the halt decider Halts() returns a value of true to H_Hat() then H_Hat() would go into an infinite loop and never halt. If the halt decider Halts() returns a value of false to H_Hat() then H_Hat would immediately stop running. The simplest way to define a halt decider is to make a program that simply runs its input to see what it does. In technical terms this would be a universal Turing machine (UTM) that has been adapted to become a halt decider. This UTM would simply simulate the execution of its input until its input halts on its own or the halt decider determines that its input would never halt on its own and stops simulating it. In order for the UTM to see what its input does it must keep track of an execution trace of its input. Every (at least partial) halt decider that decides the halting status of its input on the basis of its examination of the execution trace of its own simulation of this input would correctly decide the conventional halting problem counter-examples as not halting. The x86utm operating system was created so that halt deciders written in the C programming language would be computationally equivalent to the execution of actual Turing machines. These (at least partial) halt deciders base their halting decision on examining the execution trace of the x86 machine language of their input. The input is the COFF object file output of a C compiler and is directly executed by the x86 emulator. The halt decider Halts() determines that H_Hat() called it in infinite recursion, on the basis of the x86 machine language execution trace shown below, stop simulating its input, and decide not halting on the basis that its input would not halt. void H_Hat(u32 P) { u32 Input_Would_Halt = Halts(P, P); if (Input_Would_Halt) HERE: goto HERE; } int main() { u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat); Output("Input_Would_Halt = ", Input_Would_Halt); } _H_Hat() [0000088f](01) 55 push ebp [00000890](02) 8bec mov ebp,esp [00000892](01) 51 push ecx [00000893](03) 8b4508 mov eax,[ebp+08] [00000896](01) 50 push eax [00000897](03) 8b4d08 mov ecx,[ebp+08] [0000089a](01) 51 push ecx [0000089b](05) e87ffeffff call 0000071f [000008a0](03) 83c408 add esp,+08 [000008a3](03) 8945fc mov [ebp-04],eax [000008a6](04) 837dfc00 cmp dword [ebp-04],+00 [000008aa](02) 7402 jz 000008ae [000008ac](02) ebfe jmp 000008ac [000008ae](02) 8be5 mov esp,ebp [000008b0](01) 5d pop ebp [000008b1](01) c3 ret _main() [000008bf](01) 55 push ebp [000008c0](02) 8bec mov ebp,esp [000008c2](01) 51 push ecx [000008c3](05) 688f080000 push 0000088f [000008c8](05) 688f080000 push 0000088f [000008cd](05) e84dfeffff call 0000071f [000008d2](03) 83c408 add esp,+08 [000008d5](03) 8945fc mov [ebp-04],eax [000008d8](03) 8b45fc mov eax,[ebp-04] [000008db](01) 50 push eax [000008dc](05) 680b030000 push 0000030b [000008e1](05) e869faffff call 0000034f [000008e6](03) 83c408 add esp,+08 [000008e9](02) 33c0 xor eax,eax [000008eb](02) 8be5 mov esp,ebp [000008ed](01) 5d pop ebp [000008ee](01) c3 ret Columns (1) Execution trace sequence number (2) Machine address of instruction (3) Machine address of top of stack (4) Value of top of stack after instruction executed (5) Number of bytes of machine code (6) Machine language bytes (7) Assembly language text (01)[000008bf][00011208][00000000](01) 55 push ebp (02)[000008c0][00011208][00000000](02) 8bec mov ebp,esp (03)[000008c2][00011204][00000000](01) 51 push ecx (04)[000008c3][00011200][0000088f](05) 688f080000 push 0000088f (05)[000008c8][000111fc][0000088f](05) 688f080000 push 0000088f (06)[000008cd][000111f8][000008d2](05) e84dfeffff call 0000071f (07)[0000088f][00031288][0003128c](01) 55 push ebp (08)[00000890][00031288][0003128c](02) 8bec mov ebp,esp (09)[00000892][00031284][00021258](01) 51 push ecx (10)[00000893][00031284][00021258](03) 8b4508 mov eax,[ebp+08] (11)[00000896][00031280][0000088f](01) 50 push eax (12)[00000897][00031280][0000088f](03) 8b4d08 mov ecx,[ebp+08] (13)[0000089a][0003127c][0000088f](01) 51 push ecx (14)[0000089b][00031278][000008a0](05) e87ffeffff call 0000071f Line(11) Push second parameter value: 0000088f to Halts() Line(13) Push first parameter value: 0000088f to Halts() Line(14) H_Halt() calls Halts(0000088f, 0000088f) (15)[0000088f][00042430][00042434](01) 55 push ebp (16)[00000890][00042430][00042434](02) 8bec mov ebp,esp (17)[00000892][0004242c][00032400](01) 51 push ecx (18)[00000893][0004242c][00032400](03) 8b4508 mov eax,[ebp+08] (19)[00000896][00042428][0000088f](01) 50 push eax (20)[00000897][00042428][0000088f](03) 8b4d08 mov ecx,[ebp+08] (21)[0000089a][00042424][0000088f](01) 51 push ecx (22)[0000089b][00042420][000008a0](05) e87ffeffff call 0000071f Line(19) Push second parameter value: 0000088f to Halts() Line(21) Push first parameter value: 0000088f to Halts() Line(22) H_Halt() calls Halts(0000088f, 0000088f) Infinite Recursion Detected Simulation Stopped on the basis that H_Hat() calls Halts() with the same data a second time in sequence from the same machine address. (23)[000008d2][00011204][00000000](03) 83c408 add esp,+08 (24)[000008d5][00011204][00000000](03) 8945fc mov [ebp-04],eax (25)[000008d8][00011204][00000000](03) 8b45fc mov eax,[ebp-04] (26)[000008db][00011200][00000000](01) 50 push eax (27)[000008dc][000111fc][0000030b](05) 680b030000 push 0000030b (28)[000008e1][000111f8][000008e6](05) e869faffff call 0000034f Input_Would_Halt = 0 (29)[000008e6][00011204][00000000](03) 83c408 add esp,+08 (30)[000008e9][00011204][00000000](02) 33c0 xor eax,eax (31)[000008eb][00011208][00000000](02) 8be5 mov esp,ebp (32)[000008ed][0001120c][00010000](01) 5d pop ebp (33)[000008ee][00011210][00000080](01) c3 ret Number_of_User_Instructions(33) Copyright 2021 PL Olcott [1] sci.logic --- Daryl McCullough --- Jun 25, 2004, 6:30:39 PM [The Psychology of Self-Reference] https://groups.google.com/g/sci.logic/c/4kIXI1kxmsI/m/hRroMoQZx2IJ http://www.liarparadox.org/Eliminating_pathological_self_reference_error_from_the_halting_problem.pdf -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment