Re: Halting Problem Solved? (Black Box Decider Theory) V2

[olcott]

On 7/17/2021 9:20 AM, Mr Flibble wrote:
> On Sat, 17 Jul 2021 09:18:50 -0500
> olcott <No...@NoWhere.com> wrote:
>
>> On 7/17/2021 8:37 AM, Mr Flibble wrote:
>>> On Sat, 17 Jul 2021 13:22:56 -0000 (UTC)
>>> Alan Mackenzie <a...@muc.de> wrote:
>>>> Not really - you don't have a universal halting decider here by
>>>> design. And even if you did, the signature wouldn't do anything to
>>>> prevent the existence of the programs which have an "invalid
>>>> relationship" with D.
>>>
>>> The point is that this "invalid relationship" is DETECTABLE by the
>>> black box decider. This "invalid relationship" only exists for
>>> programs which are deliberately designed to defeat the decider
>>> which are uninteresting cases because presumably we are using a
>>> decider to decide legitimate programs that have serve some useful
>>> purpose beyond the HP itself.
>>>
>>> /Flibble
>>>
>>
>> We might as well have a black box cure for cancer or a black box cure
>> for violence in the world. Unless you say how it works it don't count.
>
> You haven't shown how your x86 omnishambles works so it "don't count".
>
> /Flibble
>

Sure I have. Anyone that:
(a) knows the x86 language.

(b) knows that H acts is a pure x86 emulator until after it makes its
halt status decision.

(c) Understands that (b) means that H can screen out its own address
range from every execution trace basis of its halt status decision.

(d) Examines the x86 execution trace of the simulation of P(P) and see
that P provides no escape from its infinite recursion.

Knows that H(P,P)==0 is the correct halt status decision.


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

// 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()
{
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
[00000c5e](05) 68360c0000 push 00000c36
[00000c63](05) e8fefcffff call 00000966
[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
[00000c5e][00101722][00000c36] 68360c0000 push 00000c36
[00000c63][0010171e][00000c68] e8fefcffff call 00000966 // call H(P,P)

Begin Local Halt Decider Simulation at Machine Address:c36
[00000c36][002117ca][002117ce] 55 push ebp
[00000c37][002117ca][002117ce] 8bec mov ebp,esp
[00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08]
[00000c3c][002117c6][00000c36] 50 push eax
[00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08]
[00000c40][002117c2][00000c36] 51 push ecx
[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
[00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08]
[00000c40][0025c1ea][00000c36] 51 push ecx
[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)


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]

On 7/17/2021 9:20 AM, Alan Mackenzie wrote:
> Mr Flibble <fli...@reddwarf.jmc> wrote:
>> On Sat, 17 Jul 2021 13:59:02 -0000 (UTC)
>> Alan Mackenzie <a...@muc.de> wrote:

>
>>> Mr Flibble <fli...@reddwarf.jmc> wrote:
>>>> On Sat, 17 Jul 2021 13:22:56 -0000 (UTC)
>>>> Alan Mackenzie <a...@muc.de> wrote:
>>>>> Not really - you don't have a universal halting decider here by
>>>>> design. And even if you did, the signature wouldn't do anything to
>>>>> prevent the existence of the programs which have an "invalid
>>>>> relationship" with D.
>
>>>> The point is that this "invalid relationship" is DETECTABLE by the
>>>> black box decider.
>

>>> I think, but I'm not sure, that such relationships cannot be detected,
>>> that it's another one of these limitation theorems. Ben could
>>> probably say more on this.

>
>>>> This "invalid relationship" only exists for programs which are

>>>> deliberately designed to defeat the decider ....
>
>>> Not at all. There will be random programs, not deliberately designed,
>>> which will also have such a relationship with the purported decider.
>
>>>> .... which are uninteresting cases because presumably we are using a

>>>> decider to decide legitimate programs that have serve some useful
>>>> purpose beyond the HP itself.
>

>>> Then you're not talking about the standard halting problem. That
>>> shows the impossibility of a decider which can decide ANY program.
>>> If you limit the scope of the programs handled, then you might well
>>> construct a practically useful partial decider. Difficult, but
>>> possible. There are probably theorems about the sort of things that
>>> are possible here, but I don't know them.
>
>>> None of this has any relevance for the theoremhood of the halting
>>> problem result itself.
>
>> Disagree: having a third result for invalid pathological programs
>> whilst novel is still a result, i.e. a decision reached in finite time.
>
> Let me stress again that there is nothing invalid or pathological about
> these programs,

You must be very very brainwashed to believe that an input the was
intentionally defined to do the opposite of whatever halt status value
is returned from its corresponding TM is not pathological.

Flibble was the first one smart enough to understand this besides me.
That makes him enormously smarter than you at least on this one key point.


> and they can run and halt or not halt like any other
> program. It is only in their relationship with H where they are special,
> in that H is unable to determine their halting status correctly.
>
> That's assuming it's possible for H to single out such programs. I don't
> know if this is possible in the general case, but I suspect it's not.
> Again, Ben or Richard might know more about this.
>
> But all this is moving away from the halting problem.
>
>> /Flibble

[olcott]

On 7/17/2021 9:34 AM, Alan Mackenzie wrote:
> Mr Flibble <fli...@reddwarf.jmc> wrote:

>> On Sat, 17 Jul 2021 14:20:42 -0000 (UTC)

>>> about these programs, and they can run and halt or not halt like any

>>> other program. It is only in their relationship with H where they
>>> are special, in that H is unable to determine their halting status
>>> correctly.
>
>>> That's assuming it's possible for H to single out such programs. I
>>> don't know if this is possible in the general case, but I suspect
>>> it's not. Again, Ben or Richard might know more about this.
>
>>> But all this is moving away from the halting problem.
>

>> Disagree: as the decider is a black box if it can always detect when it
>> is being invoked, either directly by the trusted operator or indirectly
>> by P which does not have the trusted operator's private key in order to
>> digitally sign P and I that is passed to the decider.
>
> P might contain a copy of D's algorithm (with or without the key stuff),
> and indeed P might contain a copy of the private key. Such programs
> _exist_, whether or not we could as humans create them. As I say, I
> don't think it's possible for D to detect an algorithm which does the
> same as D.
>
> But in any case, D is not behaving as a universal halting detector, in
> that it doesn't return halts/doesn't halt for all input programs.
>
>> /Flibble
>

Flibble is at least years behind me on this stuff.
I had these same sort of ideas as far back as 2004.

Correctly deciding the halt status of these "impossible" inputs is far
superior to merely recognizing and rejecting them.

Here is my most recent attempt at recognizing and rejecting the
pathological inputs:

https://www.researchgate.net/publication/323384939_Halting_Problem_Proof_from_Finite_Strings_to_Final_States

[Mr Flibble]

On Sat, 17 Jul 2021 11:23:37 -0500
olcott <No...@NoWhere.com> wrote:
> Flibble is at least years behind me on this stuff.
> I had these same sort of ideas as far back as 2004.
>
> Correctly deciding the halt status of these "impossible" inputs is
> far superior to merely recognizing and rejecting them.

Years behind? Perhaps, however I don't plan on spending years of my
life on this problem like you have: our time on this planet is finite
and precious (there is no afterlife) so given that I am happy for my
black box decider to remain an abstract hypothetical concept.

/Flibble

[olcott]

I have spent many thousands of hours on this since 2004.

I do this because the solution is the key basis for strong AI.
Once halting is known to be decidable and computation has no limits AI
research will increase 100-fold.

[olcott]

On 7/17/2021 3:05 PM, Alan Mackenzie wrote:
> [ Malicious cross posting removed ]

> Brainwashed to have a correct overview which Olcott lacks? How about you
> actually read what I wrote before answering at half-cock? My point was
> that these programs, though they may have a special relationship with a
> purported halt decider, are otherwise perfectly ordinary programs which
> run, and either halt or fail to halt. The purported halt decider will
> give the wrong answer for such programs.
>

You have proven much more honest than Ben on this he never ever
acknowledged any *special relationship*

The key is that *special relationship* is what has made them unable to
provide the correct halt status, thus making the *special relationship*
harmful AKA pathological.

>> Flibble was the first one smart enough to understand this besides me.
>> That makes him enormously smarter than you at least on this one key point.
>

> You are not smart. I think Mr. Flibble now sees that these programs are
> just programs, but we'd have to wait for him to say this himself.
>

Flibble is merely at the point that I was in 2004. This is way ahead of
everyone else that simply accepts the pathological self-reference error
as perfectly legitimate and not an error.

It is really cool that we have the exact same computer science academic
background. I had an honors level 3.515 GPA when I graduated.

[olcott]

On 7/17/2021 3:51 PM, Alan Mackenzie wrote:
> [ Malicious cross posting snipped. ]

>
> In comp.theory olcott <No...@nowhere.com> wrote:
>> On 7/17/2021 3:05 PM, Alan Mackenzie wrote:
>>> [ Malicious cross posting removed ]
>
>>> In comp.theory olcott <No...@nowhere.com> wrote:
>>>> On 7/17/2021 9:20 AM, Alan Mackenzie wrote:
>

> [ .... ]

>
>>>>> Let me stress again that there is nothing invalid or pathological
>>>>> about these programs,
>
>>>> You must be very very brainwashed to believe that an input the was
>>>> intentionally defined to do the opposite of whatever halt status
>>>> value is returned from its corresponding TM is not pathological.
>
>>> Brainwashed to have a correct overview which Olcott lacks? How about
>>> you actually read what I wrote before answering at half-cock? My
>>> point was that these programs, though they may have a special
>>> relationship with a purported halt decider, are otherwise perfectly
>>> ordinary programs which run, and either halt or fail to halt. The
>>> purported halt decider will give the wrong answer for such programs.
>
>
>> You have proven much more honest than Ben on this he never ever
>> acknowledged any *special relationship*
>
>> The key is that *special relationship* is what has made them unable to
>> provide the correct halt status, thus making the *special relationship*
>> harmful AKA pathological.
>

> What do you mean, harmful? There's nothing here which will kill polar
> bears, increase the amount of carbon dioxide in the atmosphere or cause
> floods or droughts. There's nothing pathalogical here, either - these

The fact that the *special relationship* (without my solution) has the
harmful effect of preventing useful software tools from being created.

This can harmful effect can cause human death in that the software tool
could have detected an error in the software control of a life support
system.

> special situations where a purpurted decider gives the wrong answer are
> are part of all such deciders. They are an essential property of such
> purported deciders and are a fascinating thing to explore and form
> theorems around.
>

Not at all and you know it.
This problem is all the cause of the *special relationship*.

>>>> Flibble was the first one smart enough to understand this besides me.
>>>> That makes him enormously smarter than you at least on this one key
>>>> point.
>
>>> You are not smart. I think Mr. Flibble now sees that these programs
>>> are just programs, but we'd have to wait for him to say this himself.
>
>> Flibble is merely at the point that I was in 2004. This is way ahead of
>> everyone else that simply accepts the pathological self-reference error
>> as perfectly legitimate and not an error.
>

> You are in a tiny minority (of 1?) who believes essential properties of
> mathematical logic are intrinsically erroneous.

Self-contradiction <is> an error in all logic systems. Learned-by-rote
people never notice this because their Learned-by-rote never tells them.

Only those willing to challenge the philosophical foundation of the
notion of truth itself ever begin to have a clue.

Tarski anchored his undefinability (of truth) theorem in the liar paradox.

It would
then be possible to reconstruct the antinomy of the liar in the
metalanguage, by forming in the language itself a sentence x
such that the sentence of the metalanguage which is correlated
with x asserts that x is not a true sentence.
http://www.liarparadox.org/Tarski_247_248.pdf

> It seems you are not
> prepared to live in the world we have, you want one essentially
> different (that cannot possibly exist).

>
>> It is really cool that we have the exact same computer science academic
>> background. I had an honors level 3.515 GPA when I graduated.
>

> [ .... ]

[olcott]

On 7/18/2021 5:57 AM, Alan Mackenzie wrote:
> [ Malicious cross posting removed ]
>
> In comp.theory olcott <No...@nowhere.com> wrote:
>> On 7/17/2021 3:51 PM, Alan Mackenzie wrote:
>>> [ Malicious cross posting snipped. ]
>
>>> In comp.theory olcott <No...@nowhere.com> wrote:
>>>> On 7/17/2021 3:05 PM, Alan Mackenzie wrote:
>>>>> [ Malicious cross posting removed ]
>

> [ .... ]

>
>>>>> Brainwashed to have a correct overview which Olcott lacks? How
>>>>> about you actually read what I wrote before answering at half-cock?
>>>>> My point was that these programs, though they may have a special
>>>>> relationship with a purported halt decider, are otherwise perfectly
>>>>> ordinary programs which run, and either halt or fail to halt. The
>>>>> purported halt decider will give the wrong answer for such programs.
>
>>>> You have proven much more honest than Ben on this he never ever
>>>> acknowledged any *special relationship*
>
>>>> The key is that *special relationship* is what has made them unable
>>>> to provide the correct halt status, thus making the *special
>>>> relationship* harmful AKA pathological.
>
>>> What do you mean, harmful? There's nothing here which will kill polar
>>> bears, increase the amount of carbon dioxide in the atmosphere or cause
>>> floods or droughts. There's nothing pathalogical here, either - these
>

>> The fact that the *special relationship* (without my solution) ....
>
> With or without your "solution", which isn't one.

Ignoring that I proved that H(P,P)==0 is correct is not a rebuttal.

>
>> .... has the harmful effect of preventing useful software tools from

>> being created.
>
>> This can harmful effect can cause human death in that the software tool
>> could have detected an error in the software control of a life support
>> system.
>

> You've got a strange view of things, indeed. Think of this theorem as
> something like division by zero. Nobody goes around moaning about how
> the inability to divide by zero restricts the software he can write.
>

It is not that halting is undecidable is that pathological cases that
cheat are allowed. My solution removes the pathology from these
otherwise pathological cases. When H acts as a pure simulator until
after it makes its halt status decision P can never do the opposite of
whatever H decides.

>>> special situations where a purpurted decider gives the wrong answer are
>>> are part of all such deciders. They are an essential property of such
>>> purported deciders and are a fascinating thing to explore and form
>>> theorems around.
>
>> Not at all and you know it.
>

> Don't be impertinent. What I wrote is true, and I meant it.

>
>> This problem is all the cause of the *special relationship*.
>

> You would like to believe in magic. You don't complain about the
> existence of gravity causing people to fall and hurt themselves. Or
> maybe you do, one just can't tell with some people.
>

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.

> [ .... ]

>
>>>> Flibble is merely at the point that I was in 2004. This is way ahead
>>>> of everyone else that simply accepts the pathological self-reference
>>>> error as perfectly legitimate and not an error.
>
>>> You are in a tiny minority (of 1?) who believes essential properties of
>>> mathematical logic are intrinsically erroneous.
>
>> Self-contradiction <is> an error in all logic systems. Learned-by-rote
>> people never notice this because their Learned-by-rote never tells them.
>

> Where "learned-by-rote people" means people more learned that Peter
> Olcott. It's a crude and nasty insult, and you would do better to stop
> using it.

It is the most accurate depiction of the reason for the lack of mutual
understanding. Knowing all the details of what math says is no good if
math itself gets some things wrong.

> I think you'll find (or have found) that mathematical logic is
> such a difficult topic, that learning without understanding is not
> possible.
>
> In the topic at hand there is no self-contradiction.

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.

> It's just that you
> personally have unreasonable expectations about mathematical systems.
> There is no universal halt decider, just as there's no division by zero.
> That's all there is to it.

>
>> Only those willing to challenge the philosophical foundation of the
>> notion of truth itself ever begin to have a clue.
>

> That's an extravagant claim, without basis. What we have is somebody
> without a clue challenging the mathematical basis of truth. That is
> bound to end in disappointment.
>

That you simply cut rather than responded to my basis and then claimed
that I provided no basis is flat out dishonest.

Tarski's work is considered to provide the basic mathematical foundation
of the notion of truth. All of his work besides his undefinability
theorem is great.Tarski anchored his undefinability (of truth) theorem
in the liar paradox. The next paragraph he specifies the basis of his
undefinability theorem.

It would
then be possible to reconstruct the antinomy of the liar in the
metalanguage, by forming in the language itself a sentence x
such that the sentence of the metalanguage which is correlated
with x asserts that x is not a true sentence.

http://www.liarparadox.org/Tarski_247_248.pdf

[olcott]

On 7/19/2021 1:20 PM, Alan Mackenzie wrote:
> [ Malicious cross posting removed ]
>

> No, it's an insistence on the validity of a proven theorem. *You*'re the
> one attempting rebuttal. Like I've said before, the proofs of the
> halting problem theorem are independent of the internal workings of
> purported halt deciders, so those internal workings just aren't
> interesting. H doesn't exist.
>

I show all the steps of exactly how H(P,P)==0 is derived. That you
simply ignore these steps and claim that I am incorrect is simply
dishonest.

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

>>>> .... has the harmful effect of preventing useful software tools from
>>>> being created.
>
>>>> This can harmful effect can cause human death in that the software
>>>> tool could have detected an error in the software control of a life
>>>> support system.
>
>>> You've got a strange view of things, indeed. Think of this theorem as
>>> something like division by zero. Nobody goes around moaning about how
>>> the inability to divide by zero restricts the software he can write.
>
>> It is not that halting is undecidable is that pathological cases that
>> cheat are allowed.
>

> You are in an emotional state. "Pathalogical" and "cheat" are not
> neutral terms to describe something which has nothing to do with a
> disease and has nothing to do with any sense of "fair play".

>
>> My solution removes the pathology from these otherwise pathological
>> cases. When H acts as a pure simulator until after it makes its halt
>> status decision P can never do the opposite of whatever H decides.
>

> It can, if H and H^ (?P) are defined as described by Linz, for example.
> As you keep ignoring, the internal details of purported Hs have no
> influence on the proof and are wholly unimportant.

>
>>>>> special situations where a purpurted decider gives the wrong answer
>>>>> are are part of all such deciders. They are an essential property
>>>>> of such purported deciders and are a fascinating thing to explore
>>>>> and form theorems around.
>
>>>> Not at all and you know it.
>
>>> Don't be impertinent. What I wrote is true, and I meant it.
>
>>>> This problem is all the cause of the *special relationship*.
>
>>> You would like to believe in magic. You don't complain about the
>>> existence of gravity causing people to fall and hurt themselves. Or
>>> maybe you do, one just can't tell with some people.
>
>> 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.
>

> That's a silly definition; for a start, there's no way of applying it,
> since it's impossible to determine if a turing machine "does the opposite
> of" something. Besides there are all the other TMs which the purported
> decider would get wrong which don't "do the opposite". (No, I don't know
> if there are any, but you don't know there aren't.)
>
> [ .... ]

>
>>>>> You are in a tiny minority (of 1?) who believes essential properties
>>>>> of mathematical logic are intrinsically erroneous.
>
>>>> Self-contradiction <is> an error in all logic systems.
>>>> Learned-by-rote people never notice this because their
>>>> Learned-by-rote never tells them.
>
>>> Where "learned-by-rote people" means people more learned that Peter
>>> Olcott. It's a crude and nasty insult, and you would do better to
>>> stop using it.
>
>> It is the most accurate depiction of the reason for the lack of mutual
>> understanding. Knowing all the details of what math says is no good if
>> math itself gets some things wrong.
>

> I despise you. You are ignorant of mathematics, and thus feel entitled
> to treat it with disdain. Maths doesn't "get some things wrong", at
> least not in the sense you mean. The lack of mutual understanding is
> purely a result of ignorance on the part of the crank, and the lack of
> respect for expertise he doesn't possess.

>
>>> I think you'll find (or have found) that mathematical logic is
>>> such a difficult topic, that learning without understanding is not
>>> possible.
>
>>> In the topic at hand there is no self-contradiction.
>
>> 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.
>

> Whatever. At any rate, you appear to have accepted the halting problem
> theorem, in that you accept the existence of what you call "pathological"
> input, with which purported deciders return the wrong answer. I think
> you just mean inputs that the purported decider gets wrong.

>
>>> It's just that you personally have unreasonable expectations about
>>> mathematical systems. There is no universal halt decider, just as
>>> there's no division by zero. That's all there is to it.
>
>>>> Only those willing to challenge the philosophical foundation of the
>>>> notion of truth itself ever begin to have a clue.
>
>>> That's an extravagant claim, without basis. What we have is somebody
>>> without a clue challenging the mathematical basis of truth. That is
>>> bound to end in disappointment.
>
>> That you simply cut rather than responded to my basis and then claimed
>> that I provided no basis is flat out dishonest.
>

> Sorry, misunderstanding. I thought you were talking about yourself,
> there, not Tarski.

>
>> Tarski's work is considered to provide the basic mathematical foundation
>> of the notion of truth. All of his work besides his undefinability
>> theorem is great.Tarski anchored his undefinability (of truth) theorem
>> in the liar paradox. The next paragraph he specifies the basis of his
>> undefinability theorem.
>
>> It would then be possible to reconstruct the antinomy of the liar in
>> the metalanguage, by forming in the language itself a sentence x such
>> that the sentence of the metalanguage which is correlated with x
>> asserts that x is not a true sentence.
>

[olcott]

On 7/20/2021 12:35 PM, Alan Mackenzie wrote:
> [ Malicious cross posting removed ]
>
> In comp.theory olcott <No...@nowhere.com> wrote:
>> On 7/19/2021 1:20 PM, Alan Mackenzie wrote:
>>> [ Malicious cross posting removed ]
>
>>> In comp.theory olcott <No...@nowhere.com> wrote:
>

> [ .... ]

>
>>>> Ignoring that I proved that H(P,P)==0 is correct is not a rebuttal.
>
>>> No, it's an insistence on the validity of a proven theorem. *You*'re the
>>> one attempting rebuttal. Like I've said before, the proofs of the
>>> halting problem theorem are independent of the internal workings of
>>> purported halt deciders, so those internal workings just aren't
>>> interesting. H doesn't exist.
>
>> I show all the steps of exactly how H(P,P)==0 is derived.
>

> You don't. You haven't yet published the source code of an alleged H.

>
>> That you simply ignore these steps and claim that I am incorrect is
>> simply dishonest.
>

> No, it's being dishonest to indulge you with the suggestion that what you
> are doing has any possible validity. It is unimportant and uninteresting
> why H(P,P)==0, if it actually is. It has no bearing on the halting
> theorem proofs, which work regardless of the nature of any purported
> halting decider. Seeing as how you can't disprove these proofs honestly,
> you resort to falsehoods and obfuscation. Even so, the other posters on
> this newsgroup have seen through it and exposed it. When is all this
> nonsense going to end?

>

// 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()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
}

All of the proofs conclusively prove that H cannot possibly return a
Boolean value corresponding to the actual halt status of P to P in the
above computation.

None of the proofs bother to examine whether or not returning a correct
halt status from H to P in the above computation is required, they
simply assume that it is required. *That is their error*

The paper shows the actual execution trace of the simulation of P(P) by
H cannot possibly ever stop running unless its simulation is aborted.
Because this is the definition of a computation that never halts
H(P,P)==0 is impossibly incorrect.

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

[olcott]

On 7/20/2021 1:53 PM, Alan Mackenzie wrote:
> [ Malicious cross posting removed ]
>
> In comp.theory olcott <No...@nowhere.com> wrote:
>> On 7/20/2021 12:35 PM, Alan Mackenzie wrote:
>>> [ Malicious cross posting removed ]
>
>>> In comp.theory olcott <No...@nowhere.com> wrote:
>

> [ .... ]

>
>>>> I show all the steps of exactly how H(P,P)==0 is derived.
>
>>> You don't. You haven't yet published the source code of an alleged H.
>
>>>> That you simply ignore these steps and claim that I am incorrect is
>>>> simply dishonest.
>
>>> No, it's being dishonest to indulge you with the suggestion that what
>>> you are doing has any possible validity. It is unimportant and
>>> uninteresting why H(P,P)==0, if it actually is. It has no bearing on
>>> the halting theorem proofs, which work regardless of the nature of any
>>> purported halting decider. Seeing as how you can't disprove these
>>> proofs honestly, you resort to falsehoods and obfuscation. Even so,
>>> the other posters on this newsgroup have seen through it and exposed
>>> it. When is all this nonsense going to end?
>

> [ .... ]

>
>> All of the proofs conclusively prove that H cannot possibly return a
>> Boolean value corresponding to the actual halt status of P to P in the
>> above computation.
>

> Wow!

>
>> None of the proofs bother to examine whether or not returning a correct
>> halt status from H to P in the above computation is required, they
>> simply assume that it is required. *That is their error*
>

> For crying out loud! It is an error to require what is required by the
> statement of the problem? The central element of the halting problem is
> a *UNIVERSAL* halting decider. And you're saying insisting upon this
> *universality* is an error?
>

I universal halt decider is one thing.

A universal halt decider that must return a correct halt status to an
input that does the opposite of whatever it decides is a much narrower
specification.

void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}

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

Although H cannot possibly return the correct halt status of P(P) to P
because P does the opposite of whatever H Boolean value H returns H can
return the correct halt status to main() after aborting the infinitely
nested simulation specified by P.

> Don't be stupid. There is no error in these proofs.

>
>> The paper shows the actual execution trace of the simulation of P(P) by
>> H cannot possibly ever stop running unless its simulation is aborted.
>

> That's part of the internal design of the alleged H, and has no relevance
> for the proofs we're talking about
>

It is a part of the internal design of halt decider that the proofs
never bothered to consider.

>> Because this is the definition of a computation that never halts
>> H(P,P)==0 is impossibly incorrect.
>

> "Impossibly correct" is meaningless. The point here is that if H is a
> non-halting computation, it is not a halting decider, regardless of
> anything else.
>

X > Y and Y > Z then X > Z follows by logical necessity.
Anything that follows by logical necessity is impossibly incorrect.

[olcott]

On 7/20/2021 5:27 PM, André G. Isaak wrote:
> On 2021-07-20 16:14, olcott wrote:
>> On 7/20/2021 2:49 PM, André G. Isaak wrote:

>>> 'Universal' means it decides all Turing Machines. The latter would
>>> case would be included in 'universal'. so if it cannot return the
>>> correct decision in that case it is not universal.
>>>
>>
>> It is not strictly necessary for a halt decider to return any value to
>> its input. This is merely a false assumption. H in main() aborts the
>> simulation of P before the simulation of H in P ever returns any value
>> to P. All of P including the simulation of H in P is strictly
>> controlled by the H in main():
>
> But it is your contention that your 'decider' *only* aborts an input if
> that input would not otherwise halt.

It took me several days to verify (many months before I began posting
about it) yet it is confirmed that if the outermost H does not abort its
input then no other H ever will.

> If you are forced to abort some
> instance of H you are therefore claiming that that instance does not
> halt on its input, which means that you are acknowledging that your H
> cannot decide all possible inputs. Therefore H is not a universal decider.
>
> Moreover, when P(P) is run independently, neither the uppermost P nor
> the H inside the uppermost P are under the controller of a simulator

The H that is executed rather than simulating by another H is always in
control of its whole simulation chain.

> since they are not being simulated. Therefore, the H inside the
> uppermost P *must* return a value to the uppermost P since there is no
> way for that H to be aborted. So which value does it return?
>
> André
>
>

None-the-less by logical necessity whenever H aborts its input it is
always correct because its input would never ever stop running unless
aborted.

[olcott]

On 7/20/2021 7:34 PM, André G. Isaak wrote:

> But what does the outermost H do *after* it aborts its input? When P(P)
> is run independently, neither the outermost P nor the H which it
> contains are being simulated so they cannot be aborted. So what value
> does the H inside the outermost P return to P?

>

void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}

int main()
{

P((u32)P);
}

P(P) does specify infinitely nested simulation that must be aborted or
it will never stop running. Invoking P(P) in main() merely postpones the
inevitable.

>>> If you are forced to abort some instance of H you are therefore
>>> claiming that that instance does not halt on its input, which means
>>> that you are acknowledging that your H cannot decide all possible
>>> inputs. Therefore H is not a universal decider.
>>>
>>> Moreover, when P(P) is run independently, neither the uppermost P nor
>>> the H inside the uppermost P are under the controller of a simulator
>>
>> The H that is executed rather than simulating by another H is always
>> in control of its whole simulation chain.
>

> When P(P) is executed independently, the outermost P isn't part of any
> simulation chain and is outside the scope of any H.
>

When the outermost P stops running this does not count as halting every
element of the P(P) invocation chain specifies infinitely nested
simulation.

>>> since they are not being simulated. Therefore, the H inside the
>>> uppermost P *must* return a value to the uppermost P since there is
>>> no way for that H to be aborted. So which value does it return?
>>>
>>> André
>>>
>>>
>>
>> None-the-less by logical necessity whenever H aborts its input it is
>> always correct because its input would never ever stop running unless
>> aborted.
>

> That doesn't answer my question. Which value does the H contained in the
> outermost P (the one that isn't emulated) return to P?

The question is whether or not H decides its input correctly.
We know that H does decide its input correctly by logical necessity.

Any other question unrelated to this question is the dishonest dodge
kind of fake rebuttal.

>
> André

[olcott]

On 7/20/2021 9:24 PM, André G. Isaak wrote:

> P(P) specifies a computation which at some point starts a series of
> simulations, but the outermost P isn't part of that series of simulations.

>
>>>>> If you are forced to abort some instance of H you are therefore
>>>>> claiming that that instance does not halt on its input, which means
>>>>> that you are acknowledging that your H cannot decide all possible
>>>>> inputs. Therefore H is not a universal decider.
>>>>>
>>>>> Moreover, when P(P) is run independently, neither the uppermost P
>>>>> nor the H inside the uppermost P are under the controller of a
>>>>> simulator
>>>>
>>>> The H that is executed rather than simulating by another H is always
>>>> in control of its whole simulation chain.
>>>
>>> When P(P) is executed independently, the outermost P isn't part of
>>> any simulation chain and is outside the scope of any H.
>>>
>>
>> When the outermost P stops running this does not count as halting
>> every element of the P(P) invocation chain specifies infinitely nested
>> simulation.
>

> Of course it counts as halting. The outermost P isn't being simulated,
> so it can't be aborted.
>
> I've agreed that when you abort a simulation that doesn't entail that
> the *simulation* halted, because the simulation never reaches one of its
> final states.
>
> But the outermost P *isn't* (and can't be) aborted. It halts by reaching
> one of its final states. That is what it means to halt *by definition*.
> That definitely counts as halting.

>
>>>>> since they are not being simulated. Therefore, the H inside the
>>>>> uppermost P *must* return a value to the uppermost P since there is
>>>>> no way for that H to be aborted. So which value does it return?
>>>>>
>>>>> André
>>>>>
>>>>>
>>>>
>>>> None-the-less by logical necessity whenever H aborts its input it is
>>>> always correct because its input would never ever stop running
>>>> unless aborted.
>>>
>>> That doesn't answer my question. Which value does the H contained in
>>> the outermost P (the one that isn't emulated) return to P?
>>
>> The question is whether or not H decides its input correctly.
>> We know that H does decide its input correctly by logical necessity.
>

> So why not actually answer the question? If H decides its input
> correctly, what answer does the H contained in the outermost P return to
> the outermost P?
>

We know that the input to H does not halt on its input by logical
necessity: We can verify that the input to H never every halts unless H
aborts its simulation of its input:(P, P).

This proves that H does decide its input (P,P) correctly. The halting
problem proofs that claim to prove this is impossible are wrong.

> Does it return 'halts', thereby forcing the outermost P into an infinite
> loop, thereby contradicting the answer given by H, or does it return
> 'doesn't halt', thereby causing the outermost P to *HALT*, also
> contradicting the answer given by H?
>
> It has to be one or the other.

>
>> Any other question unrelated to this question is the dishonest dodge
>> kind of fake rebuttal.
>

> You're the one who appears to be dodging the question. What does the H
> that *isn't* being simulated return to the P that *isn't* being simulated?
>
> Neither of those can be aborted, and if H is truly a decider, it *must*
> return an answer to the outermost P.

[olcott]

On 7/20/2021 10:26 PM, André G. Isaak wrote:

> There's no 'logical necessity' involved here. The definition of
> 'halting' is clear and unambiguous. A computation halts when it reaches

> one of its final states.
>

> If the H contained in the outermost P of P(P) returns 'false', then the
> outermost P *will* reach one of its final states, which means that P(P)
> *does* halt. This clearly and unambiguously demonstrates that whatever
> 'logic' your H is using to decide that P(P) doesn't halt is simply wrong.
>

This would be a contradiction proving that whatever logic that H uses is
wrong except that the logic that H used is verifiably infallible.

This is why I phrased this case as [What if a cat barks?]

If you verify that H did decide that its input never halts correctly and
then a very similar computation does halt, then this is just like
verifying that an animal is a cat by its DNA and then this cat barks.

It is absolutely certain that the input to H(P,P) cannot possibly stop
running unless H aborts its simulation of its input. We verified that
the animal has cat DNA.

When we run int main() { P(P); } P reaches its final state c3f.
The cat barks.

> There is absolutely no way around this fact. You can't simply declare
> that some instances of halting 'don't count' to justify your answer.
> Halting is well-defined. There is absolutely no doubt as to the fact
> that P(P) halts. To claim otherwise is simply delusional.

>
>> This proves that H does decide its input (P,P) correctly. The halting
>> problem proofs that claim to prove this is impossible are wrong.
>>
>>> Does it return 'halts', thereby forcing the outermost P into an
>>> infinite loop, thereby contradicting the answer given by H, or does
>>> it return 'doesn't halt', thereby causing the outermost P to *HALT*,
>>> also contradicting the answer given by H?
>

> And once again you refused to *directly* answer a simply question,
> presumably because you know that a direct answer would demonstrate how
> wrong your reasoning is.
>
> André

[olcott]

On 7/20/2021 11:02 PM, André G. Isaak wrote:

> The problem is that reaching a final state is how halting is *defined*.
>

It is good that you are focusing on reaching final states as the measure
of halting. This currently seems to be a very good measure. It also
proves that I am right about the input to H(P,P) never halting.

The input to H(P,P) never reaches its final state whether or not H
aborts its simulation of this input, thus proving that the input to H
really does never halt.

> Thus, using your silly analogy, the fact that P(P) reaches a final state
> *is* the DNA. Whatever your 'decider' is looking at is something else
> altogether.
>

That the two computations are not identical is why one does not
contradict the other.

No P(P) ever halts unless some H aborts some P.

> As has been pointed out numerous times, by numerous people, the logic by
> which your H decides that P(P) "must" be aborted is faulty, because it
> entirely ignores part of the computation P.
>

It is very simple
No P(P) ever stops running unless some H aborts some P.

> The copy of H inside P is *not* part of the decider. It is part of the
> computation about which H is being asked to make a decision, and it can
> no more be ignored than any other part of the computation P(P) can be
> ignored. Otherwise you're not actually analyzing P(P).
>

It is logically incorrect for any function called in infinite recursion
to return any value to its caller, there is no way around this.

> If you simply compared the result of your H with the *actual* DNA of the
> computation (i.e. whether it reaches a final state when run
> independently),

No P(P) ever stops running unless some H aborts some P.

> you would have realized this months ago and wouldn't
> have wasted your time on this whole pointless (and obviously flawed)
> endeavor.

[olcott]

On 7/21/2021 12:32 AM, André G. Isaak wrote:

> It's not just a good measure. It's the bloody definition. It's the
> *only* thing that actually matters.
>
> The definition of halting is that a computation reaches one of its final
> states in a finite amount of steps.
>
> The definition doesn't mention, or care, about what happens when a
> computation is simulated inside your broken "halt decider".

>
>> It also proves that I am right about the input to H(P,P) never halting.
>>
>> The input to H(P,P) never reaches its final state whether or not H
>> aborts its simulation of this input, thus proving that the input to H
>> really does never halt.
>

> The simulation of P(P) inside H isn't what is being asked about. What is
> being asked about is whether P(P) when run as an actual computation (not
> simply as the input to some alleged simulator) reaches a final state.
>
> It does. Period. Therefore *by definition* it halts.

>
>>> Thus, using your silly analogy, the fact that P(P) reaches a final
>>> state *is* the DNA. Whatever your 'decider' is looking at is
>>> something else altogether.
>>>
>>
>> That the two computations are not identical is why one does not
>> contradict the other.
>

> If you're claiming that P(P) is a different computation when run
> independently than it is when run in your simulator, you're simply
> admitting that your simulator is *not* properly simulating P(P). Thus
> whatever your H has to say about its input is completely and utterly
> irrelevant to the actual computation under consideration.
>

The fact that no P every halts unless some H aborts it proves that H[0]
did decide not halting of P[2] correctly.

int H2(u32 P, u32 I)
{
((int(*)(int))P)(I);
return 1;
}

void P(u32 x)
{
if (H2(x, x))

HERE: goto HERE;
}

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

Here is an example where no halt decider ever aborts its input and its
input never halts.

>> No P(P) ever halts unless some H aborts some P.
>

> No H aborts P(P) when it is run independently because IT ISN'T BEING RUN
> INSIDE H. Its input might be aborted, but that isn't the computation.
> That's the input to the computation. And as you admit above, the input
> isn't actually being accurately simulated.
>

I never admit that the input is not being accurately simulated in that
the behavior of the input under H2 will show the exact same execution
trace as the behavior of the input under H.

P(P) does specify infinitely nested simulation that must be aborted or
it will never stop running. Invoking P(P) in main() merely postpones the
inevitable.

> The behaviour of P(P) is *all* that matters. To accept the claim of your
> simulating 'decider' over the actual behaviour of P(P) is simply daft.
> Its akin to claiming the moon is new because your astrologer told you so
> even when looking out the window clearly shows it to be full.
>

The fact that P never halts when it calls H2 instead of H conclusively
proves that some H must abort some P and when it does this it is
correctly deciding that this input never halts.

> Halting is *defined* in terms of the behaviour of an actual computation.
> It is not defined in terms of any decider. We judge the accuracy of a
> decider based on the actual behaviour. Not vice versa.
>

Not quite, an infinite loop that stops running because it was aborted
could be misconstrued as a halting computation. A computation such as P
that has a final state this is not in the loop of its infinite behavior
can be construed as halting when it reaches this final state. I
currently believe that this is a definitive measure. I may update this
assessment in the future.

>>> As has been pointed out numerous times, by numerous people, the logic
>>> by which your H decides that P(P) "must" be aborted is faulty,
>>> because it entirely ignores part of the computation P.
>>>
>>
>> It is very simple
>> No P(P) ever stops running unless some H aborts some P.
>

> And the P that is aborted is *not* the topmost P. The topmost P actually
> halts. One of the simulations does not.
>

In the computation int main(){ H(P,P); } no P ever reaches any final
state whether or not H aborts and P. This proves beyond all possible
doubt that the input to H never halts.

> But the fact that a simulation is aborted says nothing about its halting
> status.

As I have said far too many times, the fact that unless the simulation
is aborted it can be easily verified on the basis of the execution trace
that the simulation would never end conclusively proves that H did
correctly decide that its input never halts.

The same thing goes for this computation, it never halts unless H does
decide that its input never halts: int main(){ P(P); } This proves that
H decided correctly.

> It simply says that some simulation was not allowed to continue.
> And that simulation was being *conducted* by the outermost P (or rather
> the H inside it). It was that outermost P which *decided* to discontinue
> the simulation *in accordance* to the algorithm which defines that
> computation. And it was at that point that the outermost P *halted*.
>

Even though the outermost P does reach its final state it only reaches
it final state because H correctly decided that its input never halts.

Because of this the argument that the outer P reaches its final state
contradicts that H decided its input correctly DOES NOT HOLD.

There is never a case where H(P,P)==0 is incorrect.

It can be easily verified that that input to H(P,P) never reaches its
final state whether or not H aborts its simulation of this input.

This conclusively proves that its input never halts thus conclusively
proving that H does correctly decide that this input never halts.

> The input to any computation is *not* an actual computation. If you
> decide to partially simulate the input it is still not a computation.
> Halting applies only to actual computations. In this case, the outermost
> *and only* the outermost P acting on the input P.
>
> And that computation halts.
>
> The definition of halting is what it is, regardless of what you want it
> to be.

[olcott]

On 7/20/2021 10:26 PM, André G. Isaak wrote:

> There's no 'logical necessity' involved here. The definition of

> 'halting' is clear and unambiguous. A computation halts when it reaches

> one of its final states.
>

That really does add much better focus to the dialogue, good job. This
allows a much more precise measure of the correctness of the halt status
decision of H on its input.

Every input to H that never reaches its final state (whether or not H
aborts its simulation of this input) is an input that H correctly
decides never halts.

This works just fine for infinite loops, infinite recursion and P(P). We
can know that H(P,P)==0 is correct because the x86 execution trace of
P(P) conclusively proves that it never reaches a final state.

When the P of int main(){ P(P); } does reach a final state it only does
so because H(P,P)==0 is correct, thus deriving a paradox rather than a
contradiction.

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

> If the H contained in the outermost P of P(P) returns 'false', then the
> outermost P *will* reach one of its final states, which means that P(P)
> *does* halt. This clearly and unambiguously demonstrates that whatever
> 'logic' your H is using to decide that P(P) doesn't halt is simply wrong.
>

> There is absolutely no way around this fact. You can't simply declare
> that some instances of halting 'don't count' to justify your answer.
> Halting is well-defined. There is absolutely no doubt as to the fact
> that P(P) halts. To claim otherwise is simply delusional.
>

>> This proves that H does decide its input (P,P) correctly. The halting
>> problem proofs that claim to prove this is impossible are wrong.
>>
>>> Does it return 'halts', thereby forcing the outermost P into an
>>> infinite loop, thereby contradicting the answer given by H, or does
>>> it return 'doesn't halt', thereby causing the outermost P to *HALT*,
>>> also contradicting the answer given by H?
>

> And once again you refused to *directly* answer a simply question,
> presumably because you know that a direct answer would demonstrate how
> wrong your reasoning is.
>
> André
>

[olcott]

When we apply a global halt decider to int main() { P(P); } (the exact
same code as the local halt decider) it aborts its simulation of the
P(P) in main(). The only reason for the prior paradox is that part of
the full computation of P(P) had been hidden from the view of H. When it
is no longer hidden then the paradox goes away.

[olcott]

On 7/21/2021 12:29 PM, André G. Isaak wrote:

> No. If H aborts a simulation of its input that tells us nothing more
> than that H aborted a simulation of its input. It tells us nothing about
> whether H correctly decided that the input was non-halting. That would
> require an actual proof that the input was non-halting. All your useless
> traces do not constitute proofs of this.
>

If you know the x86 language then you can verify by the
[Begin Local Halt Decider Simulation at Machine Address:c25]
execution trace of the simulation of P(P) that the input to H never ever
reaches any final state whether or not H aborts its simulation of this
input. This conclusively proves that this input never halts which in
turn conclusively proves that H(P,P)==0 is correct.

If you don't know the x86 language then you are unqualified to evaluate
my work.

// Simplified Linz Ĥ (Linz:1990:319)
// Strachey(1965) CPL translated to C

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

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

>> This works just fine for infinite loops, infinite recursion and P(P).
>> We can know that H(P,P)==0 is correct because the x86 execution trace
>> of P(P) conclusively proves that it never reaches a final state.
>

> No. The execution trace simply shows that H aborts the simulation. It
> doesn't provide *any* evidence either way regarding whether the
> simulation would have eventually reached a final state. For that you
> need to actually look at P(P).

>
>> When the P of int main(){ P(P); } does reach a final state it only
>> does so because H(P,P)==0 is correct, thus deriving a paradox rather
>> than a contradiction.
>

> And the difference between a paradox and a contradiction is...?
>
> Your H(P, P) contradicts the actual behavior of P(P). That's all that
> matter. It's a contradiction and no amount of mental gymnastics on your
> part will change this. Renaming it as a 'paradox' doesn't change this.

[olcott]

On 7/21/2021 1:19 PM, André G. Isaak wrote:

> It shows absolutely no such thing.
>
> Your trace merely shows that a particular call is made twice. It
> provides no evidence whatsoever that this represents a pattern that will
> continue indefinitely.
>

It need not show that it is a pattern that continues indefinitely. It
only needs to show that there is no case where P ever reaches its final
state. This by itself is conclusive proof that P never halts.

Only because of your suggestion to focus on reaching a final state as
the definition of halting it is perfectly clear that the input to H(P,P)
never ever halts. Thanks for that.

> To demonstrate that, you'd need to show that the machine is in the
> *exact* same state when both of these calls are made. Your trace doesn't
> do this since it doesn't provide us any information about the contents
> of registers or memory.
>
> And, since your trace entirely omits whatever it is that occurs at
> address 955, we have absolutely no way to determine how the machine
> state might be affected by this call.
>
> Traces aren't proofs. Proofs are proofs. Proofs have premises and
> conclusions linked by rules of inference. Traces do not.

[olcott]

On 7/21/2021 2:22 PM, André G. Isaak wrote:

> And how exactly does it show this?
>
> All your trace shows is that it has not *yet* reached a final state at
> the point when your H decides to abort the simulation. That hardly
> qualifies as evidence, let alone proof, that "there is no case where P

> ever reaches its final state".
>

The x86 execution trace of the simulation of P(P) combined with the x86
source-code of P proving that the execution trace is correct proves that
H either continues to simulate P(P) in which case P never reaches its
final state or H stops simulating P(P) at some point in which case P
never reaches its final state.

Begin Local Halt Decider Simulation at Machine Address:c25

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

[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/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

> Running P(P) independently where there is no possibility of aborting it
> clearly shows that it *does* reach a final state.

[olcott]

On 7/21/2021 3:07 PM, Richard Damon wrote:

> On 7/21/21 10:51 AM, olcott wrote:
>
>> If you know the x86 language then you can verify by the
>> [Begin Local Halt Decider Simulation at Machine Address:c25]
>> execution trace of the simulation of P(P) that the input to H never ever
>> reaches any final state whether or not H aborts its simulation of this
>> input. This conclusively proves that this input never halts which in
>> turn conclusively proves that H(P,P)==0 is correct.
>

> SInce I DO know something of the x86 assembly language, I have pointed
> out a number of errors.
>
> Note, P0 was NEVER aborted and reached its terminal Halt state, thus BY
> DEFINITION, is a Halting Computation, at least with your current
> definition of H (and a different definition of H will give a different
> definition of the machine P since it includes the algorithm of H as part
> of its algorithm)
>

Yes and then we have the paradox that H(P,P)==0 is the correct halt
status of the input to H.

> Right here, H shows that it makes an inaccurate trace of the execution.
> H SHOULD show the simulation of the Halt Decider, as THAT is what is
> really being run under the simulated P1
>
> At very least, we need a conditional marker as the code in H has
> conditional execution
>

This does not matter because P never reaches its final state no matter
what H does or does not do. This conclusively proves that the input to H
never halts which conclusively proves that H(P,P)==0 is the correct halt
status for the input to H.

>> [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 P2.

> Actually, H0 aborted its simulation of P1 not P2 (as P1 doesn't continue
> either) and H0 really shouldn't be simulating P2 but should be
> simulating H1 simulating P2.
>

H0 is simulating P1 calling H1 simulating P2.
All of this is data that H0 generates as a pure function of its input.

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

> Right HERE. P(P) has Halted. PROOF H is wrong.

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

> In summary:
>
> P(P) at the top level ran to completion and it reached it Halt state, so
> it is a Halting Computation.
>

André has convinced me of this on the basis that it reaches its own
final state of c3f.

> H(P,P) returned the value defined to represent a Non-Halting
> Computation, and thus is wrong.
>

No it is not wrong. That is why it is a paradox and not a contradiction.
The input to H cannot possibly ever reach its final state thus
conclusively proving that H(P,P)==0 is the correct halt status of the
input to H.

> H makes its error because it incorrect seems to assume that other copies
> of H are not going to abort their simulation, and since they will, it
> gets the wrong answer.
>

If you understand the x86 language then you can see that the execution
trace of the simulation of P(P) cannot possibly reach its final state.

It does not matter whether this simulation is aborted, when it is
aborted, which copy of H aborts it and even if it is never aborted. In
no possible scenario does the input to H(P,P) ever reach its final
state. This conclusively proves that H(P,P)==0 is correct.

[olcott]

On 7/21/2021 3:12 PM, Richard Damon wrote:

> Nope, since H WILL abort the simulation, as the trace shows, then it is
> clear that P(P) will halt.
>
> This is major logical flaw you are making, you HAVE an H that aborts,
> but you then presume that H will not abort.
>
> Since the Machine P is based on the machine H, you MUST use the right
> definition of H when you analyze P. (Something you don't seem to
> understand).
>
> This makes your logic UNSOUND, and just flat out WRONG.

*The fact that under no case what-so-ever does the input to H(P,P) ever
reach any final state conclusively proves that H(P,P)==0 is correct*

*The fact that under no case what-so-ever does the input to H(P,P) ever
reach any final state conclusively proves that H(P,P)==0 is correct*

*The fact that under no case what-so-ever does the input to H(P,P) ever
reach any final state conclusively proves that H(P,P)==0 is correct*

*The fact that under no case what-so-ever does the input to H(P,P) ever
reach any final state conclusively proves that H(P,P)==0 is correct*

*The fact that under no case what-so-ever does the input to H(P,P) ever
reach any final state conclusively proves that H(P,P)==0 is correct*

[olcott]

On 7/21/2021 4:06 PM, André G. Isaak wrote:

> And HOW exactly does it show this? Just stating that it "shows" this is
> a non-answer. You need to *prove* this, not just state it.
>
> For starters, we don't actually *have* the source code of P, just a
> skeleton.
>

That is so ridiculously false that it must be an intentional lie and no
plausibly honest mistake.

void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}

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

You have the freaking C source-code, x86 source-code and x86 machine
language.

> Second, showing that 995 is called twice in a row doesn't establish that
> there is infinite recursion. It establishes that 995 is called twice in
> a row, nothing more.

We can know by this execution trace that simulating halt decider H
either continues to simulate P(P) or fails to simulate P(P) and in
neither case does simulated P(P) ever reach its final state of c3f.

> Unless, as I pointed out above, you can demonstrate
> that the machine is in the *exact* same state, the presence of two calls
> in succession does *not* demonstrate that the recursion will be infinite.
>

I do not freaking have to show that the recursion is infinite I only
have to show that the simulated P(P) never reaches its final state of
c3f. That by itself conclusively proves that the simulated P(P) never
halts.

H(P,P)==0 only means that the input to H never halts.
(a) It never halts if no H ever aborts its input
(b) It never halts if some H aborts its input

As long as H is a simulating halt decider that is a pure x86 simulator
of its input until its input demonstrates that it will never stop
running the above set of two possibilities is exhaustively complete.

> André

[olcott]

On 7/21/2021 4:09 PM, André G. Isaak wrote:
> On 2021-07-21 13:44, olcott wrote:
>> On 7/21/2021 2:26 PM, André G. Isaak wrote:
>>> On 2021-07-21 12:54, olcott wrote:
>>>> On 7/21/2021 1:26 PM, André G. Isaak wrote:
>>>
>>>>> Your idea of a 'global decider' is simply rubbish. The Linz proof
>>>>> requires that H_Hat be derived from your halt decider. If you
>>>>> create a new 'global' decider, then you need to create a new H_Hat
>>>>> to go along with it.
>>>>>
>>>>
>>>> It is the same halt decider with global scope.
>>>> It is like the Java sandbox, nothing can run outside of it.
>>>
>>> This comment is entirely irrelevant to *anything* which I wrote. Why
>>> did you even bother with this reply? Do you have no *substantive*
>>> response to the points I make below?
>>>
>>
>> My idea of a global decider is not rubbish.
>
> And once again, you fail to address the points below.
>
> When we run P(P) independently it reaches a final state. That is
> absolute, incontrovertible evidence that P(P) is a halting computation.
> That is the *definition* of halting, and is thus the *only* criterion
> which counts for establishing that something is halting.
>
> Establishing that something is non-halting is more complicated since
> just running it won't work, but in cases where something *does* halt
> when run, no additional evidence is needed to state categorically that
> it halts.

>

*The fact that under no case what-so-ever does the input to H(P,P) ever

reach any final state conclusively proves that H(P,P)==0 is correct*

The fact that P of int main(){ P(P); } does reach its final state proves
that P halts.

P(P) halts and H(P,P)==0 are both correct.
"This sentence is not true." is indeed not true. (It is not a truth bearer).

> André
>
>>>>> And when we run P(P), nothing is being "hidden" from H *because H
>>>>> isn't even running*. P(P) is running and P(P) halts.
>>>>>
>>>>> If P(P) halts when you run it, that is *definitive* proof that P(P)
>>>>> halts.
>>>
>>> Just to expand the above point, when we can run P(P) independently
>>> and observe that it *does* reach a final state, why do we even *need*
>>> to run a halt decider (global or otherwise)? We've already *got* the
>>> answer to the question that the halt decider is purportedly answering.

[olcott]

On 7/21/2021 4:32 PM, Richard Damon wrote:

> FALSE.
>
> If that was true, the a simulating Halt Decider that just immediately
> aborted EVERY simulation and said its input was non-halting would be
> right by exactly the same logic.

Yes that is correct yet does not apply to the current case.
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 other possibility in this specific scenario is that H stops
simulating its input and again its input never reaches its final state.
This in this exact scenario it is dead certain that H(P,P)==0 is correct.

>
> It isn't,
>
> So, it isn't
>
> Can you PROVE your statement, taking into account this counter?
>
> No. Because it is false.
>
> Note, that if we replace the top level H(P,P) with UTM(P,P), i.e. make
> your decider not halt, it will still complete its simulation, thus
> showing that H did not NEED to abort it simulation and thus was wrong.
>
> Again, you are repeating your self thinking that adding volume to your
> statement somehow makes it more right, when it just makes it more wrong.

[olcott]

On 7/21/2021 4:57 PM, André G. Isaak wrote:

> That is a *skeleton*. You have never provided the source code for H()

No that is the complete code for every single aspect of P.

> which is the part that does the majority of the work inside P(). Without
> that code we don't have complete source code for P().

That is flatly false and you know it.

The fact that H is defined to be a pure x86 emulator until it matches a
self-evidently correct non-halting behavior pattern on its input is
almost all that needs to be known about H.

The only other thing that must be known about H is because H acts as a
pure x86 emulator until it matches a self-evidently correct non-halting
behavior pattern on its input this means that it can completely ignore
its entire address range in the halt analysis of the execution trace of
any input without having any effect what-so-ever on this halt status
decision.

The above details about H prove that the 14 lines of execution trace of
the simulation of P(P) are the end-all be-all entire basis of the halt
status decision.

>
> Tell me, what does the following source code do:
>
> int foo(int x, int y) {
>     if foo2(&x) != foo3(&y)
>         return (x + y)
>     else HERE:
>         goto HERE;
> }
>
> Source code of a function which calls other, undefined, functions is
> *not* complete source code.

>
>>> Second, showing that 995 is called twice in a row doesn't establish
>>> that there is infinite recursion. It establishes that 995 is called
>>> twice in a row, nothing more.
>>
>> We can know by this execution trace that simulating halt decider H
>> either continues to simulate P(P) or fails to simulate P(P) and in
>> neither case does simulated P(P) ever reach its final state of c3f.
>

> How on earth does your trace show that? You abort the simulation. The
> trace cannot possibly show whether a final state would have been reached
> had the simulation been allowed to continue past the point where you
> abort it.

>
>>> Unless, as I pointed out above, you can demonstrate that the machine
>>> is in the *exact* same state, the presence of two calls in succession
>>> does *not* demonstrate that the recursion will be infinite.
>>>
>>
>> I do not freaking have to show that the recursion is infinite I only
>> have to show that the simulated P(P) never reaches its final state of
>> c3f.
>

> No. You have to show that the simulated P(P) would have never reached
> its final state c3f had your simulator allowed the simulation to
> continue. YOU DON'T DO THIS.

When we have the above details of the behavior and design of H then we
know that every call to H(P,P) shown below repeats the sequence that
never reaches final state c3f.

When H recognizes this infinite behavior pattern it stops simulating its
input and P never reaches its final state of c3f.

Within the stipulated design of H and the stipulated code of P the input
to H cannot possibly reach its final state.

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




>

>> That by itself conclusively proves that the simulated P(P) never halts.
>

> No. It does not.

[olcott]

On 7/21/2021 5:59 PM, André G. Isaak wrote:

> It is not false at all, flatly or otherwise. P is supposed to be an
> independent, *self-contained* machine. Any and all code called by P is
> *part* of the computation performed by P. Unless your "source code" for
> P can be successfully linked, it is not the complete source code for P().
>

You can see by the code (if you bother to pay any attention) that no
linking is required. The x86utm operating system directly executes the
COFF object file output of the Microsoft C compiler. The link step is
expressly not allowed.

>> The fact that H is defined to be a pure x86 emulator until it matches
>> a self-evidently correct non-halting behavior pattern on its input is
>> almost all that needs to be known about H.
>

> How H is *defined* is not what we're interested in. We need to know how
> it is *implemented*. You have defined it to behave in a particular way
> without providing any evidence that your implementation actually behaves
> in that way, or whether it is even possible for a program to behave as
> you allege it does.
>

It is trivial to understand that H could easily be implemented to have
the stipulated functionality.

When I say that H is an x86 emulator this is immediately understood to
be easily possible. When I say that H steps though its input in machine
language instruction at a time, this is also immediately understood to
be easily possible. I say all of this in my paper I am not going to
repeat it again.

>> The only other thing that must be known about H is because H acts as a
>> pure x86 emulator until it matches a self-evidently correct non-halting
>

> Except it *doesn't* act as a pure x86 emulator until it matches some
> non-halting pattern.
>
> It performs tests which a pure x86 emulator does not perform.

That is an extraneous detail. H has no behavior that can possibly have
any effect on the behavior of its input thus no behavior that can
possibly have any effect on its halt status decision until after if halt
status decision is fully formed. Thus H is functionally equivalent to a
pure simulator on its input.

Saying this in short-hand eliminating all of the extraneous details:
H acts as a pure simulator of its input.

> Or are you
> suggesting that it only starts testing to see whether things match a
> given pattern *after* it has detected that pattern? That would be quite
> a feat.

>
>> behavior pattern on its input this means that it can completely ignore
>> its entire address range in the halt analysis of the execution trace
>> of any input without having any effect what-so-ever on this halt
>> status decision.
>>
>> The above details about H prove that the 14 lines of execution trace
>> of the simulation of P(P) are the end-all be-all entire basis of the
>> halt status decision.
>

> No, they do not. They prove nothing since they do not include the code
> to H itself. If you think otherwise, tell me whether my foo below called
> with input parameters (6, 7) is an infinite loop or not. You should be
> able to do this since by your standards I have given you its "complete"
> source code.
>

I explained that H <is> a pure simulator of its input until after it
makes its halt status decision. From this one detail we can know that
this source-code of P specifies infinitely nested simulation at its
machine address c30.

void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}

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

Because it is certainly not beyond any stretch of the imagination to
accept that C functions can implement x86 emulators your claim that you
won't believe it until you see the code is ridiculous.

> Rubbish.

>
>> When H recognizes this infinite behavior pattern it stops simulating
>> its input and P never reaches its final state of c3f.
>

> Except that you provide no proof that H has correctly recognized a
> pattern of infinite behavior.

I provide it again and again and you keep ignoring it.
You do as Ben does and nitpick one little irrelevant detail or another
and make sure to ignore the essence of what is being said.


> And we can categorically state that it has
> not based on the following trivial fact:
>
> WHEN WE RUN P(P) IT REACHES A FINAL STATE.

>
>> Within the stipulated design of H and the stipulated code of P the
>> input to H cannot possibly reach its final state.
>

> Rubbish.