XPost: comp.theory, sci.logic, sci.math

On 11/14/2021 3:33 PM, Mr Flibble wrote:

The halting problem as defined is erroneous: it is effectively a
category error.

The categories involved in the category error are:

1) A program
2) The source code for a program
3) A decider
4) That which is being decided.

Until this category error is resolved any further discussion of the
halting problem is pointless.

/Flibble

If you know both C and the x86 language quite well then this is complete
proof that the counter-examples to the halting theorem are decidable as infinite recursion:


Simulating partial halt decider H correctly decides that P(P) never
halts (V1)

#include <stdint.h>
typedef void (*ptr)();

int H(ptr x, ptr y)
{
x(y); // direct execution of P(P)
return 1;
}

// Minimal essence of Linz(1990) Ĥ
// and Strachey(1965) P
void P(ptr x)
{
H(x, x);
}

int main(void)
{
H(P, P);
}

Proof that H(P,P)==0 is correct for every possible H at machine address 00001a7e that simulates or executes the precise byte sequence shown below:

_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]

P is defined as the above precise byte sequence.
The x86 language is the entire inference basis.

For every possible H defined at machine address 00001a7e that has input
(P,P) when the input to H(P,P) is executed or simulated this input is
either infinitely recursive or aborted at some point. In no case does
the input ever reach its final state of 00001a72.

Now that we have verified that the input to H(P,P) never halts we know
that the correct return value for any correct halt decider H(P,P) must
be 0.

To determine the correct halt status of the input to H(P,P) H merely
needs to simulate its input one instruction at a time until H sees P
call itself with the same parameters that it was called with. When H
sees this H correctly returns 0 for not halting.

If the above is so simple that it doesn't even look like it applies to
the halting problem this paper has slightly more complex examples and
much more analysis and reasoning.

Halting problem undecidability and infinitely nested simulation (V2)
November 2021 PL Olcott

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


--
Copyright 2021 Pete Olcott

Talent hits a target no one else can hit;
Genius hits a target no one else can see.
Arthur Schopenhauer

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)