On 11/11/2021 3:19 PM, Richard Damon wrote:
> On 11/11/21 3:47 PM, olcott wrote:
>> On 11/11/2021 2:24 PM, Richard Damon wrote:
>>> On 11/11/21 3:01 PM, olcott wrote:
>>>> On 11/11/2021 1:32 PM, Richard Damon wrote:
>>>>>
>>>>> On 11/11/21 2:19 PM, olcott 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.
>>>>>>
>>>>>> 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]
>>>>
>>>>
>>>> YOU TOTALLY IGNORED ALL OF THESE NEXT WORDS
>>>> YOU TOTALLY IGNORED ALL OF THESE NEXT WORDS
>>>> YOU TOTALLY IGNORED ALL OF THESE NEXT WORDS
>>>> YOU TOTALLY IGNORED ALL OF THESE NEXT WORDS
>>>
>>> You can not use the 'proof' for the H that doesn't abort for the H
>>> that does, they are different Hs and create different Ps.
>> If in every H in the universe P never halts then P never halts.
>>
>>
>
> Except most do.
>
> For Any H that returns the value of 0 from H(P,P), then P(P) will halt.
>

For every H in the universe no P ever reaches its machine code address
of 1a72, thus no P ever halts.

> Yes, the simulation inside H of P(P) will not reach its end state before
> H aborts it simulation, but the actual running of P(P) or the simulaiton
> with a REAL UTM will show that halting.
>
> You are using the wrong definition of Halting, it doesn't matter about
> the partial simulation in H, what matters is the actual execution of the
> machine or its exact equivalent by the simulation with a real UTM.

--
Copyright 2021 Pete Olcott

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