Re: Halting problem erroneously defined

[olcott]

On 7/15/2021 12:22 PM, Mr Flibble wrote:
> Hi!
>
> From Wikipedia Halting Problem page:
>
> For any program f that might determine if programs halt, a
> "pathological" program g, called with some input, can pass its
> own source and its input to f and then specifically do the
> opposite of what f predicts g will do. No f can exist that
> handles this case.
>
> To me this looks like everyone is assuming that the halting problem is
> undecidable based on a misunderstanding of the contradiction
> crystallized by [Strachen 1965].
>
> Strachen isn't saying the halting problem is undecidable, he is saying that
> there is a contradiction that means that a decider can not be a part of
> or called by that which is being decided. This doesn't mean that the
> halting problem is not undecidable but it does mean that if that
> Wikipedia extract is the current state of the art then nobody has proven
> that the HP is undecidable, at least for non-"pathological" programs.
>
> Olcott is on to something. :)
>
> /Flibble
>

I am really glad that you are back.
Strachen <is> saying that the halting problem is undecidable.

The Sipser proof has the same Liar Paradox pathological
self-reference(Olcott 2004).

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. That is, it rejects if M accepts and accepts if M does not
accept. The following is a description of D:

D(⟨M⟩) = { accept if M does not accept ⟨M⟩
{ reject if M accepts ⟨M⟩

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


--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

[Mr Flibble]

On Thu, 15 Jul 2021 12:42:22 -0500
olcott <No...@NoWhere.com> wrote:

> On 7/15/2021 12:22 PM, Mr Flibble wrote:
> > Hi!
> >
> > From Wikipedia Halting Problem page:
> >
> > For any program f that might determine if programs halt, a
> > "pathological" program g, called with some input, can pass
> > its own source and its input to f and then specifically do the
> > opposite of what f predicts g will do. No f can exist that
> > handles this case.
> >
> > To me this looks like everyone is assuming that the halting problem
> > is undecidable based on a misunderstanding of the contradiction
> > crystallized by [Strachen 1965].
> >
> > Strachen isn't saying the halting problem is undecidable, he is
> > saying that there is a contradiction that means that a decider can
> > not be a part of or called by that which is being decided. This
> > doesn't mean that the halting problem is not undecidable but it
> > does mean that if that Wikipedia extract is the current state of
> > the art then nobody has proven that the HP is undecidable, at least
> > for non-"pathological" programs.
> >
> > Olcott is on to something. :)
> >
> > /Flibble
> >
>
> I am really glad that you are back.
> Strachen <is> saying that the halting problem is undecidable.

No he isn't he is saying a decider cannot decide a program that is
aware of the decider, i.e. is "pathological". So, given two things:

(1) a decider that can decide non-pathological programs, and
(2) a decider that can detect if a program is pathological (i.e. is
aware of the decider),

then:

the halting problem becomes decidable.

Unless I am missing something.

/Flibble

[Mr Flibble]

Of course for (2) to be feasible the decider would probably have to be
a black box .. but I am HP newbie so I am merely thinking out loud. :D

/Flibble

[olcott]

If you check with Mike, Ben and Kaz they will all tell you that the
halting problem is considered undecidable because of the pathlogical input.

[olcott]

My halt decider does correctly decide the pathological input by first
removing the pathology. H isolates itself from having any effect on its
halt status decision by only acting as a pure simulator of its input
until after its halt status decision has been made.

[Mr Flibble]

On Thu, 15 Jul 2021 13:04:42 -0500

Unless I am mistaken you can't do that: the candidate program can call a
function EQUIVALENT (i.e. different implementation but same result) as
your decider; you would need to be able to detect such an equivalence.

/Flibble

[olcott]

I address the Peter Linz instance of that at the end of my paper:
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

It is still very obviously infinitely nested simulation.
It is merely more difficult for the halt decider to detect.

[olcott]

On 7/15/2021 2:08 PM, Mike Terry wrote:

> On 15/07/2021 18:22, Mr Flibble wrote:
>> Hi!
>>
>>  From Wikipedia Halting Problem page:
>>
>>     For any program f that might determine if programs halt, a
>>     "pathological" program g, called with some input, can pass its
>>     own source and its input to f and then specifically do the
>>     opposite of what f predicts g will do. No f can exist that
>>     handles this case.
>

> Well, that's awful wording, because it's liable to give readers the
> impression that some specific g exists which no decider could decide
> correctly.  That would be nonsense - the fact is that g is derived from
> f, so it would be better to call it N(f) or something [N for Nemesis!].
>
> Then we could say clearly that no f can exist that handles its own N(f)
> case.  This implies that every f gets at least one input wrong (e.g.
> N(f)), so no f can correctly decide halting for all inputs.
>

It is the same freaking pathological self-reference(olcott 2004) as the
liar paradox:

Peter Olcott Sep 5, 2004, 11:21:57 AM
The Liar Paradox can be shown to be nothing more than
a incorrectly formed statement because of its pathological
self-reference. The Halting Problem can only exist because
of this same sort of pathological self-reference.
https://groups.google.com/g/comp.theory/c/RO9Z9eCabeE/m/Ka8-xS2rdEEJ

> Note that it's the ORDER of choices which is important:  FIRST f is
> fixed, THEN  N(f) becomes defined (fixed) as a consequence, and f
> decides N(f) incorrectly.  (Another decider h may decide N(f) correctly,
> but of course that h won't decide N(h) correctly and so on.)

>
>>
>> To me this looks like everyone is assuming that the halting problem is
>> undecidable based on a misunderstanding of the contradiction
>> crystallized by [Strachen 1965].
>

> Do you have a link for [Strachen 1965]?  The only link I've been able to
> find is a short letter of just three paragraphs, here:
>
>   <https://academic.oup.com/comjnl/article/7/4/313/354243>
>
> I'll assume that's what you're referring to??

That is all there is to it. Apparently Strachen is responsible for the
simplification found in all the modern proofs. He wrote his proof in the
CPL language that he created, ancestor to BCPL, B and C.

>>
>> Strachen isn't saying the halting problem is undecidable,
>

> Dude, YES HE IS:
> Quote:
>   This left me with an uneasy feeling that the proof must be long
>   and complicated, but in fact it is so short and simple it may be
>   of interest to casual readers.
>
> HE'S CONFIRMING THAT THE THEOREM IS CORRECT, and has a short proof which
> he then outlines!
>

Of this we agree.
Flibble was trying to credit Strachen 1965 with Olcott 2004.

>
>> He saying that

>> there is a contradiction that means that a decider can not be a part of
>> or called by that which is being decided.
>

> Dude, HE'S NOT SAYING THAT.
>
> Quote:
>   ...In each case T(P) has exactly the wrong value, and this
>   contradiction SHOWS THAT THE FUNCTION T CANNOT EXIST.
>
> [My CAPS.  T is the purported halt decider.]  Where does Strachen say
> anything about "a decider can not be a part of or called by that which
> is being decided"?
>
> Get a grip!  JUST READ THE WORDS... :/
>
>
> Mike.
>


He does have a deeper understanding of the malformed nature of the HP
better than anyone besides me. It has the exactly same
self-contradiction as the liar paradox.

All the academicians in the world still do not even understand that the
Liar Paradox is logically incoherent. I had to create minimal type
theory to even formally express that error of the Liar Paradox:

P := ~True(LP)


https://www.researchgate.net/publication/331859461_Minimal_Type_Theory_YACC_BNF

[olcott]

On 7/15/2021 7:29 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 7/15/2021 5:06 PM, Ben Bacarisse wrote:

>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> It is the same freaking pathological self-reference(olcott 2004) as
>>>> the liar paradox:
>>>>
>>>> Peter Olcott Sep 5, 2004, 11:21:57 AM

>>> The halting problem is not like the liar paradox in that every program P
>>> either does or does not halt when given input I.
>>
>> It is exactly like the liar paradox in one crucial way:
>>
>> The Liar paradox is neither true nor false because both true and false
>> values are contradicted.
>
> No. If you've forgotten, just go back and read any of the posts I've
> made over the last 16 years where I explain why that analogy is a false
> one. I used to repeat myself in case some innocent reader might take
> you seriously, but I think all students reading this group will be able
> to tell that you are, well, let's just say "confused".
>

The aspect that in both cases their Boolean value is contradicted is the
key analogous aspect.

Your God damned dishonest dodge fake rebuttal of pointing out there is
another aspect where they are not analogous is what a lying cheating
scoundrel would do to artificially contrive a fake rebuttal that would
fool the gullible.

>> 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. http://www.liarparadox.org/sipser_165.pdf
>>
>> All the modern proofs are based on an input doing the opposite of
>> whatever its decider decides.
>
> Some are. I am glad you agree that what is in Sipser is a proof of the
> theorem he states. Can you move on now, or did you just use that word
> by accident?
>

They are referred to as the proofs. If I referred to them as the halting
problem misconceptions you would have no idea that I was referring to
Sipser, Linz and Kozen.

[olcott]

On 7/15/2021 8:49 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 7/15/2021 7:29 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 7/15/2021 5:06 PM, Ben Bacarisse wrote:
>>>>> olcott <No...@NoWhere.com> writes:
>>>>>
>>>>>> It is the same freaking pathological self-reference(olcott 2004) as
>>>>>> the liar paradox:
>>>>>>
>>>>>> Peter Olcott Sep 5, 2004, 11:21:57 AM
>>>>> The halting problem is not like the liar paradox in that every program P
>>>>> either does or does not halt when given input I.
>>>>
>>>> It is exactly like the liar paradox in one crucial way:
>>>>
>>>> The Liar paradox is neither true nor false because both true and false
>>>> values are contradicted.
>>> No. If you've forgotten, just go back and read any of the posts I've
>>> made over the last 16 years where I explain why that analogy is a false
>>> one. I used to repeat myself in case some innocent reader might take
>>> you seriously, but I think all students reading this group will be able
>>> to tell that you are, well, let's just say "confused".
>>
>> The aspect that in both cases their Boolean value is contradicted is
>> the key analogous aspect.
>

> You are deliberately vague about "the aspect" since you know full well
> that every instance of the halting problem has a correct yes/no answer
> which seems to be very different to the liar paradox.
>

"This sentence is not true"
If the Liar Paradox is true that makes it true that it is not true AKA
false.

If the Liar paradox is false that makes not true that it is not true AKA
true.

If the C equivalent of the Strachey (1965) CPL returns true(halts) to P
then P loops. If it returns false(does not halt) to P then P halts.

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

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

The self-contradiction of the halting problem counter-examples is
apparently modeled after the liar paradox.

I continue to hope against hope that you simply misunderstand this and
will eventually agree that I am correct. I think that the problem with
this hope is that the enormous weight of evidence is on the side that
you are a lying scoundrel about my halting problem insights.

> In fact, in order to suggest a similarity you have to pretend that the
> halting problem is not as I, and many other have stated it.

>
>> Your God damned dishonest dodge fake rebuttal of pointing out there is
>> another aspect where they are not analogous is what a lying cheating
>> scoundrel would do to artificially contrive a fake rebuttal that would
>> fool the gullible.
>

> Get a grip, man! Stating what the halting problem is and making it
> clear that every instance has a correct yes/no answer is not rebutting
> anything. It's stating the issue so that you can choose to address it
> if the fancy takes you.

>
>>>> 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. http://www.liarparadox.org/sipser_165.pdf
>>>>
>>>> All the modern proofs are based on an input doing the opposite of
>>>> whatever its decider decides.
>>> Some are. I am glad you agree that what is in Sipser is a proof of the
>>> theorem he states. Can you move on now, or did you just use that word
>>> by accident?
>>
>> They are referred to as the proofs. If I referred to them as the
>> halting problem misconceptions you would have no idea that I was
>> referring to Sipser, Linz and Kozen.
>

> You need to find some way to say what you mean clearly. In the past,
> I've tried to help with that but you are not a fan of such posts so I
> will leave it up to you. If you don't consider them proofs, you should
> not call them proofs. If you do, readers are allowed to take you at
> your word.
>

The problem with that is that you simply ignore perfect clarity because
perfect clarity is inconsistent with your goal of rebuttal:

The problem with that is that you simply ignore perfect clarity because
perfect clarity is inconsistent with your goal of rebuttal:

The problem with that is that you simply ignore perfect clarity because
perfect clarity is inconsistent with your goal of rebuttal:

You ask someone (we'll call him "Jack") to give a truthful
yes/no answer to the following question:

Will Jack's answer to this question be no?

Jack can't possibly give a correct yes/no answer to the question.
https://groups.google.com/g/sci.logic/c/4kIXI1kxmsI/m/hRroMoQZx2IJ
Daryl McCullough Jun 25, 2004, 6:30:39 PM

Daryl did not at the time appreciate that he provided the perfect
analogy of the error of the halting problem. I contacted him very
recently and it seems that he still does not understand this. His
analogy goes into much greater depth with additional examples.

For Jack both yes and no are the wrong answer even though the question
does have a correct answer when posed to other people it has no correct
answer when posted to Jack.

[olcott]

On 7/16/2021 7:25 AM, Mr Flibble wrote:

> On Thu, 15 Jul 2021 20:08:00 +0100
> Mike Terry <news.dead.p...@darjeeling.plus.com> wrote:
>
>> On 15/07/2021 18:22, Mr Flibble wrote:
>>> Hi!
>>>
>>> From Wikipedia Halting Problem page:
>>>
>>> For any program f that might determine if programs halt, a
>>> "pathological" program g, called with some input, can pass
>>> its own source and its input to f and then specifically do the
>>> opposite of what f predicts g will do. No f can exist that
>>> handles this case.
>>
>> Well, that's awful wording, because it's liable to give readers the
>> impression that some specific g exists which no decider could decide
>> correctly. That would be nonsense - the fact is that g is derived
>> from f, so it would be better to call it N(f) or something [N for
>> Nemesis!].
>>
>> Then we could say clearly that no f can exist that handles its own
>> N(f) case. This implies that every f gets at least one input wrong
>> (e.g. N(f)), so no f can correctly decide halting for all inputs.
>>

>> Note that it's the ORDER of choices which is important: FIRST f is
>> fixed, THEN N(f) becomes defined (fixed) as a consequence, and f
>> decides N(f) incorrectly. (Another decider h may decide N(f)
>> correctly, but of course that h won't decide N(h) correctly and so
>> on.)
>>
>>>
>>> To me this looks like everyone is assuming that the halting problem
>>> is undecidable based on a misunderstanding of the contradiction
>>> crystallized by [Strachen 1965].
>>
>> Do you have a link for [Strachen 1965]? The only link I've been able
>> to find is a short letter of just three paragraphs, here:
>>
>> <https://academic.oup.com/comjnl/article/7/4/313/354243>
>>
>> I'll assume that's what you're referring to??
>>
>>>

>>> Strachen isn't saying the halting problem is undecidable,
>>
>> Dude, YES HE IS:
>> Quote:
>> This left me with an uneasy feeling that the proof must be long
>> and complicated, but in fact it is so short and simple it may be
>> of interest to casual readers.
>>
>> HE'S CONFIRMING THAT THE THEOREM IS CORRECT, and has a short proof
>> which he then outlines!
>>
>>

>>> He saying that
>>> there is a contradiction that means that a decider can not be a
>>> part of or called by that which is being decided.
>>
>> Dude, HE'S NOT SAYING THAT.
>>
>> Quote:
>> ...In each case T(P) has exactly the wrong value, and this
>> contradiction SHOWS THAT THE FUNCTION T CANNOT EXIST.
>>
>> [My CAPS. T is the purported halt decider.] Where does Strachen say
>> anything about "a decider can not be a part of or called by that
>> which is being decided"?
>>

He never says anything like:

a decider can not be a part of or called by that
which is being decided.

When he says that function T cannot exist he means that a universal halt
decider cannot exist.

You and I are the only ones that understand that it is an error for the
behavior of the halt decider to be a part of the halt deciding decision.
I named this the pathological self-reference(Olcott 2004) error.

My halt decider gets around that problem by remaining a pure simulator
of its input until after the halt status decision has been made.

>> Get a grip! JUST READ THE WORDS... :/
>

> You are making exactly the same mistake as everyone else. READ MY WORDS.
>
> /Flibble

[olcott]

> NO HE ISN'T. He is saying that T cannot exist as a decider of P because
> P is aware of T and attempts to defeat it; this DOES NOT MEAN that a T
> cannot decide P where P isn't attempting to defeat T by recursively
> referencing it. This is why Strachen refers to is as an "impossible
> program".
>
> /Flibble
>

Conventionally it is understood that the instance of P proves that there
cannot be any T that always correctly decides the halting status of
every input.

In the case of my H and P, because my H is a simulating halt decider
that only acts as a pure simulator until after its halt status decision
is made the pathological self-reference(olcott 2004) error that you
correctly object to has no effect on either the behavior of P or the
halt status decision of H.

H aborts the simulation of its input before any nested H ever returns
any value to any P. This utterly nullifies the prior issue that seemed
to prove that P is undecidable.

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

[olcott]

On 7/16/2021 9:44 AM, Alan Mackenzie wrote:

> Mr Flibble <fli...@reddwarf.jmc> wrote:
>> On Thu, 15 Jul 2021 20:08:00 +0100
>> Mike Terry <news.dead.p...@darjeeling.plus.com> wrote:
>

> [ .... ]

>
>>> HE'S CONFIRMING THAT THE THEOREM IS CORRECT, and has a short proof
>>> which he then outlines!
>

>> NO HE ISN'T. He is saying that T cannot exist as a decider of P ....
>
> He's saying that T cannot exist as a _universal_ decider, because there
> exists a program it cannot decide correctly.
>
>> .... because P is aware of T and attempts to defeat it;
>
> That's unsuitably anthropomorphic langauage. There is no "awareness" in
> T.

>
>> this DOES NOT MEAN that a T cannot decide P where P isn't attempting
>> to defeat T by recursively referencing it.
>

> Of course not. Such a T is called a partial halting decider. Its
> existence has nothing to do with the non-existence of a _universal_
> halting decider.
>
> Ditto about "attempting" and "defeat". The plain fact is, for any T,
> there exists a P which it incorrectly decides.
>
>> This is why ....
>
> "what", perhaps?
>
>> .... Strachen refers to is as an "impossible program".
>
> He proves there is no such T, yes.

>
>> /Flibble
>

Conventionally it is understood that the instance of P proves that there
cannot be any T that always correctly decides the halting status of
every input.

// The C equivalent of [Strachey 1965] CPL

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

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

In the case of my H and P, because my H is a simulating halt decider
that only acts as a pure simulator until after its halt status decision

is made the pathological self-reference(olcott 2004) error Flibble
correctly objects to has no effect on either the behavior of P or the

halt status decision of H.

H aborts the simulation of its input before any nested H ever returns
any value to any P. This utterly nullifies the prior issue that seemed

to prove that P is an undecidable input.

When the simulation of P is aborted P stops running. This does not count
as a P that halts. P has had its execution suspended, not halted.

[olcott]

On 7/16/2021 11:39 AM, Alan Mackenzie wrote:
> [ Offensive cross-posts removed. ]

> "Conventionally" here means by everybody but cranks. I don't recall any
> other candidate false assumption being proffered on these interminable
> threads.

>
>> // The C equivalent of [Strachey 1965] CPL
>> void P(u32 x)
>> {
>> if (H(x, x))
>> HERE: goto HERE;
>> }
>
>> int main()
>> {
>> Output("Input_Halts = ", H((u32)P, (u32)P));
>> }
>
>> In the case of my H and P, because my H is a simulating halt decider
>> that only acts as a pure simulator until after its halt status decision
>> is made the pathological self-reference(olcott 2004) error Flibble
>> correctly objects to has no effect on either the behavior of P or the
>> halt status decision of H.
>

> The internal mechanism of H isn't of much interest. It doesn't matter.
> As long as it purports to return the halting status of any program/input
> pair, there will be such a pair it gets wrong.

>
>> H aborts the simulation of its input before any nested H ever returns
>> any value to any P. This utterly nullifies the prior issue that seemed
>> to prove that P is an undecidable input.
>

> I can't be bothered even to make sense of that. Whatever, any H is not a
> universal halting decider.

In other words I am holding my hands over my ears blah, blah, blah I
can't hear you but I know that you are wrong because I am a mindless
conformity robot that totally lacks any capacity to think for myself.


There can be no H that correctly returns the halts status of an input P
that does the opposite of whatever H(P,P) decides.

Nobody ever bothered to think this ALL THE WAY THROUGH to see that a
correct halt decider need not return any value to its input.

Everyone that knows software engineering knows that no function ever
returns any value to its caller when its caller calls it in infinite
recursion.

The call H(P,P) from P is essentially infinite recursion.
H sees this and aborts the call.

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

>
>> When the simulation of P is aborted P stops running. This does not count
>> as a P that halts. P has had its execution suspended, not halted.
>

> P(P) either halts or it doesn't. H gets the wrong anwer.
>

The is what a mindless conformity robot would say.

Groupthink is a phenomenon that occurs when a group of well-intentioned
people makes irrational or non-optimal decisions spurred by the urge to
conform or the belief that dissent is impossible.

https://www.psychologytoday.com/us/basics/groupthink

[Mr Flibble]

On Fri, 16 Jul 2021 12:13:26 -0500
olcott <No...@NoWhere.com> wrote:

>
> The is what a mindless conformity robot would say.
>
> Groupthink is a phenomenon that occurs when a group of
> well-intentioned people makes irrational or non-optimal decisions
> spurred by the urge to conform or the belief that dissent is
> impossible.

Sounds an awful lot like Christianity but you seem content being part
of that particular groupthink. In other words you are being a hypocrite
moaning about people being part of a groupthink.

/Flibble

[olcott]

I am absolutely an anti-conformist.
Until I independently verify a claim I treat it as possibly false.

Since it is impossible to conclusively proof that anything existed five
minutes ago we cannot know with certainty that Christ ever existed.

https://en.wikipedia.org/wiki/Omphalos_hypothesis#Five-minute_hypothesis

None-the-less his commandment to love one another is necessarily the
best way to be on the basis that it makes perfect sense.

Most all of those that falsely call themselves Christian miss this key
point. They put loving one another on a back burner and focus instead on
getting others to obey a set of rules.

Loving others with empathy is the key to all righteousness specifically
because it produces the best fruits.

[olcott]

On 7/16/2021 12:53 PM, André G. Isaak wrote:

> For starters, No function *ever* returns a value to its input. It return
> a value to its *caller*.
>

In the above example the outermost H simulates P with input P such that
the simulated P calls H(P,P). The outermost H aborts that infinitely
recursive sequence because H ever returns any value to the P that called
it.

> Second, a decider, *by definition* must always return a value for every
> possible input. Otherwise it is not a decider.
>

When the decider is called in an infinitely recursive chain it need not
return an infinite number of values. No function called in infinite
recursion ever returns any value to its caller.

>> Everyone that knows software engineering knows that no function ever
>> returns any value to its caller when its caller calls it in infinite
>> recursion.
>

> And the relevance of this is what exactly? A decider, by definition,
> must always return a value for every possible input.

The outermost H does return a value to its caller.
All of the inner H invocations are aborted when their caller it aborted.

> Therefore if you
> are writing a decider, it must be written in a way which precludes any
> input from ever getting stuck in infinite recursion. Otherwise you have
> failed to create a decider.
>
> André
>

I have done this: Infinite_loop() is the first concrete example and
Infinite_Recursion() is the second.

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

[olcott]

On 7/16/2021 2:57 PM, André G. Isaak wrote:
> On 2021-07-16 13:40, olcott wrote:
>> On 7/16/2021 1:52 PM, André G. Isaak wrote:

>>> So which invocation of a function do you claim is supposed to return
>>> a value to its *input*?

>>>
>>>>> Second, a decider, *by definition* must always return a value for
>>>>> every possible input. Otherwise it is not a decider.
>>>>>
>>>>
>>>> When the decider is called in an infinitely recursive chain it need
>>>> not return an infinite number of values. No function called in
>>>> infinite recursion ever returns any value to its caller.
>>>

>>> By definition, a decider *always* returns a value. That definition
>>> doesn't say it always returns a value except in situations where it
>>> can't. If such situations exist, it is not a decider. Look up the
>>> word 'always' in a dictionary. It doesn't mean the same thing as
>>> 'sometimes'.
>>>
>>
>> So in other words you fail to comprehend the basic software
>> engineering principle that no function called in infinite recursion
>> ever returns to its caller. I would say that this is very very dumb on
>> your part.
>
> You seem to be the one with the comprehension problem.
>
> I am fully aware that a function called in infinite recursion will never
> return.

>

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

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

If you truly understood this and understood that H <is> a pure x86
emulator of P until H matches a non-halting behavior pattern then you
would understand the H must not return a value to P in the above
computation.

_P()
[00000c36](01) 55 push ebp
[00000c37](02) 8bec mov ebp,esp
[00000c39](03) 8b4508 mov eax,[ebp+08]
[00000c3c](01) 50 push eax
[00000c3d](03) 8b4d08 mov ecx,[ebp+08]
[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 Call H(P,P)
[00000c68](03) 83c408 add esp,+08
[00000c6b](01) 50 push eax
[00000c6c](05) 6857030000 push 00000357
[00000c71](05) e810f7ffff call 00000386
[00000c76](03) 83c408 add esp,+08
[00000c79](02) 33c0 xor eax,eax
[00000c7b](01) 5d pop ebp
[00000c7c](01) c3 ret
Size in bytes:(0039) [00000c7c]

===============================
...[00000c56][0010172a][00000000](01) 55 push ebp
...[00000c57][0010172a][00000000](02) 8bec mov ebp,esp
...[00000c59][00101726][00000c36](05) 68360c0000 push 00000c36
...[00000c5e][00101722][00000c36](05) 68360c0000 push 00000c36
...[00000c63][0010171e][00000c68](05) e8fefcffff call 00000966
Begin Local Halt Decider Simulation at Machine Address:c36
...[00000c36][002117ca][002117ce](01) 55 push ebp
...[00000c37][002117ca][002117ce](02) 8bec mov ebp,esp
...[00000c39][002117ca][002117ce](03) 8b4508 mov eax,[ebp+08]
...[00000c3c][002117c6][00000c36](01) 50 push eax
...[00000c3d][002117c6][00000c36](03) 8b4d08 mov ecx,[ebp+08]
...[00000c40][002117c2][00000c36](01) 51 push ecx
...[00000c41][002117be][00000c46](05) e820fdffff call 00000966 //
Call H(P,P)
...[00000c36][0025c1f2][0025c1f6](01) 55 push ebp
...[00000c37][0025c1f2][0025c1f6](02) 8bec mov ebp,esp
...[00000c39][0025c1f2][0025c1f6](03) 8b4508 mov eax,[ebp+08]
...[00000c3c][0025c1ee][00000c36](01) 50 push eax
...[00000c3d][0025c1ee][00000c36](03) 8b4d08 mov ecx,[ebp+08]
...[00000c40][0025c1ea][00000c36](01) 51 push ecx
...[00000c41][0025c1e6][00000c46](05) e820fdffff call 00000966
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
...[00000c68][0010172a][00000000](03) 83c408 add esp,+08
...[00000c6b][00101726][00000000](01) 50 push eax
...[00000c6c][00101722][00000357](05) 6857030000 push 00000357
---[00000c71][00101722][00000357](05) e810f7ffff call 00000386 //
Call H(P,P)
Input_Halts = 0
...[00000c76][0010172a][00000000](03) 83c408 add esp,+08
...[00000c79][0010172a][00000000](02) 33c0 xor eax,eax
...[00000c7b][0010172e][00100000](01) 5d pop ebp
...[00000c7c][00101732][00000068](01) c3 ret
Number_of_User_Instructions(27)
Number of Instructions Executed(23721)




> I also understand what the word *requirement* means.
>
> It is a *requirement* of a decider that it return a result for every
> possible input.
>
> That means that a decider *must* be constructed in such a way that no
> input can possibly result in infinite recursion. If there are inputs
> which can result in infinite recursion under your approach, then your
> approach does not meet the requirements of being a decider.
>
> Nowhere does Linz require that H simulate its input; that was entirely
> your decision, and it is that decision which leads to the potential
> infinite recursion, from which we can conclude that your approach cannot
> be used in constructing a decider. A decider must *analyze* its input,
> not simulate it, in order to ensure that such recursion cannot occur.
>
> André

[olcott]

On 7/16/2021 3:30 PM, André G. Isaak wrote:

> And if you understood what the word *requirement* meant, you'd

If you require 2 > 5 then you are simply wrong.

If anyone requires a function to return a value to its caller when
called in infinite recursion then this requirement is simply wrong.

Perhaps you are too stupid to understand this.

> understand that if it is the case that H cannot return a value to P in
> the above computation that H fails to qualify as a decider.
>

In the actual code shown below it it not possible for H to correctly
return any value to P, thus proving that any requirement that H return a
value to P is simply wrong.

If God commanded that the decimal digit "2" be numerically greater than
the decimal digit "5" God would simply be wrong. Likewise with any
theory of computation requirement that H return a value to P in the
cases where P is calling H in infinite recursion.

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

> Your position seems to be:
>
> X is a requirement of Y.
>
> My approach to Y cannot always satisfy X.
>
> Therefore my approach should be exempt from requirement X.
>
> That's not how requirements work.
>
> The correct conclusion is 'Therefore, my approach to Y cannot work'.
>
> André
>
> <snip pointless trace>

[olcott]

On 7/16/2021 5:09 PM, André G. Isaak wrote:

> You're clearly the master of completely specious analogies. This one is
> even stupider than the various natural language analogies you've been
> tossing out recently.
>
> The requirement that a decider always return a value is nothing like the
> above 'requirement', which is simply a false statement. Functions are
> written all the time which are guaranteed to return a value to their
> caller. They accomplish this by being written in a way which precludes
> them from being stuck in infinite loops or infinite recursion. The
> existence of countless such functions clearly shows that this
> requirement is not unreasonable.

>
>> If anyone requires a function to return a value to its caller when
>> called in infinite recursion then this requirement is simply wrong.
>

> No one is requiring that a function return a value to its caller when
> called in infinite recursion. They are requiring that a program which
> purports to be a decider be written in such a way that it doesn't get
> into infinite recursion in the first place. Otherwise it can't meet the
> requirement that a decider always return a value.
>
> The fact that your implementation doesn't meet this requirement in no
> way entails that the requirement is 'wrong'. It just means that you have
> failed to construct a decider.

>
>> Perhaps you are too stupid to understand this.
>>
>>> understand that if it is the case that H cannot return a value to P
>>> in the above computation that H fails to qualify as a decider.
>>>
>>
>> In the actual code shown below it it not possible for H to correctly
>> return any value to P, thus proving that any requirement that H return
>> a value to P is simply wrong.
>

> No. It shows that your H fails to meet the requirement. It in no way
> shows that there is anything 'wrong' with the requirement.
>
> André
>

It is very obvious from the details of this code when we understand that
H is a pure x86 emulator of its input until H recognizes an infinite
execution pattern that no H can possibly correctly return any value to P
without violating the basic software engineering principle to no
function can every return to any called calling it is infinite recursion.

Because you have apparent turned into a liar you will simply delete my
proof fully operational code that I am correct and say that I am wrong.

For your sake and Ben's sake I hope this is not true:

Revelation 21:8 KJV
...all liars, shall have their part in the lake which burneth with fire
and brimstone: which is the second death.

The only reason that I am even pursing these things is so that I can
mathematically formalize the notion of truth to provide the ultimate
anchor for truth conditional semantics.

[olcott]

On 7/17/2021 4:39 AM, Alan Mackenzie wrote:
> olcott <No...@nowhere.com> wrote:

>> On 7/16/2021 4:30 PM, Alan Mackenzie wrote:
>>> olcott <No...@nowhere.com> wrote:

>>>> On 7/16/2021 3:19 PM, Alan Mackenzie wrote:
>>>>> olcott <No...@nowhere.com> wrote:

>>>>>> On 7/16/2021 1:25 PM, Alan Mackenzie wrote:
>
> [ .... ]
>
>>>> You say that all input that stops running proves that it halts my
>>>> halt decider causes Infinite_Loop() to stop running.
>
>>> That "sentence" doesn't parse.
>
>> Simulating halt decider is merely fulfilling the requirements of this
>> axiom:
>
>> Halt Deciding Axiom: When the pure simulation of the machine description
>> ⟨P⟩ of a machine P on its input I never halts we know that P(I) never
>> halts.
>
> That's a strange notion to call an axiom. All it seems to be saying is
> that simulation is possible.
>

It is the equivalence of UTM(⟨P⟩,I) and TM(P,I)
Learned by rote people fail to notice this.

>> Simulating halt decider H is only answering the question:
>> Would the input halt on its input if H never stopped simulating it?
>> (a) An answer of "no" universally means that the input never halts.
>> (b) An answer of "yes" universally means that the input halts.
>
> Seems over-complicated. The question should be "does the input program
> halt?".
>

The new axioms are not subject to the pathological self-reference error.

The halt decider acts as a pure simulator until after its halt status
decision has been made. This eliminates the possibility of any feedback
loop where the halt decider has any effect on the behavior of its input.

For all computations that halt without intervention, the simulating halt
decider remains in pure simulator mode.

For all computations that do not halt without intervention, the
simulating halt decide immediately aborts the simulation of its input as
soon as a non-halting behavior pattern is recognized.

The above system makes it impossible for the input to prevent a correct
halt status decision.

Here is a complete example:

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]

[00000c3c](01) 50 push eax
[00000c3d](03) 8b4d08 mov ecx,[ebp+08]

[00000c40](01) 51 push ecx
[00000c41](05) e820fdffff call 00000966

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

===============================
...[00000c56][0010172a][00000000] 55 push ebp
...[00000c57][0010172a][00000000] 8bec mov ebp,esp
...[00000c59][00101726][00000c36] 68360c0000 push 00000c36 // push P
...[00000c5e][00101722][00000c36] 68360c0000 push 00000c36 // push P
...[00000c63][0010171e][00000c68] e8fefcffff call 00000966 // call H

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

Local Halt Decider: Infinite Recursion Detected Simulation Stopped

Because the halt decider acts as a pure simulator until after its halt
status decision is made it can ignore its own address range in any
execution trace basis of its halt status decision.

This means that the above repeating sequence of the first 7 instructions
pf P() prove that P() will never halt. None of these 7 instructions can
possibly break out of this infinite repetition.

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

> [ .... ]
>
>>>>> That concept "proof", in the mathematical sense, is one you don't
>>>>> understand. It's the fact that things can be shown to be absolutely
>>>>> correct or absolutely incorrect, without a shadow of doubt, for all time.
>>>>> If you could understand that, you'd be less pig-headed and possibly
>>>>> amenable to the truth.
>
>>>> An actual working program that shows all of the steps of correctly
>>>> deciding the impossible inputs supersedes and over-rules and proof to
>>>> the contrary that relies on false assumptions about the details of
>>>> unspecified steps.
>
>>> No it doesn't. It's merely erroneous. Like I said, you do not
>>> understand the concept of proof - you literally don't get it.
>
>> When you start with premises that can be verified as definitely true and
>> only apply truth preserving operations to these true premises then the
>> consequence/conclusion is necessarily true.
>
> That's one form of proof, yes. But you don't get it - you don't
> understand in the soul of your being that something mathematically proven
> is absolute truth. You seem to think something proven is merely some
> sort of provisional result. You are wrong.
>

The HP proof only show that no correct halt status can be returned to an
input that is designed to do the opposite of whatever the halt decider
decides.

Categorically exhaustive reasoning (my system of reasoning) finds a key
gap in this proof. I provided all the details above.

When H aborts its simulation of P before ever returning any value to P
it escapes the pathological self-reference(Olcott 2004) error.

Because this second level H is merely a part of the slave process that
is under the total control of the master H, the master H can cut off
simulation of the slave process at any point.

A slave decider need not return any value because it can have its
execution cut off at any point by its master.

As shown above the second time that a slave P calls H(P,P) its whole
slave process is terminated. Because the H in this slave process is a
part of a slave process its master can cut it off at any time.

>> Other forms of "proof" that diverge for this model are bogus.
>
> You could hardly be more wrong, here. For example, there is proof by
> contradiction. Here we assume, provisionally, something we wish to show
> is false, and by "truth preserving arguments" show that this leads to a
> contradiction. Thus this assumption is proven wrong, and we have shown
> the something to be false.
>

That is not a divergence.

>>> You don't understand the proofs of the halting problem that you have
>>> quoted here over the months and years. You do not understand that
>>> some things are unassailably and eternally true. Pythagoras's Theorem
>>> is one example - a plane triangle with sides 3, 4, and 5 will have an
>>> exact right angle. The impossibility of a universal halting decider
>>> is another example.
>
>>>> Every HP proof is never more than a sketch of a proof because it
>>>> always leaves out almost all of the details of the definition of the
>>>> computations.
>
>>> You don't get it: it leaves out unimportant details which are
>>> irrelevant to the proof. The internal structure of the computations
>>> is wholly unimportant. It doesn't matter. Whether by analysis, or
>>> simulation, or magic is wholly unimportant - just that a yes/no
>>> answer is always returned, and the same answer is always return for
>>> the same input.
>
> [ .... ]

[olcott]

On 7/16/2021 5:48 PM, André G. Isaak wrote:

> And if this is indeed very obvious then it simply confirms what I write
> above. H fails to meet the requirements of a decider, which include the
> requirement that a decider *always* return a value.
>
> It doesn't matter *why* H can't return a value. If it can't return a
> value in all instances, then it isn't a decider.

>


The HP proof only show that no correct halt status can be returned to an
input that is designed to do the opposite of whatever the halt decider
decides.

Categorically exhaustive reasoning (my system of reasoning) finds a key
gap in this proof.

When H aborts its simulation of P before ever returning any value to P
it escapes the pathological self-reference(Olcott 2004) error.

Because this second level H is merely a part of the slave process that
is under the total control of the master H, the master H can cut off
simulation of the slave process at any point.

A slave decider need not return any value because it can have its
execution cut off at any point by its master.

The second time that a slave P calls H(P,P) its whole slave process is

terminated. Because the H in this slave process is a part of a slave
process its master can cut it off at any time.

A TM decider must return a value to some caller.

This is not true for a decider that is the slave process of a simulating
halt decider. Its whole process may be killed before it transitions to
its second internal state.

> The requirement is what it is. If something fails to meet it, it isn't a
> decider. If it isn't possible to meet the requirement for a particular
> implementation, that doesn't exempt it from the requirement. It means
> that that particular implementation fails to meet the requirement.
>
> I don't see how this point could possibly be made any simpler.

>
>> Because you have apparent turned into a liar you will simply delete my
>> proof fully operational code that I am correct and say that I am wrong.
>

> You seem determined to prove something I've already agreed to. I fail to
> see the point of doing so.

[olcott]

> P(P) (like all computations) either halts or it does not. You tell us
> it halts. You also tell up that H(P,P) == 0. H(P,P) == 0 is the wrong
> answer for a halting computation.
>

int main() { P(P); } specifies infinite recursion that it aborted at its
third function call.

>> I continue to hope against hope that you simply misunderstand this and
>> will eventually agree that I am correct.
>

> I merely don't like your analogy.

Bullshit. You know that Daryl McCullough's analogy proves that I am
right and you only want to prove me wrong even if you have to lie to
make gullible fools believe that your rebuttal is valid.

https://groups.google.com/g/sci.logic/c/4kIXI1kxmsI/m/hRroMoQZx2IJ

> Are there any facts in dispute? I
> think not. If you find that the liar paradox helps to explain why your
> H gets the wrong answer, then have at it.

>
>> The problem with that is that you simply ignore perfect clarity
>> because perfect clarity is inconsistent with your goal of rebuttal:
>

> The facts of the matter are not in dispute. For F to be a halt decider,
> F(P, I) should be true iff P(I) halts and false otherwise. Your H has
> H(P,P) == false when P(I) halts.
>
> Why you are wrong can be summed up in less then three lines stating just
> a few of facts that you don't dispute.
>

We must overcome rather than simply ignore the pathological
self-reference(Olcott 2004) error:

Halt Deciding Axiom: When the pure simulation of the machine description
⟨P⟩ of a machine P on its input I never halts we know that P(I) never
halts.

Simulating halt decider H is only answering the question:
Would the input halt on its input if H never stopped simulating it?
(a) An answer of "no" universally means that the input never halts.
(b) An answer of "yes" universally means that the input halts.

The simulating halt decider must remain a pure simulator until after its
halt status decision is made. This eliminates all pathological
communication between the decider and its input.

[olcott]

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

>
> In comp.theory olcott <No...@nowhere.com> wrote:

> There is no such thing.
>

Conventional Halt Deciding Axiom:

When the pure simulation of the machine description ⟨P⟩ of a machine P

on its input I never halts we know that P(I) never halts. // based on
UTM(⟨P⟩,I) ≡ P(I)

Stipulated Definition of Halting
An input to a halt decider is defined to halt if and only if this input
stops running while simulating halt decider H remains a pure simulator
of this input.

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 seems to me that the Stipulated Definition of Halting does not add
anything but clarity to the Conventional Halt Deciding Axiom. Others may
see this differently.

None-the-less the Stipulated Definition of Halting does provide the
means to correctly decide the halting status of Pathological Inputs.

int main() { P(P); } is defined to be a non-halting computation under
the stipulated definition.

The stipulated definition of halting defines the exact same set as the
conventional definition of halting with the possible exception that
pathological inputs are decided as non-halting inputs.

Because the stipulated definition of halting is merely a paraphrase of
the Conventional Halt Deciding Axiom I propose that this stipulated
definition of halting merely provides clarity and does not change the
conventional definition of halting at all.

>> The halt decider acts as a pure simulator until after its halt status
>> decision has been made. This eliminates the possibility of any feedback
>> loop where the halt decider has any effect on the behavior of its input.
>

> If you understood the proofs of the halting problem, you would know that
> the internal details of the purported halting decider are irrelevant and
> unimportant. They're also uninteresting, so ....
>
> [ Snip more uninteresting irrelevant stuff. ]

>
>
>>> [ .... ]
>
>>>>>>> That concept "proof", in the mathematical sense, is one you don't
>>>>>>> understand. It's the fact that things can be shown to be
>>>>>>> absolutely correct or absolutely incorrect, without a shadow of
>>>>>>> doubt, for all time. If you could understand that, you'd be less
>>>>>>> pig-headed and possibly amenable to the truth.
>
>>>>>> An actual working program that shows all of the steps of correctly
>>>>>> deciding the impossible inputs supersedes and over-rules and proof
>>>>>> to the contrary that relies on false assumptions about the details
>>>>>> of unspecified steps.
>
>>>>> No it doesn't. It's merely erroneous. Like I said, you do not
>>>>> understand the concept of proof - you literally don't get it.
>
>>>> When you start with premises that can be verified as definitely true
>>>> and only apply truth preserving operations to these true premises
>>>> then the consequence/conclusion is necessarily true.
>
>>> That's one form of proof, yes. But you don't get it - you don't
>>> understand in the soul of your being that something mathematically
>>> proven is absolute truth. You seem to think something proven is
>>> merely some sort of provisional result. You are wrong.
>
>
>> The HP proof only show that no correct halt status can be returned to
>> an input that is designed to do the opposite of whatever the halt
>> decider decides.
>

> No. It shows further that there is no universal halt decider possible.

>
>> Categorically exhaustive reasoning (my system of reasoning) finds a key
>> gap in this proof. I provided all the details above.
>

> How can you find a gap in a proof when you don't even understand what
> "proof" means? You didn't provide any such details. Just prolix
> irrelevancies. The Linz version of the proof is short and easy to
> understand, possibly even for you. Which step in that proof is not
> rigorously correct?
>
> [ more irrelevant internal details of the purported decider snipped. ]

>
>>>> Other forms of "proof" that diverge for this model are bogus.
>
>>> You could hardly be more wrong, here. For example, there is proof by
>>> contradiction. Here we assume, provisionally, something we wish to show
>>> is false, and by "truth preserving arguments" show that this leads to a
>>> contradiction. Thus this assumption is proven wrong, and we have shown
>>> the something to be false.
>
>
>> That is not a divergence.
>

> Then your utterance about "Other forms of "proof" ..." is meaningless.

>
>>>>> You don't understand the proofs of the halting problem that you have
>>>>> quoted here over the months and years. You do not understand that
>>>>> some things are unassailably and eternally true. Pythagoras's Theorem
>>>>> is one example - a plane triangle with sides 3, 4, and 5 will have an
>>>>> exact right angle. The impossibility of a universal halting decider
>>>>> is another example.
>
>>>>>> Every HP proof is never more than a sketch of a proof because it
>>>>>> always leaves out almost all of the details of the definition of the
>>>>>> computations.
>
>>>>> You don't get it: it leaves out unimportant details which are
>>>>> irrelevant to the proof. The internal structure of the computations
>>>>> is wholly unimportant. It doesn't matter. Whether by analysis, or
>>>>> simulation, or magic is wholly unimportant - just that a yes/no
>>>>> answer is always returned, and the same answer is always return for
>>>>> the same input.
>

[olcott]

On 7/17/2021 8:36 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 7/16/2021 7:29 PM, Ben Bacarisse wrote:
>>> olcott <No...@NoWhere.com> writes:
>
>>>> If the C equivalent of the Strachey (1965) CPL returns true(halts) to
>>>> P then P loops. If it returns false(does not halt) to P then P halts.
>>>>
>>>> void P(u32 x)
>>>> {
>>>> if (H(x, x))
>>>> HERE: goto HERE;
>>>> }
>>>>
>>>> int main()
>>>> {
>>>> Output("Input_Halts = ", H((u32)P, (u32)P));
>>>> }
>>>>
>>>> The self-contradiction of the halting problem counter-examples is
>>>> apparently modeled after the liar paradox.
>>>
>>> P(P) (like all computations) either halts or it does not. You tell us
>>> it halts. You also tell up that H(P,P) == 0. H(P,P) == 0 is the wrong
>>> answer for a halting computation.
>>
>> int main() { P(P); } specifies infinite recursion that it aborted at
>> its third function call.
>

> P(P) halts (according to you). H(P,P) == 0 (according to you). That is
> wrong (according to everyone but you).

>

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

int main()
{

P((u32)P);
}

The fact is that the above computation never ever halts unless some H
aborts some P thus proving beyond all possible doubt that H[0] does
correctly decide that P[2] (zero based addressing) never halts.

When a computation only stops running because its simulation was aborted
this counts as a computation that never halts.

That you simply don't know the x86 language well enough to see that the
input to H has no possible escape from its infinite recursion does not
count as any sort of rebuttal at all.

>>>> I continue to hope against hope that you simply misunderstand this and
>>>> will eventually agree that I am correct.
>>> I merely don't like your analogy.
>>
>> Bullshit. You know that Daryl McCullough's analogy proves that I am
>> right and you only want to prove me wrong even if you have to lie to
>> make gullible fools believe that your rebuttal is valid.
>

> Don't be silly. You are wrong based on simple facts that you don't
> dispute. None of the facts are in dispute:
>
> For H to be a halt decider, H(P,I) must be true if and only of P(I)
> halts. P(P) halts. H(P,P) is false.
>
> Three facts. It's that simple.

[olcott]

On 7/19/2021 9:35 AM, Charlie-Boo wrote:

> On Thursday, July 15, 2021 at 1:22:19 PM UTC-4, Mr Flibble wrote:
>> Hi!
>>
>> From Wikipedia Halting Problem page:
>>
>> For any program f that might determine if programs halt, a
>> "pathological" program g, called with some input, can pass its
>> own source and its input to f and then specifically do the
>> opposite of what f predicts g will do. No f can exist that
>> handles this case.
>>

>> To me this looks like everyone is assuming that the halting problem is
>> undecidable based on a misunderstanding of the contradiction
>> crystallized by [Strachen 1965].
>>

>> Strachen isn't saying the halting problem is undecidable, he is saying that

>> there is a contradiction that means that a decider can not be a part of

>> or called by that which is being decided. This doesn't mean that the
>> halting problem is not undecidable but it does mean that if that
>> Wikipedia extract is the current state of the art then nobody has proven
>> that the HP is undecidable, at least for non-"pathological" programs.
>>
>> Olcott is on to something. :)
>>
>> /Flibble

> "a decider can not be a part of or called by that which is being decided"

> That is impossible to enforce (if definable) and not really formally definable.
> It also contradicts the definition of the Halting Problem - it has to accept any input.
> How could you even be any more explicit than "part of"? Every function can be coded in an infinite number of ways.
> That is ill-defined.
> C-B

>

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

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

In my C version H can verify that its input is calling it on the basis
that P is calling its own machine address.

H correctly decides its input never halts.

The Peter Linz version has the same infinitely repeating pattern:

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt

Ĥ0.q0 copies its input ⟨Ĥ1⟩ to ⟨Ĥx⟩ then Ĥ0.qx simulates this input with
the copy then
Ĥ1.q0 copies its input ⟨Ĥ2⟩ to ⟨Ĥy⟩ then Ĥ1.qx simulates this input with
the copy then
Ĥ2.q0 copies its input ⟨Ĥ3⟩ to ⟨Ĥz⟩ then Ĥ2.qx simulates this input with
the copy then ...

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

[olcott]

On 7/19/2021 9:43 AM, Charlie-Boo wrote:
> On Thursday, July 15, 2021 at 1:22:19 PM UTC-4, Mr Flibble wrote:
>> Hi!
>>
>> From Wikipedia Halting Problem page:
>>
>> For any program f that might determine if programs halt, a
>> "pathological" program g, called with some input, can pass its
>> own source and its input to f and then specifically do the
>> opposite of what f predicts g will do. No f can exist that
>> handles this case.
>>
>> To me this looks like everyone is assuming that the halting problem is
>> undecidable based on a misunderstanding of the contradiction
>> crystallized by [Strachen 1965].
>>
>> Strachen isn't saying the halting problem is undecidable, he is saying that
>> there is a contradiction that means that a decider can not be a part of
>> or called by that which is being decided. This doesn't mean that the
>> halting problem is not undecidable but it does mean that if that
>> Wikipedia extract is the current state of the art then nobody has proven
>> that the HP is undecidable, at least for non-"pathological" programs.
>>
>> Olcott is on to something. :)
>>
>> /Flibble
>

> The Halting Problem is like kindergarten in Computer Science.
> It is a trivial result superseded by much more general results.
> Why not learn the Arithmetic Hierarchy (not that difficult) then you can understand WHY the Halting Problem is unsolvable?
> People talking about flaws in Turing 1937 are like children fighting on the playground.
> Learn ANY incompleteness result - even just Cantor - and you will have the principle that permeates and drives all of these results.
> There are "more sets than elements".
>
> C-B
>

The conventional HP proof merely shows that no H can possibly return a
correct halt status to P:

// 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));
}

What these conventional HP proofs utterly ignore is the case of a
simulating halt decider that aborts P before ever returning any value to P.

[olcott]

On 7/19/2021 7:38 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> void P(u32 x)
>> {
>> if (H(x, x))
>> HERE: goto HERE;
>> }
>>
>> int main()
>> {
>> P((u32)P);
>> }
>>

>> The fact is that the above computation never ever halts unless...
>
> The fact is that P(P) halts (according to you). H(P,P) == 0 (according
> to you). That is wrong. You know it's wrong:
>
> Me: Every computation that halts, for whatever reason, is a halting
> computation.
>
> You: OK
>
> Are there any facts of the matter that are in dispute?
>

A computation that has its simulation aborted before it comes to its
natural end is not a halting computation.

A halting computation is a computation that stop running without ever
having its simulation aborted.

*Conventional Halt Deciding Axiom*

When the pure simulation of the machine description ⟨P⟩ of a machine P

on its input I never halts we know that P(I) never halts. // based on
UTM(⟨P⟩,I) ≡ P(I)