info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
That P(P) of main() halts does not contradict H(P,P)==0 [ exception to the rule ]
2 views
Skip to first unread message
olcott
Aug 28, 2021, 12:47:39 PM8/28/21
to
// 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((u32)P);
}
The H executed on line 1 of main() is the same function with the same
input as The executed H called from P(P) executed on line 2 of main.
These two instances have identical behavior.
The simulated H called from the P simulated by the executed H on line 1
of main() is the same function called with the same input as the
executed H.
The simulated P called from the executed H on line 1 of main() is the
same function called with the same input as the executed P on line 2 of
main().
In this case we have a brand new exception to the rule that the same
function called with the same input must have identical behavior.
When one of these function instances is directly executed and the other
is simulated by a simulating halt decider their behavior need not be
identical. The executed function can not be aborted and the simulated
function can be aborted. This forms an exception to the rule that the
same function called with the same input must have identical behavior.
The P executed on line 2 of main() is computationally distinct from the
P simulated by H executed on the first line of main(). Because these are
two different computations they can have different behavior without
contradiction.
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
// 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((u32)P);
}
The H executed on line 1 of main() is the same function with the same
input as The executed H called from P(P) executed on line 2 of main.
These two instances have identical behavior.
The simulated H called from the P simulated by the executed H on line 1
of main() is the same function called with the same input as the
executed H.
The simulated P called from the executed H on line 1 of main() is the
same function called with the same input as the executed P on line 2 of
main().
In this case we have a brand new exception to the rule that the same
function called with the same input must have identical behavior.
When one of these function instances is directly executed and the other
is simulated by a simulating halt decider their behavior need not be
identical. The executed function can not be aborted and the simulated
function can be aborted. This forms an exception to the rule that the
same function called with the same input must have identical behavior.
The P executed on line 2 of main() is computationally distinct from the
P simulated by H executed on the first line of main(). Because these are
two different computations they can have different behavior without
contradiction.
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
olcott
Aug 29, 2021, 9:28:58 AM8/29/21
to
On 8/29/2021 6:00 AM, Richard Damon wrote:
> On 8/29/21 12:00 AM, olcott wrote:
>> On 8/28/2021 7:07 PM, Richard Damon wrote:
>>> On 8/28/21 7:51 PM, olcott wrote:
>>>
>>>>
>>>> I will take this to mean that you already know that
>>>> That P(P) of main() halts does not contradict H(P,P)==0.
>>>>
>>>> The only way that I can know that my words are clear enough to escalate
>>>> to the next level of actual computer scientist review when I mostly only
>>>> have God damned liars for reviewers is that their "rebuttals" become
>>>> ridiculously lame.
>>>>
>>>
>>> WRONG.
>>
>>
>> void Infinite_Loop()
>> {
>> Infinite_Loop();
>> }
>>
>> It is dead obvious that the first line of main() has different behavior
>> than the second line of main() even though the same function with the
>> same empty arguments is simulated / executed in both cases.
>>
>> From this we can deduce that every input that never halts will have
>> different behavior when simulated by a simulating halt decider that
>> recognizes its infinite behavior pattern than it would when directly
>> executed.
>>
>> I am going to stop here to see if this much is understood.
>>
>>
>
> And who ever said that the computation of H(P,I) was the same as the
> computation P(I). Only you seem to argue that strawmand.
>
If any pair of computations are computationally distinct then that can
H(P,P) of main() correctly decides that its input never halts because
these are two entirely different computations.
For six months people have been consistently pointing out a
"contradiction" that does not exist. This non-existent "contradiction"
has been their whole basis of rebuttal. While it seemed to be an actual
contradiction it seemed to be an actual rebuttal. Now that it is known
to not be a contradiction it is no longer any sort of rebuttal.
H1(P,P) of main() reports that its input does halt because it can see
that H(P,P) of P aborts its input.
H(P,P) of main sees that unless it aborts its simulation of P(P) that
P(P) will never halt. This is conclusively proved below to anyone that
can understand the technical details and wants an honest dialogue.
> The point everyone is making is that the answer that H(P,I) needs to
> correspond to the actual behavor of P(I).
>
> If P(I) Halts, then H(P,I) needs to return 1.
> If P(I) doesn't ever Halt, then H(P,I) needs to return 0.
>
> Since Infinite_Loop() never Hals, H(Infinite_Loop, 0) should return 0.
>
> Since H^(H^) DOES Halt, H(H^,H^) must return 1 to be right, but it
> returns 0.
>
> Note, a PARTIAL simulation may be finite when the machine is being
> simulated is infinite, because a partial simulation (like used by a
> smulating halt decider) doesn't fully repoduce the machine like a PURE
> simulation needs to.
>
> But, this does NOT mean that every simulation that a simulating halt
> decider aborts would be infinite if not aborted. The fact that this
> simulator aborted the simulation doesn't affact what the machine would
> do if run by itself.
>
> I think the one key thing you keep on missing is when you start to argue
> about the H^ machine is that when you look at varying the definition of
> H, to see what answer is right, you need to decide what problem you are
> going to be looking at. If you want to see if the answer H gave was
> right for a given H/H^ pair, than when you change H, you must not change
> the version of H that H^ is using. Thus we can replace the top level H
> with a UTM, but leave the H in H^ to still have its abort in it, to see
> that this H^ does Halt. (Which it does as long as H(H^,H^) returns 0)
>
> When you want to try to see if you can find an H that gives the right
> answer, then you do need to change the H that is inside H^, and you then
> need to compare the results of H(H^,H^) to what H^(H^) does.
>
> You will find two major cases for H. There are H's that don't abort the
> simulation of H^, these Hn, fail to decide on Hn(Hn^,Hn^) so are wrong,
> and it doesn't matter that Hn^(Hn^) doesn't halt.
>
> The second case are Ha's that do abort the simulation of Ha^ and say it
> is non-halting. For all of these Ha's, we find that Ha^(H^) will be
> halting, and thus Ha was wrong.
>
> You keep on trying to do logic where you look at Hn(Ha^,Ha^) or
> Ha(Hn^,Hn^) and in both of these cases, the H can give the right answer,
> but the problem isn't in the right form to be a counter. You need to get
> the decider to decide correctly on the ^ construction of itself, not
> some other version of the decider.
>
The bottom line is that this can be verified as correct entirely on the
basis of the meaning of its words by anyone wanting an actual honest
dialogue:
Simulating Halt Decider Theorem (Olcott 2020):
A simulating halt decider correctly decides that any input that never
halts unless the simulating halt decider aborts its simulation of this
input is an input that never halts.
Next we see if that criteria is met:
Simulating partial halt decider H correctly decides that P(P) never
halts (V1)
// 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)
Infinite recursion detection criteria:
If the execution trace of function X() called by function Y() shows:
(1) Function X() is called twice in sequence from the same machine
address of Y().
(2) With the same parameters to X().
(3) With no conditional branch or indexed jump instructions in Y().
(4) With no function call returns from X().
then the function call from Y() to X() is infinitely recursive.
When we apply the above criteria to the following execution trace we see
that it is met, conclusively proving that P never halts unless H aborts
its simulation of 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
[00000c68][0010172a][00000000] 83c408 add esp,+08
[00000c6b][00101726][00000000] 50 push eax
[00000c6c][00101722][00000357] 6857030000 push 00000357
[00000c71][00101722][00000357] e810f7ffff call 00000386
Input_Halts = 0
[00000c76][0010172a][00000000] 83c408 add esp,+08
[00000c79][0010172a][00000000] 33c0 xor eax,eax
[00000c7b][0010172e][00100000] 5d pop ebp
[00000c7c][00101732][00000068] c3 ret
Number_of_User_Instructions(27)
Number of Instructions Executed(23721)
Thus we have X > Y and Y > Z therefore X > AKA air tight proof.
> On 8/29/21 12:00 AM, olcott wrote:
>> On 8/28/2021 7:07 PM, Richard Damon wrote:
>>> On 8/28/21 7:51 PM, olcott wrote:
>>>
>>>>
>>>> I will take this to mean that you already know that
>>>> That P(P) of main() halts does not contradict H(P,P)==0.
>>>>
>>>> The only way that I can know that my words are clear enough to escalate
>>>> to the next level of actual computer scientist review when I mostly only
>>>> have God damned liars for reviewers is that their "rebuttals" become
>>>> ridiculously lame.
>>>>
>>>
>>> WRONG.
>>
>>
>> void Infinite_Loop()
>> {
>> HERE: goto HERE;
>> }
>>
>> int main()
>> {
>> H0((u32)Infinite_Loop);
>> }
>>
>> int main()
>> {
>> Infinite_Loop();
>> }
>>
>> It is dead obvious that the first line of main() has different behavior
>> than the second line of main() even though the same function with the
>> same empty arguments is simulated / executed in both cases.
>>
>> From this we can deduce that every input that never halts will have
>> different behavior when simulated by a simulating halt decider that
>> recognizes its infinite behavior pattern than it would when directly
>> executed.
>>
>> I am going to stop here to see if this much is understood.
>>
>>
>
> And who ever said that the computation of H(P,I) was the same as the
> computation P(I). Only you seem to argue that strawmand.
>
If any pair of computations are computationally distinct then that can
have different behavior without contradiction.
The fact that the P(P) of main() halts does not contradict the fact that
H(P,P) of main() correctly decides that its input never halts because
these are two entirely different computations.
For six months people have been consistently pointing out a
"contradiction" that does not exist. This non-existent "contradiction"
has been their whole basis of rebuttal. While it seemed to be an actual
contradiction it seemed to be an actual rebuttal. Now that it is known
to not be a contradiction it is no longer any sort of rebuttal.
H1(P,P) of main() reports that its input does halt because it can see
that H(P,P) of P aborts its input.
H(P,P) of main sees that unless it aborts its simulation of P(P) that
P(P) will never halt. This is conclusively proved below to anyone that
can understand the technical details and wants an honest dialogue.
> The point everyone is making is that the answer that H(P,I) needs to
> correspond to the actual behavor of P(I).
>
> If P(I) Halts, then H(P,I) needs to return 1.
> If P(I) doesn't ever Halt, then H(P,I) needs to return 0.
>
> Since Infinite_Loop() never Hals, H(Infinite_Loop, 0) should return 0.
>
> Since H^(H^) DOES Halt, H(H^,H^) must return 1 to be right, but it
> returns 0.
>
> Note, a PARTIAL simulation may be finite when the machine is being
> simulated is infinite, because a partial simulation (like used by a
> smulating halt decider) doesn't fully repoduce the machine like a PURE
> simulation needs to.
>
> But, this does NOT mean that every simulation that a simulating halt
> decider aborts would be infinite if not aborted. The fact that this
> simulator aborted the simulation doesn't affact what the machine would
> do if run by itself.
>
> I think the one key thing you keep on missing is when you start to argue
> about the H^ machine is that when you look at varying the definition of
> H, to see what answer is right, you need to decide what problem you are
> going to be looking at. If you want to see if the answer H gave was
> right for a given H/H^ pair, than when you change H, you must not change
> the version of H that H^ is using. Thus we can replace the top level H
> with a UTM, but leave the H in H^ to still have its abort in it, to see
> that this H^ does Halt. (Which it does as long as H(H^,H^) returns 0)
>
> When you want to try to see if you can find an H that gives the right
> answer, then you do need to change the H that is inside H^, and you then
> need to compare the results of H(H^,H^) to what H^(H^) does.
>
> You will find two major cases for H. There are H's that don't abort the
> simulation of H^, these Hn, fail to decide on Hn(Hn^,Hn^) so are wrong,
> and it doesn't matter that Hn^(Hn^) doesn't halt.
>
> The second case are Ha's that do abort the simulation of Ha^ and say it
> is non-halting. For all of these Ha's, we find that Ha^(H^) will be
> halting, and thus Ha was wrong.
>
> You keep on trying to do logic where you look at Hn(Ha^,Ha^) or
> Ha(Hn^,Hn^) and in both of these cases, the H can give the right answer,
> but the problem isn't in the right form to be a counter. You need to get
> the decider to decide correctly on the ^ construction of itself, not
> some other version of the decider.
>
The bottom line is that this can be verified as correct entirely on the
basis of the meaning of its words by anyone wanting an actual honest
dialogue:
Simulating Halt Decider Theorem (Olcott 2020):
A simulating halt decider correctly decides that any input that never
halts unless the simulating halt decider aborts its simulation of this
input is an input that never halts.
Next we see if that criteria is met:
Simulating partial halt decider H correctly decides that P(P) never
halts (V1)
// 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));
}
[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)
Infinite recursion detection criteria:
If the execution trace of function X() called by function Y() shows:
(1) Function X() is called twice in sequence from the same machine
address of Y().
(2) With the same parameters to X().
(3) With no conditional branch or indexed jump instructions in Y().
(4) With no function call returns from X().
then the function call from Y() to X() is infinitely recursive.
When we apply the above criteria to the following execution trace we see
that it is met, conclusively proving that P never halts unless H aborts
its simulation of 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
[00000c68][0010172a][00000000] 83c408 add esp,+08
[00000c6b][00101726][00000000] 50 push eax
[00000c6c][00101722][00000357] 6857030000 push 00000357
[00000c71][00101722][00000357] e810f7ffff call 00000386
Input_Halts = 0
[00000c76][0010172a][00000000] 83c408 add esp,+08
[00000c79][0010172a][00000000] 33c0 xor eax,eax
[00000c7b][0010172e][00100000] 5d pop ebp
[00000c7c][00101732][00000068] c3 ret
Number_of_User_Instructions(27)
Number of Instructions Executed(23721)
Thus we have X > Y and Y > Z therefore X > AKA air tight proof.
olcott
Aug 31, 2021, 12:00:56 AM8/31/21
to
On 8/30/2021 10:35 PM, André G. Isaak wrote:
> On 2021-08-30 21:20, olcott wrote:
>> On 8/30/2021 10:04 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 8/30/2021 9:17 PM, Ben Bacarisse wrote:
>>>>> olcott <No...@NoWhere.com> writes:
>>>>>
>>>>>> On 8/29/2021 7:00 PM, Ben Bacarisse wrote:
>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 8/29/2021 11:19 AM, Ben Bacarisse wrote:
>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> On 8/29/2021 10:20 AM, Ben Bacarisse wrote:
>>>>>>>>>>> halting
>>>>>>>>>>> computation P(P) "of main()"?
>>>>>>>>>>
>>>>>>>>>> That is already answered in the part that you snipped.
>>>>>>>>>
>>>>>>>>> No it was not. And if I am wrong, show the world that I am
>>>>>>>>> wrong by
>>>>>>>>> writing them again here. It can be no more that two simple C
>>>>>>>>> expressions.
>>>>>>>>
>>>>>>>> It is as I have said an airtight proof, notwithstanding false
>>>>>>>> assumptions to the contrary.
>>>>>>> No answer, as expected.
>>>>>>>
>>>>>>>> You can try to point to an actual error in the proof as its
>>>>>>>> stands and
>>>>>>>> everyone that sufficiently understands the material will see your
>>>>>>>> mistake.
>>>>>>> No answer, as expected.
>>>>>>>
>>>>>>>> It is the case that H(P,P) is a computation that never halts unless
>>>>>>>> its simulation is aborted. It is the case that every computation
>>>>>>>> that
>>>>>>>> never halts unless is simulation is aborted is a non halting
>>>>>>>> computation.
>>>>>>> No answer, as expected.
>>>>>>>
>>>>>>>> There is nothing besides carefully crafted double-talk that goes
>>>>>>>> against this.
>>>>>>> No answer, as expected.
>>>>>>
>>>>>> I will only answer questions that directly pertain to the points that
>>>>>> I made and will ignore dishonest dodges that attempt to change the
>>>>>> subject away from the points that I made.
>>>>> Dodge, dodge, dodge! All the questions you have been asked pertain
>>>>> directly to the nonsense you post.
>>>>
>>>> I am only discussing that
>>>> H(P,P)==0 is correct is a necessary consequence of its two premises.
>>>
>>> You seem to forget that I agree. H(P,P)==0 is correct given the
>>> criteria you have invented.
>>
>> {H(P,P)==0 is correct} means that the input to H(P,P) is correctly
>> decided as never halting.
>
> H(P, P) is required to answer the question Does P(P) halt"
>
> It is *specifically* being asked about the behaviour of int main() {
> P(P); }
>
> It is *not* being asked about the behaviour of P(P) "under the dominion
> of a halt decider" (whatever that may mean) nor about any computation
> other than int main() { P(P); }. This follows directly from how the
> halting problem is *defined*.
In computability theory, the halting problem is the
problem of determining, from a description of an
arbitrary computer program and an input, whether the
program will finish running, or continue to run forever.
https://en.wikipedia.org/wiki/Halting_problem
No that is not true. The halting problem is always about program
descriptions not running programs. This means that it is always about
the input to the halt decider not the direct execution of the program.
If the input to the halt decider never halts unless the halt decider
aborts its simulation of this input then its input never halts.
> since int main() { P(P); } halts, if your H(P, P) returns any answer
> other than 'true', it is wrong by the very definition of the problem.
>
> You can argue all you want that it is right about some *other* question,
> or about some computation *other* than int main() { P(P); }, but then it
> isn't answering the halting problem. It is answering something else, and
> unless you can provide some reason why anyone should care about that
> other problem I assure you no one will.
>
> André
> On 2021-08-30 21:20, olcott wrote:
>> On 8/30/2021 10:04 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 8/30/2021 9:17 PM, Ben Bacarisse wrote:
>>>>> olcott <No...@NoWhere.com> writes:
>>>>>
>>>>>> On 8/29/2021 7:00 PM, Ben Bacarisse wrote:
>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 8/29/2021 11:19 AM, Ben Bacarisse wrote:
>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> On 8/29/2021 10:20 AM, Ben Bacarisse wrote:
>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> The fact that the P(P) of main() halts does not contradict
>>>>>>>>>>>> the fact
>>>>>>>>>>>> that H(P,P) of main() correctly decides that its input never
>>>>>>>>>>>> halts
>>>>>>>>>>>> because these are two entirely different computations.
>>>>>>>>>>>
>>>>>>>>>>> What arguments must be passed to H for it to report on the
>>>>>>>>>>>
>>>>>>>>>>>> The fact that the P(P) of main() halts does not contradict
>>>>>>>>>>>> the fact
>>>>>>>>>>>> that H(P,P) of main() correctly decides that its input never
>>>>>>>>>>>> halts
>>>>>>>>>>>> because these are two entirely different computations.
>>>>>>>>>>>
>>>>>>>>>>> halting
>>>>>>>>>>> computation P(P) "of main()"?
>>>>>>>>>>
>>>>>>>>>> That is already answered in the part that you snipped.
>>>>>>>>>
>>>>>>>>> No it was not. And if I am wrong, show the world that I am
>>>>>>>>> wrong by
>>>>>>>>> writing them again here. It can be no more that two simple C
>>>>>>>>> expressions.
>>>>>>>>
>>>>>>>> It is as I have said an airtight proof, notwithstanding false
>>>>>>>> assumptions to the contrary.
>>>>>>> No answer, as expected.
>>>>>>>
>>>>>>>> You can try to point to an actual error in the proof as its
>>>>>>>> stands and
>>>>>>>> everyone that sufficiently understands the material will see your
>>>>>>>> mistake.
>>>>>>> No answer, as expected.
>>>>>>>
>>>>>>>> It is the case that H(P,P) is a computation that never halts unless
>>>>>>>> its simulation is aborted. It is the case that every computation
>>>>>>>> that
>>>>>>>> never halts unless is simulation is aborted is a non halting
>>>>>>>> computation.
>>>>>>> No answer, as expected.
>>>>>>>
>>>>>>>> There is nothing besides carefully crafted double-talk that goes
>>>>>>>> against this.
>>>>>>> No answer, as expected.
>>>>>>
>>>>>> I will only answer questions that directly pertain to the points that
>>>>>> I made and will ignore dishonest dodges that attempt to change the
>>>>>> subject away from the points that I made.
>>>>> Dodge, dodge, dodge! All the questions you have been asked pertain
>>>>> directly to the nonsense you post.
>>>>
>>>> I am only discussing that
>>>> H(P,P)==0 is correct is a necessary consequence of its two premises.
>>>
>>> You seem to forget that I agree. H(P,P)==0 is correct given the
>>> criteria you have invented.
>>
>> {H(P,P)==0 is correct} means that the input to H(P,P) is correctly
>> decided as never halting.
>
> H(P, P) is required to answer the question Does P(P) halt"
>
> It is *specifically* being asked about the behaviour of int main() {
> P(P); }
>
> It is *not* being asked about the behaviour of P(P) "under the dominion
> of a halt decider" (whatever that may mean) nor about any computation
> other than int main() { P(P); }. This follows directly from how the
> halting problem is *defined*.
In computability theory, the halting problem is the
problem of determining, from a description of an
arbitrary computer program and an input, whether the
program will finish running, or continue to run forever.
https://en.wikipedia.org/wiki/Halting_problem
No that is not true. The halting problem is always about program
descriptions not running programs. This means that it is always about
the input to the halt decider not the direct execution of the program.
If the input to the halt decider never halts unless the halt decider
aborts its simulation of this input then its input never halts.
> since int main() { P(P); } halts, if your H(P, P) returns any answer
> other than 'true', it is wrong by the very definition of the problem.
>
> You can argue all you want that it is right about some *other* question,
> or about some computation *other* than int main() { P(P); }, but then it
> isn't answering the halting problem. It is answering something else, and
> unless you can provide some reason why anyone should care about that
> other problem I assure you no one will.
>
> André
olcott
Aug 31, 2021, 10:25:04 AM8/31/21
to
On 8/30/2021 11:45 PM, André G. Isaak wrote:
> On 2021-08-30 22:31, olcott wrote:
>> On 8/30/2021 11:19 PM, André G. Isaak wrote:
>>> The *input* to the decider is a program description. But the question
>>> the halt decider is expected to answer is about the *actual* program
>>> which that description describes.
>>>
>>
>> In other words whether or not the the pure simulation of this
>> description halts on its input.
>
> No. The question is whether the *actual* computation described by the
> input halts.
description is to simulate it.
> A pure simulation would have identical halting behaviour as the actual
> computation, but the question isn't about simulations. It's about actual
> computations. It isn't about what happens inside some decider; it's
> about actual computations.
>
When an "actual computation" has different behavior than the simulation
of the input to the halt decider this proves that the actual computation
is a different computation than the input to the halt decider thus not
relevant to the halting problem.
> And since you claim that it has a *different* halting behaviour inside
> your halt decider, you aren't dealing with a pure simulation but
> something else. The correct answer to the question does P(P) halt is
> determined by the *actual* computation and *nothing* else.
>
In the case of the different between int main() { P(P); } and H(P,P) the
different behavior is accounted for by many differences between the two
computations.
We have this exact same issue of the difference between Ĥ applied to ⟨Ĥ⟩
and Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩.
int main() { P(P); } halts only because H(P,P) correctly decides that
its input never halts.
Ĥ applied to ⟨Ĥ⟩ halts only because Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩ correctly
decides that its input never halts.
There is a one way dependency relationship between
(a) int main() { P(P); } and H(P,P)
(b) Ĥ applied to ⟨Ĥ⟩ and Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩
that is the key difference making the pairs of similar looking
computations derive opposite results.
The key general principle is that distinct computations can have
opposite behavior without contradiction.
These pairs of distinct computations can have opposite behavior without
contradiction.
(a) int main() { P(P); } and H(P,P)
(b) Ĥ applied to ⟨Ĥ⟩ and Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩
>>>> If the input to the halt decider never halts unless the halt decider
>>>> aborts its simulation of this input then its input never halts.
>>>
>>> If P(P) halts, but the "simulation of P(P)" does not, then either
>>> your simulator is broken or whatever is being simulated by the
>>> decider *isn't* the the program which which was actually described by
>>> its input. It is therefore answering about the *wrong* program.
>>>
>>> André
>>>
>>
>> Like I said H(P,P)==0 is correct as a logical consequence of its two
>> premises and its two premises are true. There is no escape from this.
>
> You still haven't given your two premises.
>
> But it is entirely irrelevant anyways. As I said, the correct answer to
> the question does P(P) halt is determined by the *actual* computation
> and nothing else.
>
> It is not possible to prove that H(P,P)==0 given that this doesn't match
> the behaviour of the actual computation.
>
> If you want to claim that it is the correct answer to the question 'does
> P(P) 'under the dominion' of a simulating halt decider halt?' you can do
> that to your heart's content.
>
The actual computation must be at the same point in the execution trace
as the input to the halt decider. The only way to do this is to simulate
the input to the halt decider. Running the program at some other point
in the execution trace does not count because it defines a different
computation than the one under investigation.
int main() { P(P); } halts because of what H(P,P) does later on.
int main() { H(P,P); } halts because it aborts its simulation.
This proves that the above pair are different computations that can have
opposite behavior without contradiction.
In the above two computations the relative order of P(P) to H(P,P) is
reversed thus changing their relative placement in the execution trace
which changes their behavior.
> But that *isn't* the question which the halting problem asks, nor is it
> a question that anyone gives a damn about. It's basically just nonsense.
> On 2021-08-30 22:31, olcott wrote:
>> On 8/30/2021 11:19 PM, André G. Isaak wrote:
>>> the halt decider is expected to answer is about the *actual* program
>>> which that description describes.
>>>
>>
>> In other words whether or not the the pure simulation of this
>> description halts on its input.
>
> No. The question is whether the *actual* computation described by the
> input halts.
In computability theory, the halting problem is the
problem of determining, from a description of an
arbitrary computer program and an input, whether the
program will finish running, or continue to run forever.
https://en.wikipedia.org/wiki/Halting_problem
problem of determining, from a description of an
arbitrary computer program and an input, whether the
program will finish running, or continue to run forever.
https://en.wikipedia.org/wiki/Halting_problem
The halting problem is always about program descriptions
not running programs. This means that it is always about
the input to the halt decider not the direct execution
of the program.
The most straight forward way to get the actual behavior of a program
not running programs. This means that it is always about
the input to the halt decider not the direct execution
of the program.
description is to simulate it.
> A pure simulation would have identical halting behaviour as the actual
> computation, but the question isn't about simulations. It's about actual
> computations. It isn't about what happens inside some decider; it's
> about actual computations.
>
When an "actual computation" has different behavior than the simulation
of the input to the halt decider this proves that the actual computation
is a different computation than the input to the halt decider thus not
relevant to the halting problem.
> And since you claim that it has a *different* halting behaviour inside
> your halt decider, you aren't dealing with a pure simulation but
> something else. The correct answer to the question does P(P) halt is
> determined by the *actual* computation and *nothing* else.
>
In the case of the different between int main() { P(P); } and H(P,P) the
different behavior is accounted for by many differences between the two
computations.
We have this exact same issue of the difference between Ĥ applied to ⟨Ĥ⟩
and Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩.
int main() { P(P); } halts only because H(P,P) correctly decides that
its input never halts.
Ĥ applied to ⟨Ĥ⟩ halts only because Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩ correctly
decides that its input never halts.
There is a one way dependency relationship between
(a) int main() { P(P); } and H(P,P)
(b) Ĥ applied to ⟨Ĥ⟩ and Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩
that is the key difference making the pairs of similar looking
computations derive opposite results.
The key general principle is that distinct computations can have
opposite behavior without contradiction.
These pairs of distinct computations can have opposite behavior without
contradiction.
(a) int main() { P(P); } and H(P,P)
(b) Ĥ applied to ⟨Ĥ⟩ and Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩
>>>> If the input to the halt decider never halts unless the halt decider
>>>> aborts its simulation of this input then its input never halts.
>>>
>>> your simulator is broken or whatever is being simulated by the
>>> decider *isn't* the the program which which was actually described by
>>> its input. It is therefore answering about the *wrong* program.
>>>
>>> André
>>>
>>
>> Like I said H(P,P)==0 is correct as a logical consequence of its two
>> premises and its two premises are true. There is no escape from this.
>
> You still haven't given your two premises.
>
> But it is entirely irrelevant anyways. As I said, the correct answer to
> the question does P(P) halt is determined by the *actual* computation
> and nothing else.
>
> It is not possible to prove that H(P,P)==0 given that this doesn't match
> the behaviour of the actual computation.
>
> If you want to claim that it is the correct answer to the question 'does
> P(P) 'under the dominion' of a simulating halt decider halt?' you can do
> that to your heart's content.
>
The actual computation must be at the same point in the execution trace
as the input to the halt decider. The only way to do this is to simulate
the input to the halt decider. Running the program at some other point
in the execution trace does not count because it defines a different
computation than the one under investigation.
int main() { P(P); } halts because of what H(P,P) does later on.
int main() { H(P,P); } halts because it aborts its simulation.
This proves that the above pair are different computations that can have
opposite behavior without contradiction.
In the above two computations the relative order of P(P) to H(P,P) is
reversed thus changing their relative placement in the execution trace
which changes their behavior.
> But that *isn't* the question which the halting problem asks, nor is it
> a question that anyone gives a damn about. It's basically just nonsense.
olcott
Aug 31, 2021, 12:08:14 PM8/31/21
to
On 8/31/2021 10:07 AM, André G. Isaak wrote:
> simply data. Data doesn't *have* halting behaviour. Only the actual
> computation described by that data can have halting behaviour. Your
> inability to comprehend simple definitions is not the basis for a
> coherent argument.
> the actual behaviour of a program description is to run the program it
> describes.
> not an accurate simulation.
>
> André
>
I think that I finally got it this time:
The difference in the relative invocation order of P(P) to H(P,P)
accounts for the difference in behavior.
P(P) from main() invokes P(P) then H(P,P).
H(P,P) from main reverses this relative invocation order to H(P,P) then
P(P).
Changes to the relative invocation order define distinctly different
computations that can have different behavior without contradiction.
> On 2021-08-31 08:24, olcott wrote:
>> On 8/30/2021 11:45 PM, André G. Isaak wrote:
>
>> In computability theory, the halting problem is the
>> problem of determining, from a description of an
>> arbitrary computer program and an input, whether the
>> program will finish running, or continue to run forever.
>> https://en.wikipedia.org/wiki/Halting_problem
>>
>> The halting problem is always about program descriptions
>> not running programs. This means that it is always about
>> the input to the halt decider not the direct execution
>> of the program.
>
> This is, of course, errant nonsense. The input to a halt decider is
>> On 8/30/2021 11:45 PM, André G. Isaak wrote:
>
>> In computability theory, the halting problem is the
>> problem of determining, from a description of an
>> arbitrary computer program and an input, whether the
>> program will finish running, or continue to run forever.
>> https://en.wikipedia.org/wiki/Halting_problem
>>
>> The halting problem is always about program descriptions
>> not running programs. This means that it is always about
>> the input to the halt decider not the direct execution
>> of the program.
>
> simply data. Data doesn't *have* halting behaviour. Only the actual
> computation described by that data can have halting behaviour. Your
> inability to comprehend simple definitions is not the basis for a
> coherent argument.
>
>
>> The most straight forward way to get the actual behavior of a program
>> description is to simulate it.
>
> No. The most straightforward way, and the ONLY 100% reliable way to get
>
>> The most straight forward way to get the actual behavior of a program
>> description is to simulate it.
>
> the actual behaviour of a program description is to run the program it
> describes.
>
>>> A pure simulation would have identical halting behaviour as the
>>> actual computation, but the question isn't about simulations. It's
>>> about actual computations. It isn't about what happens inside some
>>> decider; it's about actual computations.
>>>
>>
>> When an "actual computation" has different behavior than the
>> simulation of the input to the halt decider this proves that the
>> actual computation is a different computation than the input to the
>> halt decider thus not relevant to the halting problem.
>
> No, it proves that the 'simulation' performed by your halt decider is
>>> A pure simulation would have identical halting behaviour as the
>>> actual computation, but the question isn't about simulations. It's
>>> about actual computations. It isn't about what happens inside some
>>> decider; it's about actual computations.
>>>
>>
>> When an "actual computation" has different behavior than the
>> simulation of the input to the halt decider this proves that the
>> actual computation is a different computation than the input to the
>> halt decider thus not relevant to the halting problem.
>
> not an accurate simulation.
>
> André
>
I think that I finally got it this time:
The difference in the relative invocation order of P(P) to H(P,P)
accounts for the difference in behavior.
P(P) from main() invokes P(P) then H(P,P).
H(P,P) from main reverses this relative invocation order to H(P,P) then
P(P).
Changes to the relative invocation order define distinctly different
computations that can have different behavior without contradiction.
olcott
Aug 31, 2021, 5:48:30 PM8/31/21
to
On 8/31/2021 4:17 PM, Malcolm McLean wrote:
> On Tuesday, 31 August 2021 at 20:11:39 UTC+1, olcott wrote:
>> On 8/31/2021 1:40 PM, André G. Isaak wrote:
>>
>>>
>>> It makes no reference at all to the "relative invocation order" of H
>>> with respect to P. It makes no reference to H at all.
>>>
>>> If its answer doesn't correspond to the behaviour of P(P) which is a
>>> halting computation, then its answer is *wrong*.
>> H(P,P) specifies the invocation order of H(P,P) then P(P).
>>
>> If P did not have the pathological self-reference error the invocation
>> would not matter. Because P does have the pathological self-reference
>> error the invocation order does matter.
>>
>> It is very diffcult to correctly handle incorrect input.
>>
>> The key irrefutable point is that H(P,P) then P(P) is an entirely
>> different computation than P(P) then H(P,P)
>>
> So that's the central point. If H(P,P) from the root is a different computation
> to H(P,P),called from P, then indeed you can provide a counter-example to
> the Linz proof.
// opposite results without contradiction.
int main () { H(P,P); } // invocation order H(P,P) then P(P)
int main () { P(P); } // invocation order P(P) then H(P,P)
H(P,P) from anywhere has exactly the same behavior.
// H1 is an identical copy of H
int main () { H1(P,P); } // reports that its input halts.
The different invocation order of H1 and H is how they can have
identical code and different behavior. Halt deciders can only see the
instructions that they (and their slave instances) simulate. H1 cannot
see any of the instructions that H simulates.
H(P,P); P(P); and H1(P,P); are shown in sections V1,V2,V3 of this paper:
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
> On Tuesday, 31 August 2021 at 20:11:39 UTC+1, olcott wrote:
>> On 8/31/2021 1:40 PM, André G. Isaak wrote:
>>
>>>
>>> It makes no reference at all to the "relative invocation order" of H
>>> with respect to P. It makes no reference to H at all.
>>>
>>> If its answer doesn't correspond to the behaviour of P(P) which is a
>>> halting computation, then its answer is *wrong*.
>> H(P,P) specifies the invocation order of H(P,P) then P(P).
>>
>> If P did not have the pathological self-reference error the invocation
>> would not matter. Because P does have the pathological self-reference
>> error the invocation order does matter.
>>
>> It is very diffcult to correctly handle incorrect input.
>>
>> The key irrefutable point is that H(P,P) then P(P) is an entirely
>> different computation than P(P) then H(P,P)
>>
> So that's the central point. If H(P,P) from the root is a different computation
> to H(P,P),called from P, then indeed you can provide a counter-example to
> the Linz proof.
>
// Simplified Linz Ĥ (Linz:1990:319)
// Strachey(1965) CPL translated to C
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
// These are two different computations that can have
// Simplified Linz Ĥ (Linz:1990:319)
// Strachey(1965) CPL translated to C
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}
// opposite results without contradiction.
int main () { H(P,P); } // invocation order H(P,P) then P(P)
int main () { P(P); } // invocation order P(P) then H(P,P)
H(P,P) from anywhere has exactly the same behavior.
// H1 is an identical copy of H
int main () { H1(P,P); } // reports that its input halts.
The different invocation order of H1 and H is how they can have
identical code and different behavior. Halt deciders can only see the
instructions that they (and their slave instances) simulate. H1 cannot
see any of the instructions that H simulates.
H(P,P); P(P); and H1(P,P); are shown in sections V1,V2,V3 of this paper:
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
0 new messages