Refutation of [Strachey 1965] and Halting Problem associated proofs

[Mr Flibble]

I have an idea for a simulating halt decider that forks the
simulation into two branches if the input calls the halt decider as
per [Strachey 1965]'s "Impossible Program":

void P(void (*x)())
{
if (H(x, x))
infinite_loop: goto infinite_loop;
return;
}

int main()
{
std::cout << "Input halts: " << H(P, P) << std::endl;
}

When the simulator detects the call to H in P it forks the simulation
into a non-halting branch (returning 0 to P) and a halting branch
(returning 1 to P) and continues the simulation of these two branches
in parallel.

If the non-halting branch is determined to halt AND the halting branch
is determined to not halt then pathology is detected and reported.

If EITHER branch is determined to be correctly decided then that will
be the decision of the halting decider.

Crucially this scheme will handle (and correctly decide) the
following case whereby the result of H is discarded by the input:

void Px(void (*x)())
{
(void) H(x, x);
return;
}

/Flibble

Copyright (c) 2022 Mr Flibble

[Ben Bacarisse]

Mr Flibble <fli...@reddwarf.jmc.corp> writes:

> If the non-halting branch is determined to halt AND the halting branch
> is determined to not halt then pathology is detected and reported.

Thus H is not a decider in the technical sense of the word. Why is your
not-quite-a-decider any better than the ones half a dozen students come
up with every year when a class sees this problem for the first time?

--
Ben.

[Mr Flibble]

My solution is novel: it correctly decides non-pathological input
(including input that calls the decider) and signals an exception for
pathological input (which is the correct thing to do).

/Flibble

[Ben Bacarisse]

Currently you have no algorithm, just an idea for an algorithm. When
you try to pin down the details you will have something that can't
detect all inputs that a functionally the same as the pathological cases
you think you want to spot. This is a hole every such proposed "almost
solution" falls into.

Just saying that you detect them all is not an algorithm. It's design
by wishful thinking.

--
Ben.

[olcott]

On 7/30/2022 9:07 PM, Ben Bacarisse wrote:
> Mr Flibble <fli...@reddwarf.jmc.corp> writes:
>
>> On Sun, 31 Jul 2022 01:59:12 +0100
>> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>>
>>> Mr Flibble <fli...@reddwarf.jmc.corp> writes:
>>>
>>>> If the non-halting branch is determined to halt AND the halting
>>>> branch is determined to not halt then pathology is detected and
>>>> reported.
>>>
>>> Thus H is not a decider in the technical sense of the word. Why is
>>> your not-quite-a-decider any better than the ones half a dozen
>>> students come up with every year when a class sees this problem for
>>> the first time?
>>
>> My solution is novel: it correctly decides non-pathological input
>> (including input that calls the decider) and signals an exception for
>> pathological input (which is the correct thing to do).
>
> Currently you have no algorithm, just an idea for an algorithm. When
> you try to pin down the details you will have something that can't
> detect all inputs that a functionally the same as the pathological cases
> you think you want to spot. This is a hole every such proposed "almost
> solution" falls into.
>
> Just saying that you detect them all is not an algorithm. It's design
> by wishful thinking.
>

I have been telling him that.

--
Copyright 2022 Pete Olcott

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

[Richard Damon]

POT - KETTLE - BLACK

Your "algroithm" has the exact same problem.

[Mr Flibble]

On Sun, 31 Jul 2022 03:07:17 +0100

My proposal is sufficiently detailed to be classed as a high-level
design of an algorithm and I don't have to provide an implementation to
prove that my algorithm is correct. I believe have refuted [Strachey
1965] and associated Halting Problem proofs by providing a solution
that can handle the "Impossible Program".

/Flibble

[Mr Flibble]

It has likely been many years since the last time you told anyone
anything of value or substance.

/Flibble

[Mr Flibble]

No, Olcott's algorithm is demonstrably wrong; my algorithm isn't so
they do not have "the exact same problem".

/Flibble

[olcott]

Your algorithm has never been presented.

void Infinite_Recursion(int N)
{
Infinite_Recursion(N);
}

int main()
{
Output("Input_Halts = ", H(Infinite_Recursion, 0x777));
}

This is my algorithm and it does work correctly on infinite
recursion.

H: Begin Simulation Execution Trace Stored at:111b61
machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
[0000101e][00111b4d][00111b51] 55 push ebp
[0000101f][00111b4d][00111b51] 8bec mov ebp,esp
[00001021][00111b4d][00111b51] 8b4508 mov eax,[ebp+08]
[00001024][00111b49][00000777] 50 push eax
[00001025][00111b45][0000102a] e8f4ffffff call 0000101e
[0000101e][00111b41][00111b4d] 55 push ebp
[0000101f][00111b41][00111b4d] 8bec mov ebp,esp
[00001021][00111b41][00111b4d] 8b4508 mov eax,[ebp+08]
[00001024][00111b3d][00000777] 50 push eax
[00001025][00111b39][0000102a] e8f4ffffff call 0000101e
H: Infinite Recursion Detected Simulation Stopped

The state of the virtual machine that repeats is:
(a) EIP register value = 00000f9b
(b) The top two stack values = 00000f8f
(c) The call address target is 00000c9f

We also must make sure that there are no control flow
instructions between the invocation of P() and its call
to H(P,P) or P could be counting down a static variable
that could stop the repetition.

[Dennis Bush]

Maybe in this case, but not in the general case. It also doesn't help that you're answering the wrong question and think that H(P,P)==0 is correct despite the *definition* stating otherwise.

>
> H: Begin Simulation Execution Trace Stored at:111b61
> machine stack stack machine assembly
> address address data code language
> ======== ======== ======== ========= =============
> [0000101e][00111b4d][00111b51] 55 push ebp
> [0000101f][00111b4d][00111b51] 8bec mov ebp,esp
> [00001021][00111b4d][00111b51] 8b4508 mov eax,[ebp+08]
> [00001024][00111b49][00000777] 50 push eax
> [00001025][00111b45][0000102a] e8f4ffffff call 0000101e
> [0000101e][00111b41][00111b4d] 55 push ebp
> [0000101f][00111b41][00111b4d] 8bec mov ebp,esp
> [00001021][00111b41][00111b4d] 8b4508 mov eax,[ebp+08]
> [00001024][00111b3d][00000777] 50 push eax
> [00001025][00111b39][0000102a] e8f4ffffff call 0000101e
> H: Infinite Recursion Detected Simulation Stopped
>
> The state of the virtual machine that repeats is:
> (a) EIP register value = 00000f9b
> (b) The top two stack values = 00000f8f
> (c) The call address target is 00000c9f
>
> We also must make sure that there are no control flow
> instructions between the invocation of P() and its call
> to H(P,P) or P could be counting down a static variable
> that could stop the repetition.

No control flow instructions *between successive calls to H*, not just in the function P before the call to H. And there are *many* such instructions in Pa(Pa), specifically all of the instructions in Ha and the functions that it calls that check for its abort condition.

Ha(Pa,Pa) must decide the halt status of Pa(Pa), not Pn(Pn) as you claim:

On Saturday, July 30, 2022 at 4:09:34 PM UTC-4, olcott wrote:
> H(P,P) is asking would the input that I correctly emulate ever reach its
> "ret" instruction (final state) if I never stopped emulating it?

[Mr Flibble]

I have presented the high level design of an algorithm and I do not
have to provide an implementation to prove it is correct, to prove that
it does what it says on the tin.

That is a trivial case to recognize; your decider gets the following
wrong however:

void Px()
{
(void) H(Px, Px);
}

Px always halts and yet your decider returns a result of non-halting
which is INCORRECT.

/Flibble

[Ben Bacarisse]

So you can move on then. If you think there is nothing more that needs
to be said, there is no need to keep posting about it.

> I believe have refuted [Strachey
> 1965] and associated Halting Problem proofs by providing a solution
> that can handle the "Impossible Program".

Uou were clear that your algorithm was not a halt decider. What has it
got to do with proof about halt deciders?

--
Ben.

[Skep Dick]

Game theory 101 is the strategy-stealing strategy. Any strategy available to H against P is also available to P against H.

When H simulates P (simulating H(simulating P ))) the simulated H throws an exception. P catches the exception and enters an infinite loop.

Thus making top-level H enter an infinite loop also.

You and olcott should hang out more often. Your psychologies epitomize the pathological P.

[Mr Flibble]

Nope, the exception is not visible to simulated P and there is no
simulated H.

/Flibble

[Richard Damon]

Unfortunately, that means that H can't be the equivalent of a Turing
Machine.

Your "Blue Screen of Death" answer of pathological is NOT a valid
response for a true Computation, so i might allow you to define an
answer in some side system of Computation that is close to, but not the
same as, that used in Computation Theory.

The problem is you are defining some "priveldge" state of your decider
that other Computations don't have access to and thus your system
becomes non-Turing Complete.

[Mr Flibble]

FALSE. The exception is visible to whatever is calling H outside of
the simulation. It is entirely Turing Complete.

/Flibble

[Richard Damon]

So, your saying I can wrote a program P that I directly write that calls
H(P,P) and it will get the Conflicting answer, and thus H doesn't
simulate that behavior of P?

That indicates that H doesn't do a correct simulation of P.

[Mr Flibble]

On Sun, 31 Jul 2022 20:24:54 -0400

We have been over this: it is no concern of my decider what programs do
outside of calling H.

/Flibble