Groups > comp.theory > #37341 > unrolled thread

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

Started by	olcott <NoOne@NoWhere.com>
First post	2021-07-30 08:46 -0500
Last post	2021-07-30 22:26 -0600
Articles	20 on this page of 45 — 8 participants

Back to article view | Back to comp.theory

  Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-07-30 08:46 -0500
    Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-30 15:09 +0100
      Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-07-30 10:40 -0500
        Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-30 19:27 +0100
          Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-07-30 13:45 -0500
            Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Richard Damon <Richard@Damon-Family.org> - 2021-07-30 13:28 -0700
            Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-30 21:47 +0100
              Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-07-30 16:43 -0500
                Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Richard Damon <news.x.richarddamon@xoxy.net> - 2021-07-30 14:51 -0700
                  Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-07-30 16:59 -0500
                    Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Richard Damon <Richard@Damon-Family.org> - 2021-07-30 15:21 -0700
                      Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-07-30 17:45 -0500
                        Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-07-30 16:32 -0700
                          Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-07-30 18:44 -0500
                        Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Richard Damon <Richard@Damon-Family.org> - 2021-07-30 17:25 -0700
                Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-31 23:17 +0100
                  Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-07-31 21:34 -0500
                    Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-08-01 11:22 +0100
                      Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-08-01 23:07 -0500
                        Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-08-02 17:32 +0100
                          Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-08-02 13:37 -0500
                            Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-08-03 01:25 +0100
                              Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-08-02 20:02 -0500
                                Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-08-03 02:58 +0100
                                  Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-08-02 21:26 -0500
                                    Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-08-03 04:10 +0100
                                      Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-08-02 22:39 -0500
                                        Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Richard Damon <Richard@Damon-Family.org> - 2021-08-02 22:29 -0700
                                    Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-08-04 19:45 +0100
                            Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Richard Damon <Richard@Damon-Family.org> - 2021-08-02 22:22 -0700
    Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] André G. Isaak <agisaak@gm.invalid> - 2021-07-30 11:06 -0600
      Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-07-30 12:11 -0500
        Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] André G. Isaak <agisaak@gm.invalid> - 2021-07-30 15:46 -0600
          Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-07-30 16:53 -0500
            Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] André G. Isaak <agisaak@gm.invalid> - 2021-07-30 16:13 -0600
              Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-07-30 17:43 -0500
                Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] André G. Isaak <agisaak@gm.invalid> - 2021-07-30 17:01 -0600
                  Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] André G. Isaak <agisaak@gm.invalid> - 2021-07-30 17:18 -0600
                  Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-07-30 18:34 -0500
                    Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] André G. Isaak <agisaak@gm.invalid> - 2021-07-30 20:05 -0600
                      Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-07-30 21:33 -0500
                        Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] André G. Isaak <agisaak@gm.invalid> - 2021-07-30 21:09 -0600
                          Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-07-30 22:23 -0500
                            Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Richard Damon <Richard@Damon-Family.org> - 2021-07-30 20:57 -0700
                              Re: Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ] Jeff Barnett <jbb@notatt.com> - 2021-07-30 22:26 -0600

Page 1 of 3 [1] 2 3 Next page →

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

From	olcott <NoOne@NoWhere.com>
Date	2021-07-30 08:46 -0500
Subject	Pathological self-reference(Olcott 2004) decider [ Defeating Rice's Theorem ]
Message-ID	<29qdnTcRYNdXn5n8nZ2dnUU7-LfNnZ2d@giganews.com>

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

[toc] | [next] | [standalone]

#37343

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2021-07-30 15:09 +0100
Message-ID	<87v94rzye7.fsf@bsb.me.uk>
In reply to	#37341

olcott <NoOne@NoWhere.com> writes:

> 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

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!

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#37351

From	olcott <NoOne@NoWhere.com>
Date	2021-07-30 10:40 -0500
Message-ID	<z9mdnaGTLJUagJn8nZ2dnUU7-W3NnZ2d@giganews.com>
In reply to	#37343

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

[toc] | [prev] | [next] | [standalone]

#37356

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2021-07-30 19:27 +0100
Message-ID	<87bl6jmzcb.fsf@bsb.me.uk>
In reply to	#37351

olcott <NoOne@NoWhere.com> writes:

> 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.

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.

> 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.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#37357

From	olcott <NoOne@NoWhere.com>
Date	2021-07-30 13:45 -0500
Message-ID	<ndednaSwVuJe1Zn8nZ2dnUU7-XXNnZ2d@giganews.com>
In reply to	#37356

On 7/30/2021 1:27 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> 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.
> 
> 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?


-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]

#37365

From	Richard Damon <Richard@Damon-Family.org>
Date	2021-07-30 13:28 -0700
Message-ID	<ChZMI.70615$Nq7.68279@fx33.iad>
In reply to	#37357

On 7/30/21 11:45 AM, olcott wrote:
> On 7/30/2021 1:27 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> 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.
>>
>> 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.

The issue is that self-reference is a SYNTACTIC decision, not a SEMANTIC
decision. Rice is only about SEMANTIC decisions.

> 
>>> 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?
> 
> 

Because it isn't a proper trace of the ACTUAL execution of a x86
machine, skipping the trace of the function H, and the transformation of
a trace of a simulator to the trace of a simulated machine is only
applicable for a simulator that NEVER aborts its simulation (not being a
pure simulator until) so it is doing UNSOUND logic.

This is PROVED By the fact that you say it 'proves' that H^(H^) will
never halt when we also have traces, provided by you, that show that it
will halt.

[toc] | [prev] | [next] | [standalone]

#37366

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2021-07-30 21:47 +0100
Message-ID	<87o8ajleao.fsf@bsb.me.uk>
In reply to	#37357

olcott <NoOne@NoWhere.com> writes:

> On 7/30/2021 1:27 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>> 
>>> 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.
>> 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.

>>> 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.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#37369

From	olcott <NoOne@NoWhere.com>
Date	2021-07-30 16:43 -0500
Message-ID	<JfadnQDf69MG75n8nZ2dnUU7-QHNnZ2d@giganews.com>
In reply to	#37366

On 7/30/2021 3:47 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> On 7/30/2021 1:27 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> 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.
>>> 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.

-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]

#37372

From	Richard Damon <news.x.richarddamon@xoxy.net>
Date	2021-07-30 14:51 -0700
Message-ID	<se1s96$i4h$1@dont-email.me>
In reply to	#37369

On 7/30/21 2:43 PM, olcott wrote:
> On 7/30/2021 3:47 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 7/30/2021 1:27 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> 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.
>>>> 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.

But your form of Self-References isn't a Semantic property, by a
Syntactic property, and thus not under Rice's Theorem.

> 
>>>>> 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.
> 

Lack of Proof is not proof of lack. Rice's theorem is NOT just proved
from this case, and in fact, since it is a more general form than this
case, it CAN'T be proved from a simple halt decider proof. Thus your
'counter' doesn't actually counter the proof.

[toc] | [prev] | [next] | [standalone]

#37374

From	olcott <NoOne@NoWhere.com>
Date	2021-07-30 16:59 -0500
Message-ID	<2JCdndSpUaOp65n8nZ2dnUU7-avNnZ2d@giganews.com>
In reply to	#37372

On 7/30/2021 4:51 PM, Richard Damon wrote:
> On 7/30/21 2:43 PM, olcott wrote:
>> On 7/30/2021 3:47 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 7/30/2021 1:27 PM, Ben Bacarisse wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> 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.
>>>>> 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.
> 
> But your form of Self-References isn't a Semantic property, by a
> Syntactic property, and thus not under Rice's Theorem.
> 
I have already been all through this very very extensively with others 
in this forum in prior years you are wrong.

-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]

#37377

From	Richard Damon <Richard@Damon-Family.org>
Date	2021-07-30 15:21 -0700
Message-ID	<4Y_MI.17339$qL.14609@fx14.iad>
In reply to	#37374

On 7/30/21 2:59 PM, olcott wrote:
> On 7/30/2021 4:51 PM, Richard Damon wrote:
>> On 7/30/21 2:43 PM, olcott wrote:
>>> On 7/30/2021 3:47 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 7/30/2021 1:27 PM, Ben Bacarisse wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> 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.
>>>>>> 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.
>>
>> But your form of Self-References isn't a Semantic property, by a
>> Syntactic property, and thus not under Rice's Theorem.
>>
> I have already been all through this very very extensively with others
> in this forum in prior years you are wrong.
> 

Since your decider only detects 'Self-Reference' but never sees past the
reference, that is just a Syntactic Property, and can be detected by
pure examination (and not simulation) of the input.


I'm not even sure if you can even full define which machines are 'in
general' a pathological self-referent. After all, if all you had was the
complete Turing description of H^ which includes a copy of H with in,
can you relably detect that there IS a piece within it that could be a
independent Turing Machine to be pathological to?

[toc] | [prev] | [next] | [standalone]

#37379

From	olcott <NoOne@NoWhere.com>
Date	2021-07-30 17:45 -0500
Message-ID	<VdKdnaz6mqmRHJn8nZ2dnUU7-dOdnZ2d@giganews.com>
In reply to	#37377

On 7/30/2021 5:21 PM, Richard Damon wrote:
> On 7/30/21 2:59 PM, olcott wrote:
>> On 7/30/2021 4:51 PM, Richard Damon wrote:
>>> On 7/30/21 2:43 PM, olcott wrote:
>>>> On 7/30/2021 3:47 PM, Ben Bacarisse wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 7/30/2021 1:27 PM, Ben Bacarisse wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>>> 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.
>>>>>>> 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.
>>>
>>> But your form of Self-References isn't a Semantic property, by a
>>> Syntactic property, and thus not under Rice's Theorem.
>>>
>> I have already been all through this very very extensively with others
>> in this forum in prior years you are wrong.
>>
> 
> Since your decider only detects 'Self-Reference' but never sees past the
> reference, that is just a Syntactic Property, and can be detected by
> pure examination (and not simulation) of the input.
> 

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.

> 
> I'm not even sure if you can even full define which machines are 'in
> general' a pathological self-referent. After all, if all you had was the
> complete Turing description of H^ which includes a copy of H with in,
> can you relably detect that there IS a piece within it that could be a
> independent Turing Machine to be pathological to?
> 
> 
> 
> 


-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]

#37382

From	Malcolm McLean <malcolm.arthur.mclean@gmail.com>
Date	2021-07-30 16:32 -0700
Message-ID	<0cfc081a-e4ec-4975-a536-a54c61b188a1n@googlegroups.com>
In reply to	#37379

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.
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.

[toc] | [prev] | [next] | [standalone]

#37384

From	olcott <NoOne@NoWhere.com>
Date	2021-07-30 18:44 -0500
Message-ID	<8IednQ2vSftUE5n8nZ2dnUU7-TfNnZ2d@giganews.com>
In reply to	#37382

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.

-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]

#37385

From	Richard Damon <Richard@Damon-Family.org>
Date	2021-07-30 17:25 -0700
Message-ID	<BL0NI.127907$h8.94382@fx47.iad>
In reply to	#37379

On 7/30/21 3:45 PM, 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.

But the input to H(P,P) represents that same machine, so that fact that
H terminates its simulation doesn't make the machine that the input
represents non-halting.

The aborting of a simulation has absolutly NO affect on the machine
being simulated.

If it would have halted if run longer, then that input represents a
Halting Computation.

If the simulation would have NEVER halted, then that input represent a
non-Halting Computation.

One key thing to remember is that if the simulator is represented within
that input, if we change the simulator to test this, we ONLY change this
instance of the simulator, and not any copies that happen to be within
that input.

Note, when we replace H(P,P) at the top level with UTM(P.P) (and keep P
still using the original H which incorrectly aborted it) then we see
that, as expected, P(P) simulates to its final halting state in a finite
number of steps.

All that the fact tha H never gets there is just PROOF that H was based
on UNSOUND logic. Remember, when you revise the logic of H to fix this
proof, you need to also update the H^/P that it needs to decide on.

[toc] | [prev] | [next] | [standalone]

#37427

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2021-07-31 23:17 +0100
Message-ID	<87y29mjfhb.fsf@bsb.me.uk>
In reply to	#37369

olcott <NoOne@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.

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.

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.  You don't even know what mathematicians mean by "true",
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.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#37435

From	olcott <NoOne@NoWhere.com>
Date	2021-07-31 21:34 -0500
Message-ID	<Tu6dnbI5gNqhlZv8nZ2dnUU7-RPNnZ2d@giganews.com>
In reply to	#37427

On 7/31/2021 5:17 PM, Ben Bacarisse wrote:
> olcott <NoOne@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 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.

-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]

#37441

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2021-08-01 11:22 +0100
Message-ID	<87o8aha2hb.fsf@bsb.me.uk>
In reply to	#37435

olcott <NoOne@NoWhere.com> writes:

> On 7/31/2021 5:17 PM, Ben Bacarisse wrote:
>> olcott <NoOne@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.

>> 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.

Post the code and I'll see what I can do.  You'll have to define
"correct answer" as well because you use those words quasi-poetically
too.  It's quite possible your code does always give the "correct
answer".  After all, your "halt decider" gives the "correct answer" for
the case you obsess about.

>> 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.

Eh?  You are confirming that you have shown, concretely, that you do
indeed use words poetically without really knowing what they mean?  I
don't think you wanted to say that.

>> 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.

Yes, the notion is daft.  You use the words to hint that there is
something fishy going on when there is not.  I can't help you find
correct words to say something daft.

There are infinitely many HP instances.  There are infinitely many TMs.
Infinitely many of those TMs are deciders.  None of those deciders is a
halt decider.  Every decider gets an infinite number of HP instances
wrong.  It's all much simpler than you think.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#37487

From	olcott <NoOne@NoWhere.com>
Date	2021-08-01 23:07 -0500
Message-ID	<9M6dndrUNYbt8pr8nZ2dnUU7-f3NnZ2d@giganews.com>
In reply to	#37441

On 8/1/2021 5:22 AM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> On 7/31/2021 5:17 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@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.

Ĥ.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

>>> 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.
> 
> Post the code and I'll see what I can do.  You'll have to define
> "correct answer" as well because you use those words quasi-poetically
> too.  It's quite possible your code does always give the "correct
> answer".  After all, your "halt decider" gives the "correct answer" for
> the case you obsess about.
> 
>>> 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.
> 
> Eh?  You are confirming that you have shown, concretely, that you do
> indeed use words poetically without really knowing what they mean?  I
> don't think you wanted to say that.
> 

We know that in the above case no H can possibly return a correct halt 
status to P.

// 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;
}

So it should not be that hard to derive an example input that forces the 
u32 PSR_Decider(u32 P, u32 I) to get the wrong answer.

>>> 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.
> 
> Yes, the notion is daft.  You use the words to hint that there is
> something fishy going on when there is not.  I can't help you find
> correct words to say something daft.
> 
> There are infinitely many HP instances.  There are infinitely many TMs.
> Infinitely many of those TMs are deciders.  None of those deciders is a
> halt decider.  Every decider gets an infinite number of HP instances
> wrong.  It's all much simpler than you think.
> 

Maybe then Linz with the totally unspecified ⊢* wildcard state 
transitions is an HP instance template.

-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]

#37496

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2021-08-02 17:32 +0100
Message-ID	<87v94n6c4z.fsf@bsb.me.uk>
In reply to	#37487

olcott <NoOne@NoWhere.com> writes:

> On 8/1/2021 5:22 AM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>> 
>>> On 7/31/2021 5:17 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@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 Ĥ ⟨Ĥ⟩.

> Ĥ.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.

> We know that in the above case no H can possibly return a correct halt
> status to P.

We know a little bit more than that.  If we use symbolic names, we know
that, for every TM J (to which the "hat" construction can be applied), J
is wrong about ⟨Ĵ⟩ ⟨Ĵ⟩.

> // 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;
> }
>
> So it should not be that hard to derive an example input that forces
> the u32 PSR_Decider(u32 P, u32 I) to get the wrong answer.

Tell me what you consider the wrong answer, post the code for H and H2
and I'll do my best.  Of course, PSR_Decider definitely decides
/something/, so you could just declare whatever it decides is correct.
That way you couldn't be wrong.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

Page 1 of 3 [1] 2 3 Next page →

csiph-web

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

Contents

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

#37343

#37351

#37356

#37357

#37365

#37366

#37369

#37372

#37374

#37377

#37379

#37382

#37384

#37385

#37427

#37435

#37441

#37487

#37496