Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

Hacking's just another word for nothing left to kludge.


computers / comp.ai.philosophy / Re: Olcott wrong about infinite recursion [ simplest rebuttal of halting theorem ]

SubjectAuthor
* Re: Olcott wrong about infinite recursion [ simplest rebuttal ofolcott
`- Re: Olcott wrong about infinite recursion [ simplest rebuttal ofolcott

1
Subject: Re: Olcott wrong about infinite recursion [ simplest rebuttal of halting theorem ]
From: olcott
Newsgroups: comp.theory, sci.logic, sci.math, comp.ai.philosophy
Followup: comp.theory
Date: Thu, 11 Nov 2021 19:19 UTC
References: 1 2 3 4
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 11 Nov 2021 13:19:43 -0600
Date: Thu, 11 Nov 2021 13:19:33 -0600
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.3.0
Subject: Re: Olcott wrong about infinite recursion [ simplest rebuttal of
halting theorem ]
Content-Language: en-US
Newsgroups: comp.theory,sci.logic,sci.math,comp.ai.philosophy
References: <20211110215316.0000221e@reddwarf.jmc>
<ApydnX6D6fN31RH8nZ2dnUU7-UXNnZ2d@giganews.com>
<PFZiJ.19745$cW6.10169@fx08.iad> <20211111175240.00000a3b@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
Followup-To: comp.theory
In-Reply-To: <20211111175240.00000a3b@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <upSdnfNv4q1S8RD8nZ2dnUU7-WXNnZ2d@giganews.com>
Lines: 163
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-YnJ98I7AA26OoC0UsD64SaopzlN7aWoty0suLSmYh05xtst7JSssumgna3DNbGMpghyR0UyZxkv3G6h!QmXkt1CFaE/tl4C6QMFI2LzZFPnQPdE/zAMCu9WYUfQHGUA0WfSaSVEGB3kc6siA99bEG7i0qFUy!DA==
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 7300
View all headers
On 11/11/2021 11:52 AM, Mr Flibble wrote:
On Wed, 10 Nov 2021 19:42:23 -0500
Richard Damon <Richard@Damon-Family.org> wrote:

On 11/10/21 5:34 PM, olcott wrote:
On 11/10/2021 3:53 PM, Mr Flibble wrote:
Olcott is barking up the wrong tree re infinite recursion: there
is only a need to detect a single recursive call into the halt
decider and signal an exception.

Yes, I figured that out. That eliminates the need for static local
data thus allowing the halt decider to be a pure function.

Except that this logic is only correct if the function is being
executed under unconditional execution.

If the 'simulation' is being run under condition that can/will
terminate its execution, then the detection of this recursion is NOT
proof that the execution will be non-halting.

All you have show is that IF the decider would never abort its
'simulation' then the program would be non-halting.

Since it turns out that the decider DOES abort its 'simulation', the
assumptions that the analysis was done under are not in fact true, so
the analysis is invalid.



https://en.wikipedia.org/wiki/Pure_function

But Software Engineering 'Pure Function' is NOT the Compution Theory
'Computation', so you need to be aware of the difference.


That is why I needed my source-code analyzer to provide the exact
number of parameters to every function.

As long as the currently executing function (H) is called again
with the same parameters then we know that this call will be
infinitely recursive unless this infinite recursion is aborted at
some point.

Right, it would be infinite if NEVER aborted, but it IS aborted, so
it is not infinite, and since the machine uses a copy of the decider,
that same fact applies to it being run as an indepent computation,
since the decider inside it does abort its internal simulation, it
return the answer that allows the actual computation to be finint.


When H aborts this call to itself made by P then P never reaches
its final state. If H never aborts this call made by P then P never
reaches its final state. This conclusively proves that H can abort
this call to itself and report that its input never halts.


But it doensn't matter that H's PARTIAL simulation of P reached the
halting point. When we run the actual computation, or give this input
to a REAL pure simulator, it will Halt.



Here is the reference to my NumParams system:
On 10/23/2021 8:27 PM, olcott wrote:
[I finally completed my lexical analyzer generator (needed by my
halt decider)]
This system uses a DFA lexical analyzer to recognize
the pattern of function declarations. This pattern is
specified as 15 DFA states. The output is a C header
file that looks up the function name specified in the
COFF object file and returns its number of parameters.

  

And where does this code get the source code of the program whose
COMPILED form has been given to H?

Or, is H now being given the source code as the representation?

Remember, if you do that, then that source code needs to contain the
FULL description of the program, which includes the code for H, and
everything it uses, which includes your NumParams and the compiler
you are going to put that code into.

Nope, H needs to be a black box so its implementation is unknown to
everyone but the creator of H.  If H is a black box it can safely
detect recursion into it and signal an exception.

That won't work because someone could write the same H as a whitebox.

Here is my current enormously simplified proof:
Does the call from P() to H() specify infinite recursion?

#define ptr uintptr_t

void P(ptr x)
{
   H(x, x);
}

int H(ptr x, ptr y)
{
   ((void(*)(ptr))x)(y);
   return 1;
}

int main()
{
   H((ptr)P, (ptr)P);
   return 0;
}

Yes it does.

_P()
[00001a5e](01)  55              push ebp
[00001a5f](02)  8bec            mov ebp,esp
[00001a61](03)  8b4508          mov eax,[ebp+08]
[00001a64](01)  50              push eax        // push P
[00001a65](03)  8b4d08          mov ecx,[ebp+08]
[00001a68](01)  51              push ecx        // push P
[00001a69](05)  e810000000      call 00001a7e   // call H
[00001a6e](03)  83c408          add esp,+08
[00001a71](01)  5d              pop ebp
[00001a72](01)  c3              ret
Size in bytes:(0021) [00001a72]

Now we switch H executing its input to H simulating its input. H simulates the x86 machine language of its input and sees that its simulated P is calling H with the same parameters that H was called with. On this basis H aborts its simulation of P and correctly reports that P would never reach its final state at 1a72. Because H and P are both pure functions we know that H(P,P)==0 is computable.

(a) P only halts if it reaches its final state at 1a72.
(b) If H does not abort its simulation of P then P never reaches its final state at 1a72.
(c) If H aborts its simulation of P then P never reaches its final state as 1a72.
(d) Because P never halts in all possible cases H(P,P)==0 is always correct.

The fact that there are no errors in (a)(b)(c) and (d) is a necessary consequence of (a)(b)(c) conclusively proves that (d) is correct.

Halting problem undecidability and infinitely nested simulation (V2)

https://www.researchgate.net/publication/356105750_Halting_problem_undecidability_and_infinitely_nested_simulation_V2

/Flibble

--
This message is a troll.



--
Copyright 2021 Pete Olcott

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


Subject: Re: Olcott wrong about infinite recursion [ simplest rebuttal of halting theorem ]
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, sci.logic, sci.math
Followup: comp.theory
Date: Thu, 11 Nov 2021 20:15 UTC
References: 1 2 3 4 5 6
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 11 Nov 2021 14:15:21 -0600
Date: Thu, 11 Nov 2021 14:15:19 -0600
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.3.0
Subject: Re: Olcott wrong about infinite recursion [ simplest rebuttal of
halting theorem ]
Content-Language: en-US
Newsgroups: comp.theory,comp.ai.philosophy,sci.logic,sci.math
References: <20211110215316.0000221e@reddwarf.jmc>
<ApydnX6D6fN31RH8nZ2dnUU7-UXNnZ2d@giganews.com>
<PFZiJ.19745$cW6.10169@fx08.iad> <20211111175240.00000a3b@reddwarf.jmc>
<upSdnfNv4q1S8RD8nZ2dnUU7-WXNnZ2d@giganews.com>
<20211111195814.00001bcd@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
Followup-To: comp.theory
In-Reply-To: <20211111195814.00001bcd@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <N_ydnYUGyNtE5BD8nZ2dnUU7-RPNnZ2d@giganews.com>
Lines: 185
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-oiNzajsMK51S7yPQZPtvL79H9TBmyvTKKDFIvdYUVq/4s73izOxLXvT3p972oBiKueMKBy9QmoO38Iy!m4d5i5ZQgfojnCMrL7i5yNwN8kUpW7/jFlv1Ecb8L55SUlmffh3T8BFoX8f0xlcSvGNT0SHjCs8P!bw==
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 7890
View all headers
On 11/11/2021 1:58 PM, Mr Flibble wrote:
On Thu, 11 Nov 2021 13:19:33 -0600
olcott <NoOne@NoWhere.com> wrote:

On 11/11/2021 11:52 AM, Mr Flibble wrote:
On Wed, 10 Nov 2021 19:42:23 -0500
Richard Damon <Richard@Damon-Family.org> wrote:
  
On 11/10/21 5:34 PM, olcott wrote:
On 11/10/2021 3:53 PM, Mr Flibble wrote:
Olcott is barking up the wrong tree re infinite recursion: there
is only a need to detect a single recursive call into the halt
decider and signal an exception.

Yes, I figured that out. That eliminates the need for static local
data thus allowing the halt decider to be a pure function.

Except that this logic is only correct if the function is being
executed under unconditional execution.

If the 'simulation' is being run under condition that can/will
terminate its execution, then the detection of this recursion is
NOT proof that the execution will be non-halting.

All you have show is that IF the decider would never abort its
'simulation' then the program would be non-halting.

Since it turns out that the decider DOES abort its 'simulation',
the assumptions that the analysis was done under are not in fact
true, so the analysis is invalid.

 

https://en.wikipedia.org/wiki/Pure_function

But Software Engineering 'Pure Function' is NOT the Compution
Theory 'Computation', so you need to be aware of the difference.
 

That is why I needed my source-code analyzer to provide the exact
number of parameters to every function.

As long as the currently executing function (H) is called again
with the same parameters then we know that this call will be
infinitely recursive unless this infinite recursion is aborted at
some point.

Right, it would be infinite if NEVER aborted, but it IS aborted, so
it is not infinite, and since the machine uses a copy of the
decider, that same fact applies to it being run as an indepent
computation, since the decider inside it does abort its internal
simulation, it return the answer that allows the actual
computation to be finint.

When H aborts this call to itself made by P then P never reaches
its final state. If H never aborts this call made by P then P
never reaches its final state. This conclusively proves that H
can abort this call to itself and report that its input never
halts.


But it doensn't matter that H's PARTIAL simulation of P reached the
halting point. When we run the actual computation, or give this
input to a REAL pure simulator, it will Halt.



Here is the reference to my NumParams system:
On 10/23/2021 8:27 PM, olcott wrote:
[I finally completed my lexical analyzer generator (needed by my
halt decider)]
This system uses a DFA lexical analyzer to recognize
the pattern of function declarations. This pattern is
specified as 15 DFA states. The output is a C header
file that looks up the function name specified in the
COFF object file and returns its number of parameters.

     

And where does this code get the source code of the program whose
COMPILED form has been given to H?

Or, is H now being given the source code as the representation?

Remember, if you do that, then that source code needs to contain
the FULL description of the program, which includes the code for
H, and everything it uses, which includes your NumParams and the
compiler you are going to put that code into.

Nope, H needs to be a black box so its implementation is unknown to
everyone but the creator of H.  If H is a black box it can safely
detect recursion into it and signal an exception.

That won't work because someone could write the same H as a whitebox.

They could only do that by accident so if the probability of blindly
replicating the black box is sufficiently low we can discount it (just
as we can discount cracking a 512-bit encryption key with a
classical computer).

/Flibble

--
This message is a troll.


I have already spent many hundreds of hours going all through that path decades ago. As long as there is one input that can fool a halt decider the halting problem  cannot be solved.

The machine code of this input is no longer an input that cannot be correctly decided. I enormously simplified the proof of this.

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

The P show below has been simplified so that it only has the essence of the infinitely recursive nature of the above P.

#include <stdint.h>
#define ptr uintptr_t

int H(ptr x, ptr y)
{
   ((void(*)(ptr))x)(y);
   return 1;
}

void P(ptr x)
{
   H(x, x);
}

int main()
{
   H((ptr)P, (ptr)P);
   return 0;
}

_P()
[00001a7e](01)  55              push ebp
[00001a7f](02)  8bec            mov ebp,esp
[00001a81](03)  8b4508          mov eax,[ebp+08]
[00001a84](01)  50              push eax
[00001a85](03)  8b4d08          mov ecx,[ebp+08]
[00001a88](01)  51              push ecx
[00001a89](05)  e810000000      call 00001a9e
[00001a8e](03)  83c408          add esp,+08
[00001a91](01)  5d              pop ebp
[00001a92](01)  c3              ret
Size in bytes:(0021) [00001a92]

(a) P only halts if it reaches its final state at 1a72.

(b) If H does not abort its simulation of P then P never reaches its final state at 1a72.

(c) If H aborts its simulation of P then P never reaches its final state as 1a72.

(d) Because P never halts in all possible cases H(P,P)==0 is always correct.

The fact that there are no errors in (a)(b)(c) and (d) is a necessary consequence of (a)(b)(c) conclusively proves that (d) is correct.

This same proof applies to this more complex P, yet is a has more details making it more difficult to understand:

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



--
Copyright 2021 Pete Olcott

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


1
rocksolid light 0.7.2
clearneti2ptor