How is H(P,P)==0 correct even though P(P) stops running?

3 views
Skip to first unread message

olcott

unread,
Jul 22, 2021, 11:51:31 AMJul 22
to
How is H(P,P)==0 correct even though P(P) stops running?

(a) The reason that P of int main(){ P(P); } it is construed as halting
is that it reaches its final state.

(b) The reason that it reaches its final state is that H(P,P) returns zero.

(c) The reason that H(P,P) returns zero is that the correct pure
simulation of its input can't possibly reach its final state.

(d) When the pure simulation of an input can't possibly ever reach its
final state then this input never halts.

∴ The only reason that P of int main(){ P(P); } halts is because H(P,P)
correctly decided that its input never halts.

We can easily verify that the simulation of P(P) is correct by comparing
the execution trace of this simulation to the x86 source-code of P shown
below.

(c) is proved in that when P calls H and H acts as a pure simulator of
P(P) it is very obvious that P(P) is stuck in infinitely nested
simulation when we examine the execution trace of the simulation of P(P)
shown below:

// Strachey(1965) "An impossible program"
// CPL translated to C
// https://doi.org/10.1093/comjnl/7.4.313
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}

int main()
{
P((u32)P);
}

_P()
[00000c25](01) 55 push ebp
[00000c26](02) 8bec mov ebp,esp
[00000c28](03) 8b4508 mov eax,[ebp+08]
[00000c2b](01) 50 push eax // 2nd Param
[00000c2c](03) 8b4d08 mov ecx,[ebp+08]
[00000c2f](01) 51 push ecx // 1st Param
[00000c30](05) e820fdffff call 00000955 // call H
[00000c35](03) 83c408 add esp,+08
[00000c38](02) 85c0 test eax,eax
[00000c3a](02) 7402 jz 00000c3e
[00000c3c](02) ebfe jmp 00000c3c
[00000c3e](01) 5d pop ebp
[00000c3f](01) c3 ret
Size in bytes:(0027) [00000c3f]

_main()
[00000c45](01) 55 push ebp
[00000c46](02) 8bec mov ebp,esp
[00000c48](05) 68250c0000 push 00000c25 // push P
[00000c4d](05) e8d3ffffff call 00000c25 // call P
[00000c52](03) 83c404 add esp,+04
[00000c55](02) 33c0 xor eax,eax
[00000c57](01) 5d pop ebp
[00000c58](01) c3 ret
Size in bytes:(0020) [00000c58]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
[00000c45][001016d6][00000000] 55 push ebp
[00000c46][001016d6][00000000] 8bec mov ebp,esp
[00000c48][001016d2][00000c25] 68250c0000 push 00000c25 // push P
[00000c4d][001016ce][00000c52] e8d3ffffff call 00000c25 // call P0
[00000c25][001016ca][001016d6] 55 push ebp // P0 begins
[00000c26][001016ca][001016d6] 8bec mov ebp,esp
[00000c28][001016ca][001016d6] 8b4508 mov eax,[ebp+08]
[00000c2b][001016c6][00000c25] 50 push eax // push P
[00000c2c][001016c6][00000c25] 8b4d08 mov ecx,[ebp+08]
[00000c2f][001016c2][00000c25] 51 push ecx // push P
[00000c30][001016be][00000c35] e820fdffff call 00000955 // call H0

Begin Local Halt Decider Simulation at Machine Address:c25
[00000c25][00211776][0021177a] 55 push ebp // P1 begins
[00000c26][00211776][0021177a] 8bec mov ebp,esp
[00000c28][00211776][0021177a] 8b4508 mov eax,[ebp+08]
[00000c2b][00211772][00000c25] 50 push eax // push P
[00000c2c][00211772][00000c25] 8b4d08 mov ecx,[ebp+08]
[00000c2f][0021176e][00000c25] 51 push ecx // push P
[00000c30][0021176a][00000c35] e820fdffff call 00000955 // call H1
[00000c25][0025c19e][0025c1a2] 55 push ebp // P2 begins
[00000c26][0025c19e][0025c1a2] 8bec mov ebp,esp
[00000c28][0025c19e][0025c1a2] 8b4508 mov eax,[ebp+08]
[00000c2b][0025c19a][00000c25] 50 push eax // push P
[00000c2c][0025c19a][00000c25] 8b4d08 mov ecx,[ebp+08]
[00000c2f][0025c196][00000c25] 51 push ecx // push P
[00000c30][0025c192][00000c35] e820fdffff call 00000955 // call H2
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

In the above computation (zero based addressing) H0 aborts P1.

[00000c35][001016ca][001016d6] 83c408 add esp,+08
[00000c38][001016ca][001016d6] 85c0 test eax,eax
[00000c3a][001016ca][001016d6] 7402 jz 00000c3e
[00000c3e][001016ce][00000c52] 5d pop ebp
[00000c3f][001016d2][00000c25] c3 ret
[00000c52][001016d6][00000000] 83c404 add esp,+04
[00000c55][001016d6][00000000] 33c0 xor eax,eax
[00000c57][001016da][00100000] 5d pop ebp
[00000c58][001016de][00000084] c3 ret
Number_of_User_Instructions(34)
Number of Instructions Executed(23729)

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

unread,
Jul 22, 2021, 12:15:15 PMJul 22
to
On 7/22/2021 10:51 AM, olcott wrote:
> How is H(P,P)==0 correct even though P(P) stops running?
>
> (a) The reason that P of int main(){ P(P); } it is construed as halting
> is that it reaches its final state.
>
> (b) The reason that it reaches its final state is that H(P,P) returns zero.
>
> (c) The reason that H(P,P) returns zero is that the correct pure
> simulation of its input can't possibly reach its final state.
>

We can easily verify that the pure simulation of the input to
H(P,P) is correct when we verify that the execution trace of
the simulation of P(P) precisely corresponds to the x86
source-code of P.

We can easily verify that the pure simulation of the input to
H(P,P) never reaches the final state of P by examining the
execution trace of the simulation of P(P) under the assumption
that the call to H at machine address 0x955 is a call to a pure
x86 emulator.

We can know that this assumption is valid because we know that H
is computationally equivalent to a pure simulator of its input
until after it makes its halt status decision.

olcott

unread,
Jul 22, 2021, 2:16:16 PMJul 22
to
On 7/22/2021 12:34 PM, Malcolm McLean wrote:
> On Thursday, 22 July 2021 at 16:51:31 UTC+1, olcott wrote:
>> How is H(P,P)==0 correct even though P(P) stops running?
>>
>> (a) The reason that P of int main(){ P(P); } it is construed as halting
>> is that it reaches its final state.
>>
>> (b) The reason that it reaches its final state is that H(P,P) returns zero.
>>
>> (c) The reason that H(P,P) returns zero is that the correct pure
>> simulation of its input can't possibly reach its final state.
>>
>> (d) When the pure simulation of an input can't possibly ever reach its
>> final state then this input never halts.
>>
>> ∴ The only reason that P of int main(){ P(P); } halts is because H(P,P)
>> correctly decided that its input never halts.
>>
>> We can easily verify that the simulation of P(P) is correct by comparing
>> the execution trace of this simulation to the x86 source-code of P shown
>> below.
>>
>> (c) is proved in that when P calls H and H acts as a pure simulator of
>> P(P) it is very obvious that P(P) is stuck in infinitely nested
>> simulation when we examine the execution trace of the simulation of P(P)
>> shown below:
>>
> You've constructed your own paradox which has nothing to do with the
> "invert" logic of the Linz proof.
>

It uses the same "do the opposite of whatever the halt decider decides"
basis of all of the conventional proofs.

// Strachey(1965) "An impossible program"
// CPL translated to C
// https://doi.org/10.1093/comjnl/7.4.313
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}

> If H is a simulating halt decider, and it is called on a version of itself, it
> either detects that this will go on forever, or it doesn't. If it doesn't detect
> that this will go on forever, there is nothing to stop the endless spawning
> of "H" contexts, and the program never halts. So H has it wrong. However if
> H detects the situation and terminates, the the program comes to a halt,
> and H was also wrong.

Only because H[0] correctly decides that the pure simulation of P[1]
can't possibly reach its final state does P[0] ever halt.

_P()
[00000c25](01) 55 push ebp
[00000c26](02) 8bec mov ebp,esp
[00000c28](03) 8b4508 mov eax,[ebp+08]
[00000c2b](01) 50 push eax // 2nd Param
[00000c2c](03) 8b4d08 mov ecx,[ebp+08]
[00000c2f](01) 51 push ecx // 1st Param
[00000c30](05) e820fdffff call 00000955 // call H
[00000c35](03) 83c408 add esp,+08
[00000c38](02) 85c0 test eax,eax
[00000c3a](02) 7402 jz 00000c3e
[00000c3c](02) ebfe jmp 00000c3c
[00000c3e](01) 5d pop ebp
[00000c3f](01) c3 ret
Size in bytes:(0027) [00000c3f]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
Begin Local Halt Decider Simulation at Machine Address:c25
[00000c25][00211776][0021177a] 55 push ebp // P1 begins
[00000c26][00211776][0021177a] 8bec mov ebp,esp
[00000c28][00211776][0021177a] 8b4508 mov eax,[ebp+08]
[00000c2b][00211772][00000c25] 50 push eax // push P
[00000c2c][00211772][00000c25] 8b4d08 mov ecx,[ebp+08]
[00000c2f][0021176e][00000c25] 51 push ecx // push P
[00000c30][0021176a][00000c35] e820fdffff call 00000955 // call H1
[00000c25][0025c19e][0025c1a2] 55 push ebp // P2 begins
[00000c26][0025c19e][0025c1a2] 8bec mov ebp,esp
[00000c28][0025c19e][0025c1a2] 8b4508 mov eax,[ebp+08]
[00000c2b][0025c19a][00000c25] 50 push eax // push P
[00000c2c][0025c19a][00000c25] 8b4d08 mov ecx,[ebp+08]
[00000c2f][0025c196][00000c25] 51 push ecx // push P
[00000c30][0025c192][00000c35] e820fdffff call 00000955 // call H2
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

https://www.researchgate.net/profile/Pl-Olcott/research

>
> There might be something useful here.

olcott

unread,
Jul 22, 2021, 3:18:04 PMJul 22
to
On 7/22/2021 1:30 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> How is H(P,P)==0 correct even though P(P) stops running?
>
> Because H is not a halt decider. You've been clear that H does not
> compute the halting function. If it did, H(P, I) == 0 would be correct
> only when P(I) does not stop running.
>
> This is the pinnacle of your 17 years of "work" on halting?
>
> Seriously, go walk a shelter dog.
>

The original post shows P[1] as P1 and such because the original source
of this original post has formatted text equivalent to: P<sub>1</sub>

The fact that P[0] Only halts because H(P[1],P[1]) was correctly decided
as not halting and that P[0] would never halt unless P[1] has been
aborted conclusively proves that H does correctly decide that its input
never halts.

olcott

unread,
Jul 22, 2021, 6:18:56 PMJul 22
to
On 7/22/2021 2:11 PM, André G. Isaak wrote:
> On 2021-07-22 09:51, olcott wrote:
>> How is H(P,P)==0 correct even though P(P) stops running?
>>
>> (a) The reason that P of int main(){ P(P); } it is construed as
>> halting is that it reaches its final state.
>>
>> (b) The reason that it reaches its final state is that H(P,P) returns
>> zero.
>>
>> (c) The reason that H(P,P) returns zero is that the correct pure
>> simulation of its input can't possibly reach its final state.
>>
>> (d) When the pure simulation of an input can't possibly ever reach its
>> final state then this input never halts.
>
> A 'pure simulation' of its inputs is NOT what you describe below. A pure
> simulation of P(P) behaves *identically* to P(P). They both halt (see
> below for explanation).
>

*Pathological Input* to a halt decider is defined as any input that was
defined to do the opposite of whatever its corresponding halt decider
decides.

Now we construct a new Turing machine D with H as a subroutine.
This new TM calls H to determine what M does when the input to
M is its own description ⟨M⟩. Once D has determined this information,
it does the opposite. (Sipser:1997:165)

This question can only be correctly answered after the pathology has
been removed. When a halt decider only acts as a pure simulator of its
input until after its halt status decision is made there is no feedback
loop of back channel communication between the halt decider and its
input that can prevent a correct halt status decision.

It can be seen that while H(P,P) acts as a pure x86 emulator of its
input that its input cannot possibly reach its final state.

>> ∴ The only reason that P of int main(){ P(P); } halts is because
>> H(P,P) correctly decided that its input never halts.
>
> When run independently H(P,P) isn't even being computed. If you are
> referring to the *internal* copy of H contained in P, then that
> *incorrectly* decided that its input never halts.
>

You keep ignoring the key fact that unless some H aborts some P int
main() { P(P); } never halts. This proves that when H[0] aborts the
simulation of P[1] that it was necessarily correct to the same degree
that we know that 2 == 2 is correct.

>> We can easily verify that the simulation of P(P) is correct by
>> comparing the execution trace of this simulation to the x86
>> source-code of P shown below.
>>
>> (c) is proved in that when P calls H and H acts as a pure simulator of
>> P(P) it is very obvious that P(P) is stuck in infinitely nested
>> simulation when we examine the execution trace of the simulation of
>> P(P) shown below:
>
> Here you're just being idiotic. This error has been pointed out to you
> so many times that you cannot possibly not see it by now.
>
> A 'pure simulation' of P(P) involves passing the description of P, P to
> some pure simulator. It DOES NOT involve taking P and changing its
> internal code so that its copy of H acts as a simulator rather than a
> halt decider.
>
> If you do that you are *not* simulating the input which you gave to H(P,
> P). You are simulating some entirely different computation (call it
> PBroken) whose halting status has absolutely no bearing on the
> computation under consideration.
>
> When S is a pure simulator, S(P, P) completes its simulation and that
> simulation reaches one of its final states. IOW, it halts, just like
> P(P) halts when run as an independent computation.
>
> S(PBroken, PBroken) won't halt any more than PBroken(PBroken) will, but
> that is an entirely different computation from the one which H is being
> asked about. Talking about it has no relevance to anything.
>
> André

olcott

unread,
Jul 22, 2021, 7:25:40 PMJul 22
to
On 7/22/2021 6:04 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 7/22/2021 1:30 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> How is H(P,P)==0 correct even though P(P) stops running?
>>> Because H is not a halt decider. You've been clear that H does not
>>> compute the halting function. If it did, H(P, I) == 0 would be correct
>>> only when P(I) does not stop running.
>>> This is the pinnacle of your 17 years of "work" on halting?
>>> Seriously, go walk a shelter dog.
>>
>> The fact that P[0] Only halts because H(P[1],P[1]) was correctly
>> decided as not halting
>
> Stupid smoke and mirrors. P(P) halts. The reason does not matter. H
> does not compute the halting function because H(P, P) == 0. What else
> do you have?
>

int main() { P(P); } only halts because H(P,P) correctly determines that
its input cannot possibly reach its final state.

olcott

unread,
Jul 23, 2021, 9:53:47 AMJul 23
to
On 7/22/2021 6:48 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 7/22/2021 6:04 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 7/22/2021 1:30 PM, Ben Bacarisse wrote:
>>>>> olcott <No...@NoWhere.com> writes:
>>>>>
>>>>>> How is H(P,P)==0 correct even though P(P) stops running?
>>>>> Because H is not a halt decider. You've been clear that H does not
>>>>> compute the halting function. If it did, H(P, I) == 0 would be correct
>>>>> only when P(I) does not stop running.
>>>>> This is the pinnacle of your 17 years of "work" on halting?
>>>>> Seriously, go walk a shelter dog.
>>>>
>>>> The fact that P[0] Only halts because H(P[1],P[1]) was correctly
>>>> decided as not halting
>>> Stupid smoke and mirrors. P(P) halts. The reason does not matter. H
>>> does not compute the halting function because H(P, P) == 0. What else
>>> do you have?
>>
>> int main() { P(P); } only halts because H(P,P) correctly determines
>> that its input cannot possibly reach its final state.
>
> For H to be halt decider, H(P,I) == 0 only for computations P(I) that
> don't halt. You know this. H is not deciding halting, it's deciding
> something else you refuse to give a name to.
>

Because we know that the simulation of a machine on its input is
equivalent to the execution of this machine on its input we know that
when the pure simulation of P on its input never halts that P never halts.

int main() { P(P); } only halts because H(P,P) correctly determines that
its input cannot possibly reach its final state.

> (a) P(P) halts.
> (b) H(P,P) == 0.
> (c) H(P, I) == 0 is only correct if P(I) does not halt.
>
> You don't accept (c). No amount of waffle about P(P) "only" halting
> because reason, will alter what the right answer is.
>

I understand that you have no problem with contradicting yourself as
long as it supports your goal of staying focused on rebuttal no matter
what the truth is:

On 5/11/2021 11:10 AM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> Truism:
>> Every simulation that would never stop unless Halts() stops
>> it at some point specifies infinite execution.
>
> Any algorithm that implements this truism is, of course, a halting
> decider.

Unless H[0] aborts P[1] int main(){ P(P); } never halts proving that
H[0](P[1], P[1])==0 is correct according to the criteria that you agreed
to.

olcott

unread,
Jul 23, 2021, 10:35:40 AMJul 23
to
On 7/22/2021 6:08 PM, André G. Isaak wrote:
> On 2021-07-22 16:18, olcott wrote:
>> On 7/22/2021 2:11 PM, André G. Isaak wrote:
>>> On 2021-07-22 09:51, olcott wrote:
>>>> How is H(P,P)==0 correct even though P(P) stops running?
>>>>
>>>> (a) The reason that P of int main(){ P(P); } it is construed as
>>>> halting is that it reaches its final state.
>>>>
>>>> (b) The reason that it reaches its final state is that H(P,P)
>>>> returns zero.
>>>>
>>>> (c) The reason that H(P,P) returns zero is that the correct pure
>>>> simulation of its input can't possibly reach its final state.
>>>>
>>>> (d) When the pure simulation of an input can't possibly ever reach
>>>> its final state then this input never halts.
>>>
>>> A 'pure simulation' of its inputs is NOT what you describe below. A
>>> pure simulation of P(P) behaves *identically* to P(P). They both halt
>>> (see below for explanation).
>>>
>>
>> *Pathological Input* to a halt decider is defined as any input that
>> was defined to do the opposite of whatever its corresponding halt
>> decider decides.
>
> There's nothing "pathological" about the transformation which derives
> H_Hat from H. And you cannot formally define something in terms of the
> "intent" of the designer. That simply isn't present in a Turing Machine.
> H_Hat is simply an algorithm that does what it does.
>

When I use the term *Pathological Input* I am only applying a name to
the case that Sipser describes and Strachey encodes.

>> Now we construct a new Turing machine D with H as a subroutine.
>> This new TM calls H to determine what M does when the input to
>> M is its own description ⟨M⟩. Once D has determined this information,
>> it does the opposite. (Sipser:1997:165)
>>

Here are Strachey's (verbatim) own words
Suppose T[R] is a Boolean function taking a routine
(or program) R with no formal or free variables as its
argument and that for all R, T[R] — True if R terminates
if run and that T[R] = False if R does not terminate.
Consider the routine P defined as follows

rec routine P
§L:if T[P] go to L
Return §

If T[P] = True the routine P will loop, and it will
only terminate if T[P] = False. In each case T[P] has
exactly the wrong value, and this contradiction shows
that the function T cannot exist.

// Strachey(1965) "An impossible program"
// CPL translated to C
// https://doi.org/10.1093/comjnl/7.4.313
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}

>> This question can only be correctly answered after the pathology has
>> been removed. When a halt decider only acts as a pure simulator of its
>> input until after its halt status decision is made there is no
>> feedback loop of back channel communication between the halt decider
>> and its input that can prevent a correct halt status decision.
>>
>> It can be seen that while H(P,P) acts as a pure x86 emulator of its
>> input that its input cannot possibly reach its final state.
>
> You need to stop conflating the Halt decider H with the *copy* of H
> inside of P. They are not the same thing.
>

I will not address your diversions from the essence of what I am saying.
There is no copy of H, H is a single machine-code function. Ben has used
distraction away form the essence of what I am saying as his primary
"rebuttal" tactic. When he knows that what I say is correct he changes
the subject, I cannot afford to tolerate that.

> You really don't seem to grasp how P is supposed to be derived.
>
> We start by making a *copy* of all of the state transitions of H. We
> then prepend a number of transitions to the beginning of this which
> duplicates the input string. Finally, we remove one of the final states
> of the original H (meaning it is no longer H) and replace that with two
> states which loop indefinitely.
>
> What we now have is a *single* TM P which exists *entirely independent*
> of H and which performs a computation entirely distinct from H. It
> doesn't 'call' H since that is not possible for Turing machines. It
> would really be best to not even talk about the 'embedded H' since this
> isn't really a halt decider anymore; it's just one portion of the state
> transitions of P. Moreover, P(P) must be able to run on a system in
> which H is entirely absent (or at least a C 'implementation' of it must
> -- there is no 'system' where TMs are concerned). There can be no
> dependency between H and P since they are *separate* TMs.
>
> Any discussion about the halt decider should be referring *only* to H
> and not to *anything* that goes on inside the simulation of its input P
> since that is not a halt decider at all. it is part of the input
> computation, and P does not purport to answer questions about halting.
> It does not purport to answer any question at all.
>
>>>> ∴ The only reason that P of int main(){ P(P); } halts is because
>>>> H(P,P) correctly decided that its input never halts.
>>>
>>> When run independently H(P,P) isn't even being computed. If you are
>>> referring to the *internal* copy of H contained in P, then that
>>> *incorrectly* decided that its input never halts.
>>>
>>
>> You keep ignoring the key fact that unless some H aborts some P int
>> main() { P(P); } never halts. This proves that when H[0] aborts the
>> simulation of P[1] that it was necessarily correct to the same degree
>> that we know that 2 == 2 is correct.
>
> But there really only is one H when you run H(P, P). Everything else is
> part of the input P. And H does *not* need to abort P(P), because P(P)
> *as you have already admitted* does reach a final state.

olcott

unread,
Jul 24, 2021, 1:11:55 AMJul 24
to
On 7/22/2021 12:34 PM, Malcolm McLean wrote:
> On Thursday, 22 July 2021 at 16:51:31 UTC+1, olcott wrote:
>> How is H(P,P)==0 correct even though P(P) stops running?
>>
>> (a) The reason that P of int main(){ P(P); } it is construed as halting
>> is that it reaches its final state.
>>
>> (b) The reason that it reaches its final state is that H(P,P) returns zero.
>>
>> (c) The reason that H(P,P) returns zero is that the correct pure
>> simulation of its input can't possibly reach its final state.
>>
>> (d) When the pure simulation of an input can't possibly ever reach its
>> final state then this input never halts.
>>
>> ∴ The only reason that P of int main(){ P(P); } halts is because H(P,P)
>> correctly decided that its input never halts.
>>
>> We can easily verify that the simulation of P(P) is correct by comparing
>> the execution trace of this simulation to the x86 source-code of P shown
>> below.
>>
>> (c) is proved in that when P calls H and H acts as a pure simulator of
>> P(P) it is very obvious that P(P) is stuck in infinitely nested
>> simulation when we examine the execution trace of the simulation of P(P)
>> shown below:
>>
> You've constructed your own paradox which has nothing to do with the
> "invert" logic of the Linz proof.
>
> If H is a simulating halt decider, and it is called on a version of itself, it
> either detects that this will go on forever, or it doesn't. If it doesn't detect
> that this will go on forever, there is nothing to stop the endless spawning
> of "H" contexts, and the program never halts. So H has it wrong. However if
> H detects the situation and terminates, the the program comes to a halt,
> and H was also wrong.
>
> There might be something useful here.
>

The only reason why int main(){ P(P); } ever halts is that the
subsequent P(P) can be examined by the simulating halt decider and
determined to never reach its final state. H aborts it on this basis.

olcott

unread,
Jul 24, 2021, 9:51:12 AMJul 24
to
On 7/24/2021 5:56 AM, Malcolm McLean wrote:
> On Saturday, 24 July 2021 at 00:49:43 UTC+1, André G. Isaak wrote:
>> On 2021-07-23 14:56, olcott wrote:
>>
>>> The P in main() is hidden from H that is why it wrongly halts.
>>> int main(){ P(P); }
>> Nothing is being 'hidden' from H. H isn't even running.
>>
> It at least one version of this work, "H" is the operating system.
>

That one correctly decides that int main(){ P(P); } never halts.

> It's quite a clever idea. A simulating halt decider can also be used
> as a host system for Turing machines. Instead of user having to
> terminate them manually, the system culls them when they get into
> fixed loops which indicate non-halting behaviour.
>
> It's not really a refutation of Linz, of course.
>

Linz has the same sort of infinitely repeating pattern that can be
recognized on the basis that a copies of the exact same TM description
are being infinitely simulated.

This is easier to see when the infinite cycle in its execution trace is
graphed in Figure 12.4 in my paper:

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

olcott

unread,
Jul 24, 2021, 9:55:55 AMJul 24
to
On 7/24/2021 6:40 AM, Andy Walker wrote:
> On 24/07/2021 11:56, Malcolm McLean wrote:
>> [...]  Instead of user having to
>> terminate them manually, the system culls them when they get into
>> fixed loops which indicate non-halting behaviour.
>
>     Just a comment:  There is a tendency in these debates to
> assume that programs either halt or "get into fixed loops".  Not
> so.  If it was so, then a "halt decider" would be easy to write
> [and indeed may conceivably be what PO either has written or is
> trying to write].  Sadly, there is a great sea of other programs;
> it is these that make a full halt decider impossible.
>

Refuting the conventional halting problem proofs is my primary goal.
Others here have said that these proofs are mutually reducible to some
of the others such as BB. When we reduce BB to HP then when we decide HP
the corresponding BB would seem to be decided.

>     [FTAOD, I'm tolerably sure that most people here, inc
> Malcolm, already know that.]

olcott

unread,
Jul 24, 2021, 10:06:02 AMJul 24
to
On 7/24/2021 1:17 AM, Richard Damon wrote:
> On 7/23/21 9:38 PM, olcott wrote:
>> On 7/23/2021 9:28 PM, Richard Damon wrote:
>
>>> This CAN'T be right, because we KNOW from the running of P(P) that P(P)
>>> does halt.
>>
>> If you carefully study the x86 execution trace of P you will see that it
>> is definitely true. If you keep ignoring this validation I will write
>> you off as a liar.
>>
>>
>
> As has been pointed out many times, the trace is incorrect.
>

It has been pointed out many times that the trace is assumed to be
incorrect. It has never been pointed out that the trace actually is
incorrect.

_P()
[00000c25](01) 55 push ebp
[00000c26](02) 8bec mov ebp,esp
[00000c28](03) 8b4508 mov eax,[ebp+08]
[00000c2b](01) 50 push eax // 2nd Param
[00000c2c](03) 8b4d08 mov ecx,[ebp+08]
[00000c2f](01) 51 push ecx // 1st Param
[00000c30](05) e820fdffff call 00000955 // call H
[00000c35](03) 83c408 add esp,+08
[00000c38](02) 85c0 test eax,eax
[00000c3a](02) 7402 jz 00000c3e
[00000c3c](02) ebfe jmp 00000c3c
[00000c3e](01) 5d pop ebp
[00000c3f](01) c3 ret
Size in bytes:(0027) [00000c3f]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
Begin Local Halt Decider Simulation at Machine Address:c25
[00000c25][00211776][0021177a] 55 push ebp // P begins
[00000c26][00211776][0021177a] 8bec mov ebp,esp
[00000c28][00211776][0021177a] 8b4508 mov eax,[ebp+08]
[00000c2b][00211772][00000c25] 50 push eax // push P
[00000c2c][00211772][00000c25] 8b4d08 mov ecx,[ebp+08]
[00000c2f][0021176e][00000c25] 51 push ecx // push P
[00000c30][0021176a][00000c35] e820fdffff call 00000955 // call H(P,P)

[00000c25][0025c19e][0025c1a2] 55 push ebp // P begins
[00000c26][0025c19e][0025c1a2] 8bec mov ebp,esp
[00000c28][0025c19e][0025c1a2] 8b4508 mov eax,[ebp+08]
[00000c2b][0025c19a][00000c25] 50 push eax // push P
[00000c2c][0025c19a][00000c25] 8b4d08 mov ecx,[ebp+08]
[00000c2f][0025c196][00000c25] 51 push ecx // push P
[00000c30][0025c192][00000c35] e820fdffff call 00000955 // call H(P,P)
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

If a person understands the x86 language and is not a liar they will
admit that the pure simulation of P(P) cannot possibly ever reach its
final state.

If they don't know the x86 language they better make sure to say this
otherwise they will be written off as a liar.

> The trace omits the tracing of code, using an incorrect transformation,
> and thus the reasoning you make is unsound.
>
> The replacement of the tracing of the simulator with the trace of the
> simulation is ONLY valid for a PURE simulator, not a 'pure simulator
> until ...' which isn't a pure simulator.
>
> Would you eat food that was 'clean until ...', I hope not.

olcott

unread,
Jul 24, 2021, 10:23:25 AMJul 24
to
On 7/23/2021 8:44 PM, André G. Isaak wrote:
> On 2021-07-23 19:32, olcott wrote:
>> On 7/23/2021 8:02 PM, André G. Isaak wrote:
>>> On 2021-07-23 18:26, olcott wrote:
>>>> On 7/23/2021 6:42 PM, André G. Isaak wrote:
>>>>> On 2021-07-23 14:38, olcott wrote:
>>>>>
>>>>>> int main(){ P(P); } initially doesn't give H jack shit, that it
>>>>>> the only reason why that P halts and this P never halts: int
>>>>>> main(){ H(P,P); }
>>>>>
>>>>> Well, duh. Of course it doesn't 'give H jack shit' because H *isn't
>>>>> being computed* in this case.
>>>>
>>>> Richard doesn't notice details like this.
>>>
>>> Richard gets it just fine. You're the one who is confused.
>>>
>>> int main(){ P(P); } is the only case we care about
>>
>> Then you are committed to deception.
>
> How so? the behaviour of int main(){ P(P); } is what int main(){ H(P,P);
> } is supposed to be deciding, so the behaviour of int main(){ P(P); } is
> the ultimate arbiter of the correct answer to the question. AND IT HALTS.
>

I am going to stay focused on this one point until we have mutual
agreement.

_P()
[00000c25](01) 55 push ebp
[00000c26](02) 8bec mov ebp,esp
[00000c28](03) 8b4508 mov eax,[ebp+08]
[00000c2b](01) 50 push eax // 2nd Param
[00000c2c](03) 8b4d08 mov ecx,[ebp+08]
[00000c2f](01) 51 push ecx // 1st Param
[00000c30](05) e820fdffff call 00000955 // call H
[00000c35](03) 83c408 add esp,+08
[00000c38](02) 85c0 test eax,eax
[00000c3a](02) 7402 jz 00000c3e
[00000c3c](02) ebfe jmp 00000c3c
[00000c3e](01) 5d pop ebp
[00000c3f](01) c3 ret
Size in bytes:(0027) [00000c3f]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
Begin Local Halt Decider Simulation at Machine Address:c25
[00000c25][00211776][0021177a] 55 push ebp // P begins
[00000c26][00211776][0021177a] 8bec mov ebp,esp
[00000c28][00211776][0021177a] 8b4508 mov eax,[ebp+08]
[00000c2b][00211772][00000c25] 50 push eax // push P
[00000c2c][00211772][00000c25] 8b4d08 mov ecx,[ebp+08]
[00000c2f][0021176e][00000c25] 51 push ecx // push P
[00000c30][0021176a][00000c35] e820fdffff call 00000955 // call H(P,P)

[00000c25][0025c19e][0025c1a2] 55 push ebp // P begins
[00000c26][0025c19e][0025c1a2] 8bec mov ebp,esp
[00000c28][0025c19e][0025c1a2] 8b4508 mov eax,[ebp+08]
[00000c2b][0025c19a][00000c25] 50 push eax // push P
[00000c2c][0025c19a][00000c25] 8b4d08 mov ecx,[ebp+08]
[00000c2f][0025c196][00000c25] 51 push ecx // push P
[00000c30][0025c192][00000c35] e820fdffff call 00000955 // call H(P,P)
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

If a person understands the x86 language and is not a liar they will
admit that the pure simulation of P(P) cannot possibly ever reach its
final state.

>>> since it is the only case where the computation P(P) is actually
>>> being performed, and that's what the halting problem is concerned
>>> with. Does this computation halt?
>>>
>>> in int main(){ H(P,P); } P is the *input* to a computation. Inputs
>>> neither halt nor don't halt because they *aren't* computations. The
>>
>> Yes more deception, knowing full well that the simulation of the
>> description of a machine on its input is computationally equivalent to
>> the execution of this machine on it input YOU DENY IT ANYWAY.
>
> Obviously they AREN'T computationally equivalent, because you claim that
> your simulated P(P) has DIFFERENT halting behaviour than the actual P(P).
>
> André

olcott

unread,
Jul 24, 2021, 10:34:25 AMJul 24
to
On 7/23/2021 6:49 PM, André G. Isaak wrote:
> On 2021-07-23 14:56, olcott wrote:
>
>> The P in main() is hidden from H that is why it wrongly halts.
>> int main(){ P(P); }
>
> Nothing is being 'hidden' from H. H isn't even running.
>
> And how can something 'wrongly halt'? Halting describes what a
> computation *actually* does. That you think it should do something else
> is immaterial. Computational theory isn't normative.
>
> You do realize that whenever people talk about P(P) they are talking
> about what you have taken to calling int main(){ P(P); }, right?
>
> And when they talk about H(P, P) they are talking about what you have
> taken to calling int main(){ H(P, P); }
>
> By the definition of 'halt decider' int main(){ H(P, P); } is supposed
> to tell us whether int main(){ P(P); } halts.
>
> You have now acknowledged that int main(){ P(P); } HALTS. Therefore,
> that is the *only* correct answer that int main(){ H(P, P); } can give
> if your H is actually a halt decider.
>
> André
>

Pathological Input to a halt decider is stipulated to mean any input
that was defined to do the opposite of whatever its corresponding halt
decider decides as Sipser describes:

Now we construct a new Turing machine D with H as a subroutine.
This new TM calls H to determine what M does when the input to
M is its own description ⟨M⟩. Once D has determined this information,
it does the opposite. (Sipser:1997:165)

This question can only be correctly answered after the pathology has
been removed. When a halt decider only acts as a pure simulator of its
input until after its halt status decision is made there is no feedback
loop of back channel communication between the halt decider and its
input that can prevent a correct halt status decision.

The verifiably correct x86 execution trace of the simulation of the
input to H(P,P) proves that this input cannot possibly reach its final
state while H acts as a pure x86 emulator of this input. This
unequivocally proves that H does correctly decide that its input never
halts.

_P()
[00000c25](01) 55 push ebp
[00000c26](02) 8bec mov ebp,esp
[00000c28](03) 8b4508 mov eax,[ebp+08]
[00000c2b](01) 50 push eax // 2nd Param
[00000c2c](03) 8b4d08 mov ecx,[ebp+08]
[00000c2f](01) 51 push ecx // 1st Param
[00000c30](05) e820fdffff call 00000955 // call H
[00000c35](03) 83c408 add esp,+08
[00000c38](02) 85c0 test eax,eax
[00000c3a](02) 7402 jz 00000c3e
[00000c3c](02) ebfe jmp 00000c3c
[00000c3e](01) 5d pop ebp
[00000c3f](01) c3 ret
Size in bytes:(0027) [00000c3f]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
Begin Local Halt Decider Simulation at Machine Address:c25
[00000c25][00211776][0021177a] 55 push ebp // P begins
[00000c26][00211776][0021177a] 8bec mov ebp,esp
[00000c28][00211776][0021177a] 8b4508 mov eax,[ebp+08]
[00000c2b][00211772][00000c25] 50 push eax // push P
[00000c2c][00211772][00000c25] 8b4d08 mov ecx,[ebp+08]
[00000c2f][0021176e][00000c25] 51 push ecx // push P
[00000c30][0021176a][00000c35] e820fdffff call 00000955 // call H(P,P)

[00000c25][0025c19e][0025c1a2] 55 push ebp // P begins
[00000c26][0025c19e][0025c1a2] 8bec mov ebp,esp
[00000c28][0025c19e][0025c1a2] 8b4508 mov eax,[ebp+08]
[00000c2b][0025c19a][00000c25] 50 push eax // push P
[00000c2c][0025c19a][00000c25] 8b4d08 mov ecx,[ebp+08]
[00000c2f][0025c196][00000c25] 51 push ecx // push P
[00000c30][0025c192][00000c35] e820fdffff call 00000955 // call H(P,P)
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

If a person understands the x86 language and is not a liar they will
admit that the pure simulation of P(P) cannot possibly ever reach its
final state.

Sipser, Michael 1997. Introduction to the Theory of Computation. Boston:
PWS Publishing Company (165-167)

olcott

unread,
Jul 24, 2021, 11:54:42 AMJul 24
to
On 7/24/2021 10:44 AM, Andy Walker wrote:
> On 24/07/2021 14:55, olcott wrote:
>> Refuting the conventional halting problem proofs is my primary goal.
>> Others here have said that these proofs are mutually reducible to
>> some of the others such as BB.
>
>     Not the proofs, but the results.  Even if you were to refute
> the conventional HP proof, it would do nothing to change the status
> of the HP, or of BB.
>
>>                  When we reduce BB to HP then when we
>> decide HP the corresponding BB would seem to be decided.
>
>     BB, as a problem, is long-since decided;  there is no program
> that computes the BB function [elementary proof in the Wiki article on
> BB].  Since the BB and HP /results/ are "mutually reducible", that
> amounts to an independent [and elementary] proof of the HP result.
> There is /also/ a simple proof [also given in Wiki] of the BB result
> from the HP result.
>
>     It is quite common in maths for interesting results to have
> several or even many proofs;  ISTR collections of 50+ proofs that
> sqrt(2) is irrational, and many proofs of Pythagoras's Theorem.
> There are also, for example, 30+ proofs of the result that if you
> dissect a rectangle into smaller rectangles each of which has at
> least one side an integer, then the original rectangle must have
> the same property.  It's perfectly possible that many of those
> proofs are flawed;  but you would need to refute /all/ of them
> to overturn the original result.
>

That BB is not computable on physical hardware is easy to see in that
the more complex cases require more memory cells than atoms in the
universe.

None-the-less refuting the conventional HP proofs is of very significant
consequence.

olcott

unread,
Jul 24, 2021, 1:24:06 PMJul 24
to
On 7/24/2021 11:31 AM, Richard Damon wrote:
> On 7/24/21 7:05 AM, olcott wrote:
>> On 7/24/2021 1:17 AM, Richard Damon wrote:
>>> On 7/23/21 9:38 PM, olcott wrote:
>>>> On 7/23/2021 9:28 PM, Richard Damon wrote:
>>>
>>>>> This CAN'T be right, because we KNOW from the running of P(P) that P(P)
>>>>> does halt.
>>>>
>>>> If you carefully study the x86 execution trace of P you will see that it
>>>> is definitely true. If you keep ignoring this validation I will write
>>>> you off as a liar.
>>>>
>>>>
>>>
>>> As has been pointed out many times, the trace is incorrect.
>>>
>>
>> It has been pointed out many times that the trace is assumed to be
>> incorrect. It has never been pointed out that the trace actually is
>> incorrect.
>
> No, it HAS been pointed out MANY times, you just don't seem to be able
> to read, at least not anything that disagrees with you.

When we examine the execution trace of the simulation of the input to
H(P,P) we can confirm that a pure simulation of this input cannot
possibly ever reach its final state.

What happens when int main(){ P(P); } is executed is another different
point. The you refuse to acknowledge the first point really seems to
make you a liar.

olcott

unread,
Jul 24, 2021, 1:41:41 PMJul 24
to
On 7/24/2021 11:33 AM, Richard Damon wrote:
> As has been pointed out many times, this is an incorrect trace of the
> program.
>
> You seem to be insisting that it is correct to deceive. YOU ARE A LIAR.
>

(1) H does perform a pure simulation of its input until after it makes
its halt status decision.

(2) It can be verified that this is a pure simulation on the basis that
the execution trace does what the x86 source-code of P specifies.

(3) Because there are no control flow instructions in the execution
trace that can possibly escape the infinite recursion the execution
trace proves that a pure simulation of the above input cannot possibly
ever reach its final state.

(4) Therefore H was correct when it decided that its input never halts.

olcott

unread,
Jul 24, 2021, 2:42:34 PMJul 24
to
On 7/24/2021 1:34 PM, Richard Damon wrote:
> On 7/24/21 10:23 AM, olcott wrote:
>> On 7/24/2021 11:31 AM, Richard Damon wrote:
>>> On 7/24/21 7:05 AM, olcott wrote:
>>>> On 7/24/2021 1:17 AM, Richard Damon wrote:
>>>>> On 7/23/21 9:38 PM, olcott wrote:
>>>>>> On 7/23/2021 9:28 PM, Richard Damon wrote:
>>>>>
>>>>>>> This CAN'T be right, because we KNOW from the running of P(P) that
>>>>>>> P(P)
>>>>>>> does halt.
>>>>>>
>>>>>> If you carefully study the x86 execution trace of P you will see
>>>>>> that it
>>>>>> is definitely true. If you keep ignoring this validation I will write
>>>>>> you off as a liar.
>>>>>>
>>>>>>
>>>>>
>>>>> As has been pointed out many times, the trace is incorrect.
>>>>>
>>>>
>>>> It has been pointed out many times that the trace is assumed to be
>>>> incorrect. It has never been pointed out that the trace actually is
>>>> incorrect.
>>>
>>> No, it HAS been pointed out MANY times, you just don't seem to be able
>>> to read, at least not anything that disagrees with you.
>>
>> When we examine the execution trace of the simulation of the input to
>> H(P,P) we can confirm that a pure simulation of this input cannot
>> possibly ever reach its final state.
>
> But the trace ISN'T a PURE SIMULATION TRACE.
>

There are no deceitful weasel words to get around this:

It is proven to be a pure simulation on the basis that the execution
trace of P precisely matches the x86 source-code of P.

olcott

unread,
Jul 24, 2021, 3:23:09 PMJul 24
to
On 7/24/2021 2:07 PM, André G. Isaak wrote:
> Matches the source-code?
>
> To show it is a pure simulation of P(P), you'd need to compare the trace
> of H(P, P) with a *trace* of P(P), not the source code.
>

You are wrong and you know it. Why lie?

The behavior of P must correspond to the behavior that its code stipulates.

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

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============

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



> And since you have already acknowledged that P(P) HALTS, the trace of
> P(P) *will* show that P(P) ultimately reaches one of its final states.
>
> André

olcott

unread,
Jul 24, 2021, 3:24:48 PMJul 24
to
On 7/24/2021 2:21 PM, Richard Damon wrote:
> Except that it doesn't trace a call instruction correctly!


You are wrong and you know it. Why lie?

The behavior of P must correspond to the behavior that its code stipulates.

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

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
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


olcott

unread,
Jul 24, 2021, 6:31:16 PMJul 24
to
On 7/24/2021 5:10 PM, André G. Isaak wrote:
> On 2021-07-24 14:03, olcott wrote:
>
>> The question is: Can the input to H ever reach its final state while H
>> is in pure simulator mode?
>
> No, it is not.

Yes it is.

_P()
[00000c25](01) 55 push ebp
[00000c26](02) 8bec mov ebp,esp
[00000c28](03) 8b4508 mov eax,[ebp+08]
[00000c2b](01) 50 push eax // 2nd Param
[00000c2c](03) 8b4d08 mov ecx,[ebp+08]
[00000c2f](01) 51 push ecx // 1st Param
[00000c30](05) e820fdffff call 00000955 // call H
...

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
Begin Local Halt Decider Simulation at Machine Address:c25
[00000c25][00211776][0021177a] 55 push ebp // P1 begins
[00000c26][00211776][0021177a] 8bec mov ebp,esp
[00000c28][00211776][0021177a] 8b4508 mov eax,[ebp+08]
[00000c2b][00211772][00000c25] 50 push eax // push P
[00000c2c][00211772][00000c25] 8b4d08 mov ecx,[ebp+08]
[00000c2f][0021176e][00000c25] 51 push ecx // push P
[00000c30][0021176a][00000c35] e820fdffff call 00000955 // call H1
[00000c25][0025c19e][0025c1a2] 55 push ebp // P2 begins
[00000c26][0025c19e][0025c1a2] 8bec mov ebp,esp
[00000c28][0025c19e][0025c1a2] 8b4508 mov eax,[ebp+08]
[00000c2b][0025c19a][00000c25] 50 push eax // push P
[00000c2c][0025c19a][00000c25] 8b4d08 mov ecx,[ebp+08]
[00000c2f][0025c196][00000c25] 51 push ecx // push P
[00000c30][0025c192][00000c35] e820fdffff call 00000955 // call H2
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

(1) H does perform a pure simulation of its input until after it makes
its halt status decision.

(2) It can be verified that this is a pure simulation on the basis that
the execution trace does what the x86 source-code of P specifies.

(3) Because there are no control flow instructions in the execution
trace that can possibly escape the infinite recursion the execution
trace proves that a pure simulation of the above input cannot possibly
ever reach its final state.

(4) Therefore H was correct when it decided that its input never halts.

If you bother to carefully study all of the above then you know that H
does correctly decide that its input never halts.

*How we reconcile this with the fact that int main(){ P(P); } halts is
another different issue*

If (1)(2)(3) are verified facts then NO MATTER WHAT
(4) follows by logical necessity.

(1) Is a verified fact.
(2) is a verified fact.
(3) is a verified fact.

> The question which a halt decider is supposed to answer
> about input (P, P) is *does P(P) halt*. (or int main { P(P); } as you
> insist on more verbosely expressing it for some mysterious reason)
>
> We KNOW what the answer to that question is.
>
> No amount of traces or arguments on your part can possibly justify the
> claim that H(P, P) == 0 is correct given that we *know* what the answer
> to this question is based on the behaviour of P(P).
>
> Given the definition of the halting problem, the actual behaviour of
> P(P) is the ultimate authority on the answer to this question. The
> actual behaviour of P(P) is the *only* thing that matters in
> establishing the correct answer to this question.
>
> Even if the logical flaws in your traces and arguments weren't apparent
> (They are and have been pointed out to you) it WOULDN'T MATTER. When a
> 'decider' gives an answer that contradicts the ACTUAL answer then the
> decider is wrong.
>
> AFAICT your argument runs as follows:
>
> (1) We know that P(P) halts.
> (2) My decider H determines P(P) doesn't halt.
> (3) My decider must be right because I say so. I even have traces.
> (4) Therefore P(P) must not "really" halt even though it does.
>     Therefore it "wrongly" halts.
>
> Let's see how well that goes over with peer reviewers.
>
> André

olcott

unread,
Jul 26, 2021, 11:08:54 AMJul 26
to
On 7/25/2021 3:02 PM, Mike Terry wrote:
> On 25/07/2021 04:07, Ben Bacarisse wrote:
>> Richard Damon <Ric...@Damon-Family.org> writes:
>>
>>> And the code stipulates a call to H that isn't traced.
>>
>> Which is by means an accidental omission.  H is being kept secret, not
>> because it's so wonderful, but because it's junk.  I don't for a moment
>> think he's got an H that does what he claims.  I don't think he knows
>> how to have H invoke the simulation software recursively.  I'd put money
>> on the fact that H just makes calls and not nested simulations.
>>
>
> I think PO may have done better than a direct call, but I doubt he has
> done things in a "natural" way you or I would like.  For a "pure"
> approach, given PO's emulation is implemented in the OS rather than in
> the decider code, I'd expect to see primitive APIs to
> a)  create a new emulation environment
> b)  single step an emulation
> c)  retrieve current emulation state data (with options, e.g. to
>     retrieve current registers, or to read virtual process memory)
> Tracking nested simulations would be the responsibility of the
> application which created the emulation, i.e. it would recognise when an
> emulated program in turn creates a nested emulation, and when that
> simulation is stepped and so on recursively.  (This is what a TM would
> need to do, but it's much harder for a TM as it's not obvious what
> constitutes "emulator behaviour" in a TM - it's just more TM-ing.)
>
> But that's all rather fiddly, and I think PO's handling of nested
> simulations is for the OS to maintain a global merged trace of all (or
> some?) instructions executed during nested emulations, and make those
> directly available to the applications (and emulated applications). That
> wouldn't be /disasterous/ provided it's done without leakage of
> information which would enable emulated code to determine details about
> it's emulator (or even /whether/ its in fact being emulated or run
> directly in x86utm).
>
> Whatever PO has done, the key to whether it's emulation-like or
> call-like is where the "stepping" of the emulation happens.  It should
> be the case that an emulation advances ONLY when it's emulating
> application calls the API to step the emulation a number of
> instructions.  I don't know if PO's software works like that, but he
> didn't disagree when I suggested something like this some time back.
>
>
> Mike.

All of the levels of emulators simulate their inputs in SingleStep()
mode. All of the emulations are data belonging to the outermost emulator.

The data that is shown in the debug trace is the only data that is
stored. This data is the sole basis of the halt status decision.

To model actual TM's more closely the input to H is simulated in its own
separate process context virtual machine having its own RAM, stack and
registers.

This API function simulates one instruction of the slave and returns the
line of code that was simulated:

u32 DebugStep(Registers* master_state, Registers* slave_state,
Decoded_Line_Of_Code* decoded) {}
Reply all
Reply to author
Forward
0 new messages