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

// Simplified Linz Ĥ (Linz:1990:319)
// Strachey(1965) CPL translated to C
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}

int main()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
}

We can analyze H(P,P) at the very high level of abstraction of its two
possible behaviors relative to its input allows us to concisely prove
that not halting <is> the correct decision for this input. No matter how
H works internally the only thing that counts is the behavior of its
input for the two possible behaviors that H can have.

Since the input to H(P,P) never reaches its final state for the two
possible behaviors that every H can possibly have (abort the input or do
not abort the input) then we can conclude that not halting is the
correct decision for every possible simulating halt decider H.

Halting problem undecidability and infinitely nested simulation
May 2021 PL Olcott

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation



--
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)

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

On 11/1/2021 5:50 AM, Ben Bacarisse wrote:

olcott <NoOne@NoWhere.com> writes:

Subject: Re: H(P,P)==0 is correct for every simulating halt decider H --- V2

No. H(P,P) == 0 is correct if, and only if, P(P) does not halt. But (according to you -- we are not allowed to see the full code) P(P)
halts:

No matter what the code is for H every possible H must abort its
simulation of (P,P) otherwise this input never halts.

|| Here's the key question: do you still assert that H(P,P) == false is
|| the "correct" answer even though P(P) halts?

H(P,P) reports that its input never halts.
It is indeed a verified fact that its input never halts.
When you argue with verified facts you diverge from rationality.

H1(P,P) reports that P(P) halts.

Both are correct.

| Yes that is the correct answer even though P(P) halts.

No waffle can alter the fact that false (or 0 etc.) is the wrong return.

--
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)

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

On 11/1/2021 7:46 AM, Malcolm McLean wrote:

On Monday, 1 November 2021 at 03:45:47 UTC, olcott wrote:

// Simplified Linz Ĥ (Linz:1990:319)
// Strachey(1965) CPL translated to C
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}

int main()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
}

We can analyze H(P,P) at the very high level of abstraction of its two
possible behaviors relative to its input allows us to concisely prove
that not halting <is> the correct decision for this input. No matter how
H works internally the only thing that counts is the behavior of its
input for the two possible behaviors that H can have.

Since the input to H(P,P) never reaches its final state for the two
possible behaviors that every H can possibly have (abort the input or do
not abort the input) then we can conclude that not halting is the
correct decision for every possible simulating halt decider H.

I can see where the confusion lies. If H never aborts, it simulates P forever.
If it aborts, then it aborts because it has detected that otherwise P would simulate forever.

What you are forgetting is that P depends on H. If H aborts, the P would also abort i.e. terminate. So if H aborts P, it aborts incorrectly, despite the fact
that if it didn't abort, P would run forever.
That seems like a contradiction, but it isn't really, because we are talking about two Ps, one with an H which never aborts, one with an H that aborts.

void Infinite_Loop()
{
HERE: goto HERE;
}

_Infinite_Loop()
[00000ab0](01) 55 push ebp
[00000ab1](02) 8bec mov ebp,esp
[00000ab3](02) ebfe jmp 00000ab3
[00000ab5](01) 5d pop ebp
[00000ab6](01) c3 ret
Size in bytes:(0007) [00000ab6]

If H allows Infinite_Loop() to continue then Infinite_Loop() never
reaches its final state of 0xab6. If H aborts its simulation of
Infinite_Loop() then it stops at 0xab3 and never reaches its final state
of 0xab6. H(P,P) is the same situation:

We are talking about this case shown below which conclusively proves
that every simulating halt decider H must abort its simulation its input otherwise (just like the infinite loop shown above) its input never halts.

Aborting the input does not count as halting because the input never
reaches its final state no matter what H does. Any input that never
reaches its final state NO MATTER WHAT is an input that never halts.

// Simplified Linz Ĥ (Linz:1990:319)
// Strachey(1965) CPL translated to C
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}

int main()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
}

_P()
[00000c36](01) 55 push ebp
[00000c37](02) 8bec mov ebp,esp
[00000c39](03) 8b4508 mov eax,[ebp+08] // 2nd Param
[00000c3c](01) 50 push eax
[00000c3d](03) 8b4d08 mov ecx,[ebp+08] // 1st Param
[00000c40](01) 51 push ecx
[00000c41](05) e820fdffff call 00000966 // call H
[00000c46](03) 83c408 add esp,+08
[00000c49](02) 85c0 test eax,eax
[00000c4b](02) 7402 jz 00000c4f
[00000c4d](02) ebfe jmp 00000c4d
[00000c4f](01) 5d pop ebp
[00000c50](01) c3 ret
Size in bytes:(0027) [00000c50]

_main()
[00000c56](01) 55 push ebp
[00000c57](02) 8bec mov ebp,esp
[00000c59](05) 68360c0000 push 00000c36 // push P
[00000c5e](05) 68360c0000 push 00000c36 // push P
[00000c63](05) e8fefcffff call 00000966 // call H(P,P)
[00000c68](03) 83c408 add esp,+08
[00000c6b](01) 50 push eax
[00000c6c](05) 6857030000 push 00000357
[00000c71](05) e810f7ffff call 00000386
[00000c76](03) 83c408 add esp,+08
[00000c79](02) 33c0 xor eax,eax
[00000c7b](01) 5d pop ebp
[00000c7c](01) c3 ret
Size in bytes:(0039) [00000c7c]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= ============= [00000c56][0010172a][00000000] 55 push ebp [00000c57][0010172a][00000000] 8bec mov ebp,esp [00000c59][00101726][00000c36] 68360c0000 push 00000c36 // push P [00000c5e][00101722][00000c36] 68360c0000 push 00000c36 // push P [00000c63][0010171e][00000c68] e8fefcffff call 00000966 // call H(P,P)

Begin Local Halt Decider Simulation at Machine Address:c36 [00000c36][002117ca][002117ce] 55 push ebp [00000c37][002117ca][002117ce] 8bec mov ebp,esp [00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08] [00000c3c][002117c6][00000c36] 50 push eax // push P [00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08] [00000c40][002117c2][00000c36] 51 push ecx // push P [00000c41][002117be][00000c46] e820fdffff call 00000966 // call H(P,P)

[00000c36][0025c1f2][0025c1f6] 55 push ebp [00000c37][0025c1f2][0025c1f6] 8bec mov ebp,esp [00000c39][0025c1f2][0025c1f6] 8b4508 mov eax,[ebp+08] [00000c3c][0025c1ee][00000c36] 50 push eax // push P [00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08] [00000c40][0025c1ea][00000c36] 51 push ecx // push P [00000c41][0025c1e6][00000c46] e820fdffff call 00000966 // call H(P,P)
Local Halt Decider: Infinite Recursion Detected Simulation Stopped


The above if from pages 4 and 5
Halting problem undecidability and infinitely nested simulation
May 2021 PL Olcott

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation




--
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)

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

On 11/1/2021 9:28 AM, Ben Bacarisse wrote:

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

On Monday, 1 November 2021 at 03:45:47 UTC, olcott wrote:

// Simplified Linz Ĥ (Linz:1990:319)
// Strachey(1965) CPL translated to C
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}

int main()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
}

We can analyze H(P,P) at the very high level of abstraction of its two
possible behaviors relative to its input allows us to concisely prove
that not halting <is> the correct decision for this input. No matter how >>> H works internally the only thing that counts is the behavior of its
input for the two possible behaviors that H can have.

Since the input to H(P,P) never reaches its final state for the two
possible behaviors that every H can possibly have (abort the input or do >>> not abort the input) then we can conclude that not halting is the
correct decision for every possible simulating halt decider H.

I can see where the confusion lies. If H never aborts, it simulates P forever.
If it aborts, then it aborts because it has detected that otherwise P would >> simulate forever.

What you are forgetting is that P depends on H.

What makes you think he's forgetting that? Having (at least) two
different Hs without changing H^ (now called P) has been the ruse for
months and months.

His Halts function was declared correct because of what would happen if
line 15 were commented out. It has always been some variation of the
theme of "the wrong answer is right because of what would happen if H
(but not H^) were not the function it really is".

No matter what the code is for H every possible H must abort its
simulation of (P,P) otherwise this input never halts.

Whether or not H(P,P) aborts its simulation of its input this input
reaches its final state, thus in all cases the input to H(P,P) never
reaches its final state thus in all cases the input to H(P,P) matches
the definition of not halting.

Now that I have generalized my proof such that this proof can be
directly applied to the Linz it is in a form that is in the ballpark of
what academic journals would accept.

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
If the pure simulation of the input to Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ reaches Ĥ.qy

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
If the pure simulation of the input to Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ would never reach
Ĥ.qy or Ĥ.qn

Halting problem undecidability and infinitely nested simulation
May 2021 PL Olcott

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

If H aborts, the P would also
abort i.e. terminate. So if H aborts P, it aborts incorrectly, despite the fact
that if it didn't abort, P would run forever.
That seems like a contradiction, but it isn't really, because we are talking >> about two Ps, one with an H which never aborts, one with an H that
aborts.

Do you think the change of name from a dependent one (H^) to one that
hides the dependence (P) is an accident? Might is not be part of the
scheme to find words that make the wrong answer, H(P,P) == false, seem
less wrong despite the fact that P(P) halts?

--
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)

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

On 11/1/2021 5:38 PM, Ben Bacarisse wrote:

olcott <NoOne@NoWhere.com> writes:

|| Here's the key question: do you still assert that H(P,P) == false is
|| the "correct" answer even though P(P) halts?

To which you replied (but have for some reason cut from this post)

| Yes that is the correct answer even though P(P) halts.

H(P,P) reports that its input never halts.

H(P,P) should report on whether P(P) halts. Stating that the wrong
answer is the right one is not how mathematics is done.

H1(P,P) is computationally equivalent to P(P).
H(P,P) is not computationally equivalent to P(P).


--
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)

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

On 11/2/2021 8:19 AM, Ben Bacarisse wrote:

olcott <NoOne@NoWhere.com> writes:

On 11/1/2021 5:38 PM, Ben Bacarisse wrote:

olcott <NoOne@NoWhere.com> writes:

|| Here's the key question: do you still assert that H(P,P) == false is >>>>> || the "correct" answer even though P(P) halts?

To which you replied (but have for some reason cut from this post)

| Yes that is the correct answer even though P(P) halts.

H(P,P) reports that its input never halts.

H(P,P) should report on whether P(P) halts. Stating that the wrong
answer is the right one is not how mathematics is done.

H1(P,P) is computationally equivalent to P(P).
H(P,P) is not computationally equivalent to P(P).

H(P,P) == false is wrong if P(P) halts.

The input to H(P,P) really does never halt this has been conclusively
proven. That you keep ignoring the verified fact that the input to
H(P,P) has been totally proven to never reaches its final state sure
seems to be an irrational break from reality to me.

It really seems that P(P) should have behavior consistent with H(P,P). Intuitively they seem to be the same computation. When they don't have
behavior that is consistent with each other this merely proves that
intuition was wrong. Intuition is not infallible. Running the actual
code does infallibly show what the code actually does.

Since a halt decider is supposed to report what its input actually does
we still have H1(P,P) that does just that.

The whole issue with the halting problem proofs is that an input was intentionally designed to thwart the halt decider. This has always been understood to be an input that does the opposite of whatever the halt
decider decides.

One of the two halt deciders does get an answer that is consistent with
the behavior of its input.

This comes from the definition
of the problem you have been studying for more than 14 years. I think
it's time you did something else. It seems such a waste...

H1(P,P) is computationally equivalent to P(P) and and reports that P(P)
halts. This is the same as applying H to ⟨Ĥ⟩ ⟨Ĥ⟩ which was something that Linz "proved" was impossible.



--
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)