Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ]

0 views
Skip to first unread message

olcott

unread,
Jul 30, 2021, 9:46:58 AMJul 30
to
int Factorial(int n)
{
Output("Factorial(n)",n);
if (n > 1)
return n * Factorial(n - 1);
else
return 1;
}

void Infinite_Recursion(u32 N)
{
Infinite_Recursion(N);
}

void Infinite_Loop()
{
HERE: goto HERE;
}

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));
Output("PSR_Decider = ", PSR_Decider((u32)Factorial, 3));
Output("PSR_Decider = ", PSR_Decider((u32)Infinite_Recursion, 3));
Output("PSR_Decider = ", PSR_Decider((u32)Infinite_Loop,
(u32)Infinite_Loop));
}

Here are the return values proving that Rice has been defeated:
PSR_Decider((u32)P, (u32)P)==1
PSR_Decider((u32)Factorial, 3)==0
PSR_Decider((u32)Infinite_Recursion, 3)==0
PSR_Decider((u32)Infinite_Loop, (u32)Infinite_Loop)==0



--
Copyright 2021 Pete Olcott

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

olcott

unread,
Jul 30, 2021, 11:41:02 AMJul 30
to
On 7/30/2021 9:09 AM, Ben Bacarisse wrote:
> olcott <No...@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)

olcott

unread,
Jul 30, 2021, 2:45:30 PMJul 30
to
On 7/30/2021 1:27 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 7/30/2021 9:09 AM, Ben Bacarisse wrote:
>>> olcott <No...@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.
>
> My point was that what you posted proves nothing. You need to post code
> and then prove that it decides a "non-trivial" property of Turing
> machines.
>

In prior conversations long ago it has been established that dividing
inputs having pathological self-reference(Olcott 2004) from ones that do
not does refute Rice's theorem.

A very careful study on the x86 assembly language execution trace does
prove that H/H2 does decide its inputs correctly. On the basis of
knowing that H/H2 does decide its inputs correctly there is no need to
see the H/H2 code.

>> machine stack stack machine assembly
>> address address data code language
>> ======== ======== ======== ========= =============
>> ...[00000cd2][001017ed][00000000] 55 push ebp
>
> No execution trace can prove what you claimed either. If you want to
> know why, just ask. I think you need to learn Rice's theorem all over
> again.
>

Why do you believe that an execution trace does not prove that H/H2 did
decide their inputs correctly?

olcott

unread,
Jul 30, 2021, 5:44:03 PMJul 30
to
On 7/30/2021 3:47 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 7/30/2021 1:27 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 7/30/2021 9:09 AM, Ben Bacarisse wrote:
>>>>> olcott <No...@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.
>>> My point was that what you posted proves nothing. You need to post code
>>> and then prove that it decides a "non-trivial" property of Turing
>>> machines.
>>
>> In prior conversations long ago it has been established that dividing
>> inputs having pathological self-reference(Olcott 2004) from ones that
>> do not does refute Rice's theorem.
>
> Then go ahead and post the code and the proof that it decides a
> non-trivial property of computations (note the plural).
>
>> A very careful study on the x86 assembly language execution trace does
>> prove that H/H2 does decide its inputs correctly.
>
> A trace of some code correctly deciding some non-trivial property of
> some other code does not refute Rice's theorem. You need to lean the
> theorem.
>

Yes the claim is that it cannot always do this correctly because a
counter-example exists that it cannot decide. I propose that those
counter-examples will not make pathological self-reference(Olcott 2004)
undecidable for my code.

>>>> machine stack stack machine assembly
>>>> address address data code language
>>>> ======== ======== ======== ========= =============
>>>> ...[00000cd2][001017ed][00000000] 55 push ebp
>>> No execution trace can prove what you claimed either. If you want to
>>> know why, just ask. I think you need to learn Rice's theorem all over
>>> again.
>>
>> Why do you believe that an execution trace does not prove that H/H2
>> did decide their inputs correctly?
>
> It does not matter what the trace shows. The trace can show some code
> deciding absolutely anything, either correctly or incorrectly, and still
> not refute Rice's theorem. Rice's theorem is about the decidability of
> sets.
>

If there exists no undecidable counter-example showing the Rice's
theorem is true then it would seem that Rice's theorem would have no basis.

olcott

unread,
Jul 30, 2021, 5:53:26 PMJul 30
to
On 7/30/2021 4:46 PM, André G. Isaak wrote:
> On 2021-07-30 11:11, olcott wrote:
>> On 7/30/2021 12:06 PM, André G. Isaak wrote:
>>> On 2021-07-30 07:46, olcott wrote:
>>>
>>>> int Simulate(u32 P, u32 I)
>>>> {
>>>>    ((int(*)(int))P)(I);
>>>>    return 1;
>>>> }
>>>
>>> Why is this function called 'Simulate'?
>>>
>>> There's nothing remotely resembling simulation going on there. The
>>> function is simply calling the function pointer that was passed to
>>> it. That's execution, not simulation.
>>>
>>
>> It is the simplest possible function that is computationally
>> equivalent to a simulation. Since every single instruction of the
>> entire x86utm operating system is simulated the name is also literally
>> true.
>
> Well, no, it isn't. The name 'simulator' suggests that this function
> performs simulation. From what you suggest above, 'simulator' is,
> itself, being simulated. That's something altogether different which
> makes the name incredibly misleading.
>

Then think of it as being named Big_Freds_Pizza(), the point is that my
code seems to defeat Rice.

Didn't you make a claim that you could fool it?

>>> Which raises all sorts of questions regarding your previous usage of
>>> the term 'simulate'. Does your 'simulating decider' actually involve
>>> simulation at all?
>>>
>>> André
>>>
>>>
>>
>> The x86utm operating system is based on an x86 emulator that has
>> decades of development.
>
> That doesn't answer my question at all (and I don't know why you think
> anyone cares how many decades something has been under development).
>
> You consistently referred to your H as a 'simulating halt decider', but
> every time you present code snippets of H it shows H making a direct
> call to its input rather than invoking any kind of simulator.
>
> So is H actually the thing doing the simulation, or is H simply *being*
> simulated in much the same way as your so-called 'Simulate' function
> above is?
>
> André
>

Why can't you seem to stay focused on the key point at hand?
Why do you diverge off on inconsequential trivialities?

If you think that you can fool my Pathological self-reference(Olcott
2004) decider go ahead any try this. If it is impossible to fool it then
that proves that it is correct.

olcott

unread,
Jul 30, 2021, 7:44:17 PMJul 30
to
On 7/30/2021 6:32 PM, Malcolm McLean wrote:
> On Friday, 30 July 2021 at 23:45:39 UTC+1, olcott wrote:
>>
>> The P of int main(){ P(P); } reaches its final state.
>> The input to H(P,P) cannot possibly reach its final state.
>> PSR_Decider() sees this difference.
>> PSR_Decider() detects that inputs have the Pathological
>> Self-reference(Olcott 2004) property.
>>
> So we have two halt deciders, H1 and H2.
> H1 is confounded by H1_Hat, H2 is confounded by H2_Hat.

No in both cases the input is the same. The only difference is that H2
is at a different point in the execution trace than H.

// this one corresponds to the point where H(P,P) evaluates its input
u32 Input_Halts1 = H((u32)P, (u32)P);

// this one corresponds to the point before H(P,P) evaluates its input
u32 Input_Halts2 = H2((u32)Simulate, (u32)P, (u32)P);

> However H1 classifies H2_Hat correctly, and H2 classifies H1_Hat
> correctly.
> So at first sight this seems promising. We can run H1 and H2 on the
> same input, see if they match, and if there is a disgreement, detect
> pathological self reference.
>
> The snag is that you've got to show that "pathological self reference"
> is the only input that confounds your two deciders.
>

I tested this, it is the case.
Both halting and non halting cases return 0.

olcott

unread,
Jul 30, 2021, 10:33:21 PMJul 30
to
On 7/30/2021 9:05 PM, André G. Isaak wrote:
> On 2021-07-30 17:34, olcott wrote:
>> On 7/30/2021 6:01 PM, André G. Isaak wrote:
>>> On 2021-07-30 16:43, olcott wrote:
>>>> On 7/30/2021 5:13 PM, André G. Isaak wrote:
>>>>> Because it *isn't* an inconsequential triviality. I'm trying to
>>>>> figure out the actual architecture of your system, and you are
>>>>> being deliberately unhelpful.
>>>>>
>>>>> Just because you don't understand why a particular question is
>>>>> being asked isn't a good reason to refuse to answer it.
>>>>
>>>> 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));
>>>> }
>>>>
>>>> The point of this post is whether or not my PSR_Decider() is correct.
>>>> The name that I choose for my functions is not related to that.
>>>
>>> I'm not asking about the name. I'm asking whether your "simulating
>>> halt decider" H actually performs any simulation or whether it is
>>> simply being simulated as you claim that 'Simulate' above is.
>>>
>>> And once again you've failed to answer. It's a simple straightforward
>>> question. It can be answered in a single short sentence. So why not
>>> simply answer it rather than coming up with excuses for not answering
>>> it?
>>>
>>
>> I have aready answered this many hundreds of times, asking the same
>> quesition again seems quite disingenuous. Here is an additional detail
>> that I have only provided about a dozen times:
>>
>> This is *how* H simulates its slave process one x86 instruction
>> at-a-time.
>>
>> u32  DebugStep(Registers* master_state,
>>                 Registers* slave_state,
>>                 Decoded_Line_Of_Code* decoded) {}
>>
>> master_state has the machine register values of H and slave_state has
>> the machine register values of P. decoded has the simplified machine
>> code that was executed.
>
> That doesn't answer my question, though. I am interested in *where* the
> simulation actually takes place. Does H actually initialize the
> simulation

Yes

> and set up these state records, or is this something done by
> your "operating system".
>
> When you call H(P, P) does the copy of H inside P set up a second set of
> register state records and initialize a new simulation or not?
>

It is more accurately a copy of P inside of H. H creates a whole process
context including stack, and registers for each virtual machine that it
simulates.

> Also, why would a simulation of P require *two* sets of register states?
> It should only require the state of the machine being simulated.
>

An operating system function switches to the process context of the
slave, executes one instruction then switches back to the master.

>>>>> I can guarantee you that if you ever present your work in a *real*
>>>>> academic environment, you will be asked all sorts of questions of
>>>>> which you might not immediately see the relevance, and you *will*
>>>>> be expected to answer them.
>>>>>
>>>>>> If you think that you can fool my Pathological
>>>>>> self-reference(Olcott 2004) decider go ahead any try this. If it
>>>>>> is impossible to fool it then that proves that it is correct.
>>>>>
>>>>> How can anyone possible answer this?
>>>>>
>>>>> You've apparently now got two different halt decider, H1 and H2.
>>>>> You haven't provided even the vaguest description of what these
>>>>> things do or how they differ from one another.
>>>>>
>>>>
>>>> So before you ever read what I say you first make sure to forget
>>>> everything else that we have discussed.
>>>>
>>>> The P of int main(){ P(P); } reaches its final state.
>>>> The input to H(P,P) cannot possibly reach its final state.
>>>> PSR_Decider() sees this difference.
>>>
>>> So why are you using a different halt decider for each case? What's
>>> the different between H1 and H2? And why do you need Simulate at all?
>>> Why not just call H2(P, P) given that your 'simulate' is no more than
>>> a wrapper for a function call.
>>>
>>
>> H2 take three params so that it can execute the equivalent of
>> int main(){ P(P); }
>
> P(P) is already the equivalent of int main() { P(P); }.
>

Yet we need to see what int main(){ P(P); } does and we can't do that
without a global halt decider so I derived the computational equivalent
using local functions.

> So H2(Simulate, P, P)
>
> should return the exact same answer as
>
> H1(P, P)
>
> given that 'Simulate' is just a wrapper for P(P).
>

No the reason that they give different results is that
H2 is at a different point in the execution trace than H.

// this one corresponds to the point where H(P,P) evaluates its input
u32 Input_Halts1 = H((u32)P, (u32)P);

// this one corresponds to the point before H(P,P) evaluates its input
u32 Input_Halts2 = H2((u32)Simulate, (u32)P, (u32)P);

It has never been the case that one is correct and the other is wrong.

It has always been the case that the correct answer depends on where the
question is asked.


>>> How is it that H2 *correctly* determines that P(P) does halt
>>
>> P reaches its final state.
>
> But how exactly is it that H2 gets this answer right when H1 gets the
> answer wrong?
>

Both answers are correct at the point in the execution trace where they
are asked.

>>> (or that Simulate(P, P) doesn't halt)
>>
>> Simulate does halt.
>
> Yes. That was a typo. I already corrected it.
>
>>> whereas H1 incorrectly claims that P(P) doesn't halt?
>>
>> H1 correctly determines that its input cannot possibly ever halt
>> unless H1 aborts its simulation of P, thus perfectly matching the
>> never halts criteria.
> >
>> int main(){ P(P); } does halt.
>
> Yes. I get that. What I don't get is how your H2 manages to correctly
> determine this if it is using the same broken halting criteria as H1.
>

It is correct halting criteria. Both H and H2 are correct at the point
in the execution trace where they are asked.

It is true that the input to H(P,P) cannot possibly and never does reach
its final state. It is also true that when P(P) is invoked separately
that P does reach its final state. The different points in the execution
trace derive different correct answers.

When we ask whether or not Bill is a criminal we cannot correctly answer
this question on the basis of the behavior of his twin brother.

> In both cases you have P(P) appearing as an input to your halt decider
> rather than as an independent computation.
>
> André

olcott

unread,
Jul 31, 2021, 10:34:43 PMJul 31
to
> There is no such thing as an undecidable example (singular). But I
> think you now agree with me: nothing you have posted says anything about
> the soundness of the theorem. The "if ... then it would seem..."
> pattern suggest you know you haven't proved anything.
>


// Simplified Linz Ĥ (Linz:1990:319)
// Strachey(1965) CPL translated to C
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}

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

I call the above an HP counter example instance.

I thought that André claimed that he had such a counter-example for my
PSR_Decider().

> I won't even try to understand what a "counter-example showing the
> Rice's theorem is true" is. If you read a book on this topic (properly,
> not just scanning it), you'd pick the language and might end up knowing
> how to say what you mean.
>

Try an find a case where my PSR_Decider() can't possibly get the correct
answer.

> I've accused you before of writing "math poems" when you try to use
> symbolic notation, but I've just realised you do it with words as well.
> You don't really know what "decidable", "counter-example" and "Rice's
> theorem" mean.

I have shown this concretely.

> You don't even know what mathematicians mean by "true",

They have since Tarski added the whole convoluted mess of model theory
on top of Tarski's original simple notion.

> so when you string them all together like this, the reader has to
> analyse the poem to see how you are using these words as metaphors. If
> the reader can do that, they will know what you mean.
>

I asked you for the proper terminology for the HP counter-example
instance that I provided above and you indicated that there is none. You
said it is simply called the inputs that H gets wrong. Objectively this
is not a very good formal name.

olcott

unread,
Aug 2, 2021, 2:38:07 PMAug 2
to
On 8/2/2021 11:32 AM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 8/1/2021 5:22 AM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 7/31/2021 5:17 PM, Ben Bacarisse wrote:
>>>>> olcott <No...@NoWhere.com> writes:
>>>>>
>>>>>> On 7/30/2021 3:47 PM, Ben Bacarisse wrote:
>>>>>
>>>>>>> It does not matter what the trace shows. The trace can show some code
>>>>>>> deciding absolutely anything, either correctly or incorrectly, and still
>>>>>>> not refute Rice's theorem. Rice's theorem is about the decidability of
>>>>>>> sets.
>>>>>>
>>>>>> If there exists no undecidable counter-example showing the Rice's
>>>>>> theorem is true then it would seem that Rice's theorem would have no
>>>>>> basis.
>>>>> There is no such thing as an undecidable example (singular). But I
>>>>> think you now agree with me: nothing you have posted says anything about
>>>>> the soundness of the theorem. The "if ... then it would seem..."
>>>>> pattern suggest you know you haven't proved anything.
>>>>
>>>> // Simplified Linz Ĥ (Linz:1990:319)
>>>> // Strachey(1965) CPL translated to C
>>>> void P(u32 x)
>>>> {
>>>> if (H(x, x))
>>>> HERE: goto HERE;
>>>> }
>>>>
>>>> int main()
>>>> {
>>>> Output("Input_Halts = ", H((u32)P, (u32)P));
>>>> }
>>>>
>>>> I call the above an HP counter example instance.
>>>
>>> I can't stop you. Is the fact that a key part of the program is missing
>>> what makes it an "HP counter example instance"?
>>>
>>> What the rest of the world calls "HP instances" are actual programs
>>> (plus any required input). But as I've said, you are using words to
>>> suggest things, poetically, in the reader's mind, not to communicate a
>>> precise technical meaning.
>>
>> And (according to you) the technical name for this Ĥ ⟨Ĥ⟩ is the cases
>> that Ĥ gets wrong. That sure doesn't seem like a formal defintion to
>> me.
>
> It's not. The formal definition of the case Ĥ ⟨Ĥ⟩ is Ĥ ⟨Ĥ⟩.
>

What is the name of the category where a TM/input pair: (X,Y) is
undecidable for X? It seems to make the most sense to simply calls this
an undecidable TM/input pair.

>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
>> if M applied to wM halts, and
>>
>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
>> if M applied to wM does not halt
>
> As you keep telling us, for your actual Ĥ,
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>
> which is fine. Nothing contradictory or paradoxical about that result.
> It's just how you've chosen to write Ĥ. The part you get wrong is
> thinking (and claiming) that your Ĥ says something about Linz's proof.
> For a TM to be like Linz's Ĥ (even for the one case Ĥ ⟨Ĥ⟩) the above
> should happen only
>
> if Ĥ applied to ⟨Ĥ⟩ does not halt.
>
> For the proof to be wrong, you would need to have what you once falsely
> claimed to have: an Ĥ that, at least for this one case, behaves as Linz
> (and everyone else) says is impossible.
>

As Linz already specifies yet does not encode in his notation there are
at least three separate and distinct instances of Ĥ.

H[0] means H<sub>0</sub>

H[0] The first one of these instances is the actual Turing machine Ĥ.
H[1] The second one is the TM description ⟨Ĥ⟩ input to Ĥ.
H[2] The third one is the copy of the TM description ⟨Ĥ⟩ input to Ĥ.

If we do not keep track of these distinctions then it seems like Ĥ.qx
decides that its input never halts and then its input immediately halts.
This would be an actual contradiction.

When we do keep track of these distinctions then the input: ⟨Ĥ[1]⟩ to
Ĥ[0] can be understood to never reach its final states Ĥ[1].qy or
Ĥ[1].qn thus proving that Ĥ[0].qx did correctly decide that its input
⟨Ĥ[1]⟩ ⟨Ĥ[2]⟩ never halts.

olcott

unread,
Aug 2, 2021, 11:39:31 PMAug 2
to
On 8/2/2021 10:10 PM, Mike Terry wrote:
> On 03/08/2021 03:26, olcott wrote:
>>>>> I can't stop you using words like this.  But if you want to write
>>>>> clearly so that experts can understand you, you would need to learn
>>>>> what
>>>>> the words you use mean to other people.
>>>>> But part of me is happy for you keep misusing terms like this.  It
>>>>> makes
>>>>> it obvious that you don't really know how to say what you mean, so
>>>>> naive
>>>>> readers are less likely to be taken in.
>>>>
>>>> I asked you for a correction, simply ignoring this request is not an
>>>> honest dialogue.
>>>
>>> You asked me for the name of a category that is, at best, vague for me
>>> because you described the category using technical words in a way that's
>>> not usual.
>>>
>>> My best guess for "undecidable TM/input pair for X" is "a halting
>>> problem instance that X gets wrong".
>>
>> Surely there is a better way to say it than that.
>
> "Nemesis" inputs...  That should be emotive enough for you, but still
> conveys the impression that the input is constructed to "defeat" the
> potential decider - like pretending that the decider is a superhero and
> every superhero has to have (at least) one nemesis, or things would be
> boring!
>

Among all philosophical understandings of the formal nature of truth the
Liar Paradox (upon which the Tarski undefinability theorem is based) has
fooled all into believing that Truth itself is incoherent:

http://www.liarparadox.org/Tarski_Proof_275_276.pdf

> But Ben's "inputs the decider gets wrong" is ok too!
>
>>
>>> I've given you this alternative
>>> before, but you don't like it.  Maybe you just want a more emotive or
>>> poetic term.  Shall we call them "spawn of the devil inputs for X"?
>>>
>>> But step one is for you to read a book so you know what decidable means
>>> (in this context).  Ideally, you will see from the book that the term is
>>> not ideal, and you'll switch to talking about recursive sets.  Shall we
>>> do that?  It might help.
>>>
>>
>> It seems to me that saying that it is a TM/input pair such that both
>> Boolean values are incorrect final states for the decision criteria
>> gets closer to the philosophical underpinnings of the issue.
Reply all
Reply to author
Forward
0 new messages