XPost: comp.theory, sci.logic, sci.math
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
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)