Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

"jackpot: you may have an unnecessary change record" -- message from "diff"


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
Re: Olcott wrong about infinite recursion [ simplest rebuttal of halting theorem ]

<upSdnfNv4q1S8RD8nZ2dnUU7-WXNnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/computers/article-flat.php?id=7577&group=comp.ai.philosophy#7577

 copy link   Newsgroups: comp.theory sci.logic sci.math comp.ai.philosophy
Followup: comp.theory
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
 by: olcott - Thu, 11 Nov 2021 19:19 UTC

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

Re: Olcott wrong about infinite recursion [ simplest rebuttal of halting theorem ]

<N_ydnYUGyNtE5BD8nZ2dnUU7-RPNnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/computers/article-flat.php?id=7579&group=comp.ai.philosophy#7579

 copy link   Newsgroups: comp.theory comp.ai.philosophy sci.logic sci.math
Followup: comp.theory
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
 by: olcott - Thu, 11 Nov 2021 20:15 UTC

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

rocksolid light 0.9.7
clearnet tor