On 7/30/2021 9:09 AM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
>
> I have trivial implementations of the functions you are hiding that give
> exactly those results. I don't think I've "defeated Rice" but perhaps
> you should worry that someone else will come up with the H and H2 I have
> and publish first!
>

Yet those trivial implementations do not have complete execution traces
showing that a partial halt decider does correctly decide the halt
status of its input.

int Simulate(u32 P, u32 I)
{ ((int(*)(int))P)(I);
return 1;
}

// H and H2 are partial halt deciders
u32 PSR_Decider(u32 P, u32 I)
{ u32 Input_Halts1 = H((u32)P, (u32)I);
u32 Input_Halts2 = H2((u32)Simulate, (u32)P, (u32)I);
Output("Input_Halts1 = ", Input_Halts1);
Output("Input_Halts2 = ", Input_Halts2);
if (Input_Halts1 != Input_Halts2)
return 1;
return 0;
}

void P(u32 x)
{ if (H(x, x))
HERE: goto HERE;
}

int main()
{ Output("PSR_Decider = ", PSR_Decider((u32)P, (u32)P));
}

_Simulate()
[00000c22](01) 55 push ebp
[00000c23](02) 8bec mov ebp,esp
[00000c25](03) 8b450c mov eax,[ebp+0c]
[00000c28](01) 50 push eax
[00000c29](03) ff5508 call dword [ebp+08]
[00000c2c](03) 83c404 add esp,+04
[00000c2f](05) b801000000 mov eax,00000001
[00000c34](01) 5d pop ebp
[00000c35](01) c3 ret
Size in bytes:(0020) [00000c35]

_PSR_Decider()
[00000c42](01) 55 push ebp
[00000c43](02) 8bec mov ebp,esp
[00000c45](03) 83ec08 sub esp,+08
[00000c48](03) 8b450c mov eax,[ebp+0c]
[00000c4b](01) 50 push eax
[00000c4c](03) 8b4d08 mov ecx,[ebp+08]
[00000c4f](01) 51 push ecx
[00000c50](05) e86dfeffff call 00000ac2 // call H
[00000c55](03) 83c408 add esp,+08
[00000c58](03) 8945fc mov [ebp-04],eax
[00000c5b](03) 8b550c mov edx,[ebp+0c]
[00000c5e](01) 52 push edx
[00000c5f](03) 8b4508 mov eax,[ebp+08]
[00000c62](01) 50 push eax
[00000c63](05) 68220c0000 push 00000c22
[00000c68](05) e875fdffff call 000009e2 // call H2
[00000c6d](03) 83c40c add esp,+0c
[00000c70](03) 8945f8 mov [ebp-08],eax
[00000c73](03) 8b4dfc mov ecx,[ebp-04]
[00000c76](01) 51 push ecx
[00000c77](05) 6823030000 push 00000323
[00000c7c](05) e8f1f6ffff call 00000372
[00000c81](03) 83c408 add esp,+08
[00000c84](03) 8b55f8 mov edx,[ebp-08]
[00000c87](01) 52 push edx
[00000c88](05) 6833030000 push 00000333
[00000c8d](05) e8e0f6ffff call 00000372
[00000c92](03) 83c408 add esp,+08
[00000c95](03) 8b45fc mov eax,[ebp-04]
[00000c98](03) 3b45f8 cmp eax,[ebp-08]
[00000c9b](02) 7407 jz 00000ca4
[00000c9d](05) b801000000 mov eax,00000001
[00000ca2](02) eb02 jmp 00000ca6
[00000ca4](02) 33c0 xor eax,eax
[00000ca6](02) 8be5 mov esp,ebp
[00000ca8](01) 5d pop ebp
[00000ca9](01) c3 ret
Size in bytes:(0104) [00000ca9]

_P()
[00000cb2](01) 55 push ebp
[00000cb3](02) 8bec mov ebp,esp
[00000cb5](03) 8b4508 mov eax,[ebp+08]
[00000cb8](01) 50 push eax
[00000cb9](03) 8b4d08 mov ecx,[ebp+08]
[00000cbc](01) 51 push ecx
[00000cbd](05) e800feffff call 00000ac2
[00000cc2](03) 83c408 add esp,+08
[00000cc5](02) 85c0 test eax,eax
[00000cc7](02) 7402 jz 00000ccb
[00000cc9](02) ebfe jmp 00000cc9
[00000ccb](01) 5d pop ebp
[00000ccc](01) c3 ret
Size in bytes:(0027) [00000ccc]

_main()
[00000cd2](01) 55 push ebp
[00000cd3](02) 8bec mov ebp,esp
[00000cd5](05) 68b20c0000 push 00000cb2
[00000cda](05) 68b20c0000 push 00000cb2
[00000cdf](05) e85effffff call 00000c42
[00000ce4](03) 83c408 add esp,+08
[00000ce7](01) 50 push eax
[00000ce8](05) 6843030000 push 00000343
[00000ced](05) e880f6ffff call 00000372
[00000cf2](03) 83c408 add esp,+08
[00000cf5](02) 33c0 xor eax,eax
[00000cf7](01) 5d pop ebp
[00000cf8](01) c3 ret
Size in bytes:(0039) [00000cf8]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
....[00000cd2][001017ed][00000000] 55 push ebp
....[00000cd3][001017ed][00000000] 8bec mov ebp,esp
....[00000cd5][001017e9][00000cb2] 68b20c0000 push 00000cb2
....[00000cda][001017e5][00000cb2] 68b20c0000 push 00000cb2
....[00000cdf][001017e1][00000ce4] e85effffff call 00000c42
....[00000c42][001017dd][001017ed] 55 push ebp
....[00000c43][001017dd][001017ed] 8bec mov ebp,esp
....[00000c45][001017d5][90909090] 83ec08 sub esp,+08
....[00000c48][001017d5][90909090] 8b450c mov eax,[ebp+0c]
....[00000c4b][001017d1][00000cb2] 50 push eax // push P
....[00000c4c][001017d1][00000cb2] 8b4d08 mov ecx,[ebp+08]
....[00000c4f][001017cd][00000cb2] 51 push ecx // push P
....[00000c50][001017c9][00000c55] e86dfeffff call 00000ac2 // H(P,P)

Begin Local Halt Decider Simulation at Machine Address:cb2
....[00000cb2][0021188d][00211891] 55 push ebp
....[00000cb3][0021188d][00211891] 8bec mov ebp,esp
....[00000cb5][0021188d][00211891] 8b4508 mov eax,[ebp+08]
....[00000cb8][00211889][00000cb2] 50 push eax
....[00000cb9][00211889][00000cb2] 8b4d08 mov ecx,[ebp+08]
....[00000cbc][00211885][00000cb2] 51 push ecx
....[00000cbd][00211881][00000cc2] e800feffff call 00000ac2
....[00000cb2][0025c2b5][0025c2b9] 55 push ebp
....[00000cb3][0025c2b5][0025c2b9] 8bec mov ebp,esp
....[00000cb5][0025c2b5][0025c2b9] 8b4508 mov eax,[ebp+08]
....[00000cb8][0025c2b1][00000cb2] 50 push eax
....[00000cb9][0025c2b1][00000cb2] 8b4d08 mov ecx,[ebp+08]
....[00000cbc][0025c2ad][00000cb2] 51 push ecx
....[00000cbd][0025c2a9][00000cc2] e800feffff call 00000ac2
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

....[00000c55][001017d5][90909090] 83c408 add esp,+08
....[00000c58][001017d5][90909090] 8945fc mov [ebp-04],eax
....[00000c5b][001017d5][90909090] 8b550c mov edx,[ebp+0c]
....[00000c5e][001017d1][00000cb2] 52 push edx // push P
....[00000c5f][001017d1][00000cb2] 8b4508 mov eax,[ebp+08]
....[00000c62][001017cd][00000cb2] 50 push eax // push P
....[00000c63][001017c9][00000c22] 68220c0000 push 00000c22 // push Simulate
....[00000c68][001017c5][00000c6d] e875fdffff call 000009e2 //
H2(Simulate,P,P)

Begin Local Halt Decider Simulation at Machine Address:c22
....[00000c22][0026c351][0026c355] 55 push ebp
....[00000c23][0026c351][0026c355] 8bec mov ebp,esp
....[00000c25][0026c351][0026c355] 8b450c mov eax,[ebp+0c]
....[00000c28][0026c34d][00000cb2] 50 push eax
Calling:_P()
Decode_Control_Flow_Instruction([00000008][0026c351][00000cb2])
....[00000c29][0026c349][00000c2c] ff5508 call dword [ebp+08]
Decode_Control_Flow_Instruction([00000008][00101771][001017bd])
....[00000cb2][0026c345][0026c351] 55 push ebp
....[00000cb3][0026c345][0026c351] 8bec mov ebp,esp
....[00000cb5][0026c345][0026c351] 8b4508 mov eax,[ebp+08]
....[00000cb8][0026c341][00000cb2] 50 push eax
....[00000cb9][0026c341][00000cb2] 8b4d08 mov ecx,[ebp+08]
....[00000cbc][0026c33d][00000cb2] 51 push ecx
....[00000cbd][0026c339][00000cc2] e800feffff call 00000ac2

Begin Local Halt Decider Simulation at Machine Address:cb2
....[00000cb2][002b6d7d][002b6d81] 55 push ebp
....[00000cb3][002b6d7d][002b6d81] 8bec mov ebp,esp
....[00000cb5][002b6d7d][002b6d81] 8b4508 mov eax,[ebp+08]
....[00000cb8][002b6d79][00000cb2] 50 push eax
....[00000cb9][002b6d79][00000cb2] 8b4d08 mov ecx,[ebp+08]
....[00000cbc][002b6d75][00000cb2] 51 push ecx
....[00000cbd][002b6d71][00000cc2] e800feffff call 00000ac2
....[00000cb2][003017a5][003017a9] 55 push ebp
....[00000cb3][003017a5][003017a9] 8bec mov ebp,esp
....[00000cb5][003017a5][003017a9] 8b4508 mov eax,[ebp+08]
....[00000cb8][003017a1][00000cb2] 50 push eax
....[00000cb9][003017a1][00000cb2] 8b4d08 mov ecx,[ebp+08]
....[00000cbc][0030179d][00000cb2] 51 push ecx
....[00000cbd][00301799][00000cc2] e800feffff call 00000ac2
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

....[00000cc2][0026c345][0026c351] 83c408 add esp,+08
....[00000cc5][0026c345][0026c351] 85c0 test eax,eax
....[00000cc7][0026c345][0026c351] 7402 jz 00000ccb
....[00000ccb][0026c349][00000c2c] 5d pop ebp
....[00000ccc][0026c34d][00000cb2] c3 ret
....[00000c2c][0026c351][0026c355] 83c404 add esp,+04
....[00000c2f][0026c351][0026c355] b801000000 mov eax,00000001
....[00000c34][0026c355][00000aa3] 5d pop ebp
....[00000c35][0026c359][00000cb2] c3 ret
....[00000c6d][001017d5][90909090] 83c40c add esp,+0c
....[00000c70][001017d5][00000001] 8945f8 mov [ebp-08],eax
....[00000c73][001017d5][00000001] 8b4dfc mov ecx,[ebp-04]
....[00000c76][001017d1][00000000] 51 push ecx
....[00000c77][001017cd][00000323] 6823030000 push 00000323
---[00000c7c][001017cd][00000323] e8f1f6ffff call 00000372
Input_Halts1 = 0
....[00000c81][001017d5][00000001] 83c408 add esp,+08
....[00000c84][001017d5][00000001] 8b55f8 mov edx,[ebp-08]
....[00000c87][001017d1][00000001] 52 push edx
....[00000c88][001017cd][00000333] 6833030000 push 00000333
---[00000c8d][001017cd][00000333] e8e0f6ffff call 00000372
Input_Halts2 = 1
....[00000c92][001017d5][00000001] 83c408 add esp,+08
....[00000c95][001017d5][00000001] 8b45fc mov eax,[ebp-04]
....[00000c98][001017d5][00000001] 3b45f8 cmp eax,[ebp-08]
....[00000c9b][001017d5][00000001] 7407 jz 00000ca4
....[00000c9d][001017d5][00000001] b801000000 mov eax,00000001
....[00000ca2][001017d5][00000001] eb02 jmp 00000ca6
....[00000ca6][001017dd][001017ed] 8be5 mov esp,ebp
....[00000ca8][001017e1][00000ce4] 5d pop ebp
....[00000ca9][001017e5][00000cb2] c3 ret
....[00000ce4][001017ed][00000000] 83c408 add esp,+08
....[00000ce7][001017e9][00000001] 50 push eax
....[00000ce8][001017e5][00000343] 6843030000 push 00000343
---[00000ced][001017e5][00000343] e880f6ffff call 00000372
PSR_Decider = 1
....[00000cf2][001017ed][00000000] 83c408 add esp,+08
....[00000cf5][001017ed][00000000] 33c0 xor eax,eax
....[00000cf7][001017f1][00100000] 5d pop ebp
....[00000cf8][001017f5][00000184] c3 ret
Number_of_User_Instructions(98)
Number of Instructions Executed(652216)

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein