On Strachey

111 views
Skip to first unread message

Mr Flibble

unread,
May 5, 2022, 3:45:56 PMMay 5
to
Strachey's "Impossible Program" [Strachey, 1965] is indeed impossible
but not for the reason Strachey suggests. Strachey's impossible program
is impossible not due to the contradiction he posits but is instead
impossible due to an invalid infinite recursion (a category error
in this case) which prevents the contradiction from ever being realised.
As Strachey claims his "Impossible Program" proof is based on
communication he had with Turing it seems reasonable to assume that
Turing's proof has the same flaw.

I suppose at some point I should stop trolling and actually read what
Turing wrote so I don't have to rely on what seems reasonable. :D

/Flibble

olcott

unread,
May 5, 2022, 5:30:46 PMMay 5
to
What Turing wrote never mentions halting:
https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

This proof is the clearest one that provide all of its details as
explicit state transitions:
https://www.liarparadox.org/Peter_Linz_HP_317-320.pdf

All of the experts will agree that it is accurately specifies the
halting theorem.

--
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer

Mr Flibble

unread,
May 5, 2022, 5:39:11 PMMay 5
to
On Thu, 5 May 2022 16:30:41 -0500
olcott <polc...@gmail.com> wrote:

> On 5/5/2022 2:45 PM, Mr Flibble wrote:
> > Strachey's "Impossible Program" [Strachey, 1965] is indeed
> > impossible but not for the reason Strachey suggests. Strachey's
> > impossible program is impossible not due to the contradiction he
> > posits but is instead impossible due to an invalid infinite
> > recursion (a category error in this case) which prevents the
> > contradiction from ever being realised. As Strachey claims his
> > "Impossible Program" proof is based on communication he had with
> > Turing it seems reasonable to assume that Turing's proof has the
> > same flaw.
> >
> > I suppose at some point I should stop trolling and actually read
> > what Turing wrote so I don't have to rely on what seems reasonable.
> > :D
> >
> > /Flibble
> >
>
> What Turing wrote never mentions halting:
> https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

"Alan Turing proved in 1936 that a general algorithm to solve the
halting problem for all possible program-input pairs cannot exist"
[Wikipedia, 2022]

/Flibble

olcott

unread,
May 5, 2022, 5:48:24 PMMay 5
to

Mr Flibble

unread,
May 5, 2022, 5:53:37 PMMay 5
to
On Thu, 5 May 2022 16:48:21 -0500
The fact it wasn't called The Halting Problem when Turing wrote his
paper doesn't really change any facts on the ground?

/Flibble

olcott

unread,
May 5, 2022, 6:18:48 PMMay 5
to
Right, so it proves that you are right and Ben is wrong.
What Turing wrote in 1936 is now known as the halting theorem.

Ben

unread,
May 5, 2022, 9:34:37 PMMay 5
to
>>> Yes what you said is equally true:
>>> https://www.sciencedirect.com/science/article/pii/S235222082100050X
>>
>> The fact it wasn't called The Halting Problem when Turing wrote his
>> paper doesn't really change any facts on the ground?
>
> Right, so it proves that you are right and Ben is wrong.
> What Turing wrote in 1936 is now known as the halting theorem.

Two people who have not read the paper have persuaded themselves that
someone who has must be wrong about it. Is there any need for facts?

Turing's 1936 paper is not about halting. It proves a related theorem
about the outputs -- the symbols a TM writes to the tape. Did Turing
know, in 1936, that halting could not be decided? Almost certainly.
But he didn't prove it because his concern was about the strings
written, even those that are not finite.

(It also uses a term, "cycle-free" that is likely to mislead the casual
reader.)

--
Ben.
"le génie humain a des limites, quand la bêtise humaine n’en a pas"
Alexandre Dumas (fils)

olcott

unread,
May 5, 2022, 9:40:16 PMMay 5
to
Turing's paper is construed to be the foundation of the halting theorem
even though the term halting was not applied to it until 1958.
https://www.sciencedirect.com/science/article/pii/S235222082100050X

Mr Flibble

unread,
May 5, 2022, 9:59:45 PMMay 5
to
On Fri, 06 May 2022 02:34:35 +0100
Ben <ben.u...@bsb.me.uk> wrote:

> Two people who have not read the paper have persuaded themselves that
> someone who has must be wrong about it. Is there any need for facts?
>
> Turing's 1936 paper is not about halting.

[Wikipedia, 2022] disagrees with you:

"Alan Turing proved in 1936 that a general algorithm to solve the
halting problem for all possible program-input pairs cannot exist."

https://en.wikipedia.org/wiki/Halting_problem

/Flibble

Ben

unread,
May 5, 2022, 10:50:48 PMMay 5
to
And? People like you write wikipedia articles.

This seems like a very odd debate since you could simply see for your
self. Academics (like Turing) publish papers so we can all see what
they are saying.

--
Ben.

Ben

unread,
May 5, 2022, 10:53:03 PMMay 5
to
It is not only construed to be, it /is/ the foundation of the halting
theorem.

Jeff Barnett

unread,
May 6, 2022, 1:01:37 AMMay 6
to
I pulled Davis /The undecidable/ off the shelf recently - it includes
The Turing paper. I think that you have been referring to Chapter or
Section 8 and that is as close to mucking about with halting as he got.
Your reading is, of course, correct. The fact that the idiot and his
sock puppet were the other side of the dialogue, kept me from butting in
for a few reasons: 1) the term "cycle-free" being used as you noted
above and 2) the use of a "diagonal argument" for what he did prove.
Both terms, I thought, would drive the two/one to utter madness and
confusion since we've seen that diagonal arguments are beyond their
comprehension and cycle-free would conjure visions of infinite recursion
and the "Demons of the Christmas story about Scrooge". When ignorant of
or confronted with words not understood they go into a most interesting
tail (or is that tale) spin. So I passed. Since you broached the topic,
I thought what the hell .....
--
Jeff Barnett

Mikko

unread,
May 6, 2022, 9:09:16 AMMay 6
to
On 2022-05-05 19:45:51 +0000, Mr Flibble said:

> Strachey's "Impossible Program" [Strachey, 1965] is indeed impossible
> but not for the reason Strachey suggests. Strachey's impossible program
> is impossible not due to the contradiction he posits but is instead
> impossible due to an invalid infinite recursion (a category error
> in this case) which prevents the contradiction from ever being realised.
> As Strachey claims his "Impossible Program" proof is based on
> communication he had with Turing it seems reasonable to assume that
> Turing's proof has the same flaw.

A category error does not lead to an infinite recursion. A category error
is detected by the compiler, which then doesn't compile it, so no recursion
is executed.

An infinite recursion typically results in a stack overflow abort but
sometimes can be a valid structure in a program. Some programs are
required to never stop and an infinite tail recursion may be one way to
achieve that.

> I suppose at some point I should stop trolling and actually read what
> Turing wrote so I don't have to rely on what seems reasonable. :D

You needn't stop trolling in order to read what Turing wrote. But you
might be a more successfull troll if you switch to a less competed topic.

Mikko



Mr Flibble

unread,
May 6, 2022, 9:56:49 AMMay 6
to
On Fri, 06 May 2022 03:50:46 +0100
Ben <ben.u...@bsb.me.uk> wrote:

> Mr Flibble <fli...@reddwarf.jmc> writes:
>
> > On Fri, 06 May 2022 02:34:35 +0100
> > Ben <ben.u...@bsb.me.uk> wrote:
> >
> >> Two people who have not read the paper have persuaded themselves
> >> that someone who has must be wrong about it. Is there any need
> >> for facts?
> >>
> >> Turing's 1936 paper is not about halting.
> >
> > [Wikipedia, 2022] disagrees with you:
> >
> > "Alan Turing proved in 1936 that a general algorithm to solve the
> > halting problem for all possible program-input pairs cannot exist."
> >
> > https://en.wikipedia.org/wiki/Halting_problem
>
> And? People like you write wikipedia articles.

Most Wikipedia articles crowd source peer review by multiple experts in
their field: who should I trust? Those experts or random guy on
Usenet? I think the answer is obvious.

If you think the Wikipedia is incorrect then either correct it and have
your corrections peer reviewed or shut the fuck up.

/Flibble

Mr Flibble

unread,
May 6, 2022, 9:59:47 AMMay 6
to
On Fri, 6 May 2022 16:09:13 +0300
Mikko <mikko....@iki.fi> wrote:

> On 2022-05-05 19:45:51 +0000, Mr Flibble said:
>
> > Strachey's "Impossible Program" [Strachey, 1965] is indeed
> > impossible but not for the reason Strachey suggests. Strachey's
> > impossible program is impossible not due to the contradiction he
> > posits but is instead impossible due to an invalid infinite
> > recursion (a category error in this case) which prevents the
> > contradiction from ever being realised. As Strachey claims his
> > "Impossible Program" proof is based on communication he had with
> > Turing it seems reasonable to assume that Turing's proof has the
> > same flaw.
>
> A category error does not lead to an infinite recursion. A category
> error is detected by the compiler, which then doesn't compile it, so
> no recursion is executed.

The category error (as an invalid infinite recursion) is in the
definition of the proof itself: it is NOT some function call-like
infinite recursion that gets executed at runtime.

> An infinite recursion typically results in a stack overflow abort but
> sometimes can be a valid structure in a program. Some programs are
> required to never stop and an infinite tail recursion may be one way
> to achieve that.

As I said the category error is not runtime function call-like infinite
recursion.

/Flibble

Mr Flibble

unread,
May 6, 2022, 10:42:16 AMMay 6
to
Gas.

/Flibble

Mikko

unread,
May 6, 2022, 12:16:18 PMMay 6
to
On 2022-05-06 13:59:44 +0000, Mr Flibble said:

> On Fri, 6 May 2022 16:09:13 +0300
> Mikko <mikko....@iki.fi> wrote:
>
>> On 2022-05-05 19:45:51 +0000, Mr Flibble said:
>>
>>> Strachey's "Impossible Program" [Strachey, 1965] is indeed
>>> impossible but not for the reason Strachey suggests. Strachey's
>>> impossible program is impossible not due to the contradiction he
>>> posits but is instead impossible due to an invalid infinite
>>> recursion (a category error in this case) which prevents the
>>> contradiction from ever being realised.

Although the sentence containing the alleged "category error" is not
identifed, this seems to say that it is in the "Impossible program".

> The category error (as an invalid infinite recursion) is in the
> definition of the proof itself: it is NOT some function call-like
> infinite recursion that gets executed at runtime.

However, this says that it is elsewhere but still does not identify
the sentence. Claims of the type "there is a thing that is distinct
from everything one could mention" are not credible without a very
good proof.

Mikko



olcott

unread,
May 6, 2022, 12:49:04 PMMay 6
to
This paper makes all these things concrete in the x86utm operating system.

Halting problem undecidability and infinitely nested simulation
May 2021

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

olcott

unread,
May 6, 2022, 12:58:41 PMMay 6
to
Ben really hates to get down to the essence of things he loves to
quibble over tiny little inessential details. It is currently understood
that Turing's 1936 paper does establish what is now known as the halting
theorem.

olcott

unread,
May 6, 2022, 1:10:59 PMMay 6
to
It is certainly a Category error in Gödel's G, Tarski's p and the Liar
Paradox. {G, p, LP} are incorrectly placed in the category of a logic
sentence / truth bearer.

Incomplete(F) ↔ ∃G ((F ⊬ G) ∧ (F ⊬ ¬G)).

If a math formula has infinitely recursive definition it is simply
incorrect. If a TM / input pair specifies infinitely nested simulation
halt decider H can spot this and reject it.

olcott

unread,
May 6, 2022, 1:34:52 PMMay 6
to
On 5/6/2022 8:09 AM, Mikko wrote:
> On 2022-05-05 19:45:51 +0000, Mr Flibble said:
>
>> Strachey's "Impossible Program" [Strachey, 1965] is indeed impossible
>> but not for the reason Strachey suggests. Strachey's impossible program
>> is impossible not due to the contradiction he posits but is instead
>> impossible due to an invalid infinite recursion (a category error
>> in this case) which prevents the contradiction from ever being realised.
>> As Strachey claims his "Impossible Program" proof is based on
>> communication he had with Turing it seems reasonable to assume that
>> Turing's proof has the same flaw.
>
> A category error does not lead to an infinite recursion. A category error
> is detected by the compiler, which then doesn't compile it, so no recursion
> is executed.
>
> An infinite recursion typically results in a stack overflow abort but
> sometimes can be a valid structure in a program. Some programs are
> required to never stop and an infinite tail recursion may be one way to
> achieve that.
>

This paper shows all of the details of the actual issue using C/x86 code
for H and P that is directly executed in the x86utm operating system.

Halting problem undecidability and infinitely nested simulation

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


#include <stdint.h>
typedef void (*ptr)();

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

int main()
{
int halts = H(P,P);
}

>> I suppose at some point I should stop trolling and actually read what
>> Turing wrote so I don't have to rely on what seems reasonable. :D
>
> You needn't stop trolling in order to read what Turing wrote. But you
> might be a more successfull troll if you switch to a less competed topic.
>
> Mikko
>
>
>


Ben

unread,
May 6, 2022, 7:58:53 PMMay 6
to
Mr Flibble <fli...@reddwarf.jmc> writes:

> On Fri, 06 May 2022 03:50:46 +0100
> Ben <ben.u...@bsb.me.uk> wrote:
>
>> Mr Flibble <fli...@reddwarf.jmc> writes:
>>
>> > On Fri, 06 May 2022 02:34:35 +0100
>> > Ben <ben.u...@bsb.me.uk> wrote:
>> >
>> >> Two people who have not read the paper have persuaded themselves
>> >> that someone who has must be wrong about it. Is there any need
>> >> for facts?
>> >>
>> >> Turing's 1936 paper is not about halting.
>> >
>> > [Wikipedia, 2022] disagrees with you:
>> >
>> > "Alan Turing proved in 1936 that a general algorithm to solve the
>> > halting problem for all possible program-input pairs cannot exist."
>> >
>> > https://en.wikipedia.org/wiki/Halting_problem
>>
>> And? People like you write wikipedia articles.
>
> Most Wikipedia articles crowd source peer review by multiple experts in
> their field: who should I trust? Those experts or random guy on
> Usenet? I think the answer is obvious.

I never said you should trust me. I said you could just read the paper
and find out for yourself.

> If you think the Wikipedia is incorrect then either correct it and have
> your corrections peer reviewed or shut the fuck up.

Or I can just suggest you find out for yourself and leave it at that
because, as I have already said, the article also quotes Copleland:

"It is often said that Turing stated and proved the halting theorem in
'On Computable Numbers', but strictly this is not true"

so I don't feel an edit is needed.

--
Ben.

Ben

unread,
May 6, 2022, 8:11:21 PMMay 6
to
olcott <polc...@gmail.com> writes:

> On 5/6/2022 8:56 AM, Mr Flibble wrote:
>> On Fri, 06 May 2022 03:50:46 +0100
>> Ben <ben.u...@bsb.me.uk> wrote:
>>
>>> Mr Flibble <fli...@reddwarf.jmc> writes:
>>>
>>>> On Fri, 06 May 2022 02:34:35 +0100
>>>> Ben <ben.u...@bsb.me.uk> wrote:
>>>>
>>>>> Two people who have not read the paper have persuaded themselves
>>>>> that someone who has must be wrong about it. Is there any need
>>>>> for facts?
>>>>>
>>>>> Turing's 1936 paper is not about halting.
>>>>
>>>> [Wikipedia, 2022] disagrees with you:
>>>>
>>>> "Alan Turing proved in 1936 that a general algorithm to solve the
>>>> halting problem for all possible program-input pairs cannot exist."
>>>>
>>>> https://en.wikipedia.org/wiki/Halting_problem
>>>
>>> And? People like you write wikipedia articles.
>> Most Wikipedia articles crowd source peer review by multiple experts in
>> their field: who should I trust? Those experts or random guy on
>> Usenet? I think the answer is obvious.
>> If you think the Wikipedia is incorrect then either correct it and have
>> your corrections peer reviewed or shut the fuck up.
>> /Flibble
>>
>
> Ben really hates to get down to the essence of things he loves to
> quibble over tiny little inessential details.

So why did I go even further than you did to say of the result in that
paper:

"It is not only construed to be, it /is/ the foundation of the halting
theorem."?

> It is currently understood that Turing's 1936 paper does establish
> what is now known as the halting theorem.

Yes, provided you are not using established to mean proved as some
people do. Turing proved a very closely related result from with the
halting theorem would follow as a corollary.

The halting theorem follows, trivially, from lots of simpler theorems,
none of which have you bothered to read. In Linz, the theorem is
presented as a corollary of a simpler theorem in chapter 11.

olcott

unread,
May 6, 2022, 8:32:00 PMMay 6
to
11.3, 11.4, and 11.5. I will look at them.

Ben

unread,
May 6, 2022, 9:07:40 PMMay 6
to
Goodness! A good move. Why the change of heart?

olcott

unread,
May 6, 2022, 9:34:58 PMMay 6
to
On 5/6/2022 8:07 PM, Ben wrote:
> olcott <polc...@gmail.com> writes:
>
>> On 5/6/2022 7:11 PM, Ben wrote:
>
>>> The halting theorem follows, trivially, from lots of simpler theorems,
>>> none of which have you bothered to read. In Linz, the theorem is
>>> presented as a corollary of a simpler theorem in chapter 11.
>>
>> 11.3, 11.4, and 11.5. I will look at them.
>
> Goodness! A good move. Why the change of heart?
>

There is enough progress now that I don't have to have an absolutely
single-minded focus.

THIS IS AN EASILY VERIFIABLE FACT:
Both H() and H1() take the machine code of P as input parameters and
correctly compute the mapping from this input to an accept ore reject
state on the basis of the actual behavior that these inputs actually
specify.

This makes them correct halt deciders for this input. I have correctly
refuted the halting theorem on the basis of the above facts. That people
here insist on contradicting facts that they know are true is not any
actual rebuttal at all.

Richard Damon

unread,
May 6, 2022, 11:08:37 PMMay 6
to
On 5/6/22 9:34 PM, olcott wrote:
> On 5/6/2022 8:07 PM, Ben wrote:
>> olcott <polc...@gmail.com> writes:
>>
>>> On 5/6/2022 7:11 PM, Ben wrote:
>>
>>>> The halting theorem follows, trivially, from lots of simpler theorems,
>>>> none of which have you bothered to read.  In Linz, the theorem is
>>>> presented as a corollary of a simpler theorem in chapter 11.
>>>
>>> 11.3, 11.4, and 11.5. I will look at them.
>>
>> Goodness!  A good move.  Why the change of heart?
>>
>
> There is enough progress now that I don't have to have an absolutely
> single-minded focus.
>
> THIS IS AN EASILY VERIFIABLE FACT:
> Both H() and H1() take the machine code of P as input parameters and
> correctly compute the mapping from this input to an accept ore reject
> state on the basis of the actual behavior that these inputs actually
> specify.
>
> This makes them correct halt deciders for this input. I have correctly
> refuted the halting theorem on the basis of the above facts. That people
> here insist on contradicting facts that they know are true is not any
> actual rebuttal at all.
>

No, to be correct Halt Deciders, they need to compute the HALTING
FUNCTION of that input, which is the behavior of the machine + input
represented by their input, in this case P(P).

Since you claim that this is not what they compute (because you say they
can't), they are not Halt Decider.

Since your definition of "Correct Simulation" disagrees with the
definiton used by the Halting Problem, you are not working on it, but on
your POOP, and you can't actually say anything about halting based on
your work.

Note, the definition of Halting refers to the behavior of a Machine, and
that machine is what the first part of the input represents, which is P.
Since you say P isn't the input, then your representation doesn't match
that needed to be a Halt Decider, it is just that simple.

Maybe once you try to write an actual Turing Machine and understand the
difference between the actual tape and what it represents, maybe you
will understand.

Ben

unread,
May 7, 2022, 6:47:13 PMMay 7
to
olcott <polc...@gmail.com> writes:

> On 5/6/2022 8:07 PM, Ben wrote:
>> olcott <polc...@gmail.com> writes:
>>
>>> On 5/6/2022 7:11 PM, Ben wrote:
>>
>>>> The halting theorem follows, trivially, from lots of simpler theorems,
>>>> none of which have you bothered to read. In Linz, the theorem is
>>>> presented as a corollary of a simpler theorem in chapter 11.
>>>
>>> 11.3, 11.4, and 11.5. I will look at them.
>> Goodness! A good move. Why the change of heart?
>
> There is enough progress now that I don't have to have an absolutely
> single-minded focus.

Progress?

> THIS IS AN EASILY VERIFIABLE FACT:
> Both H() and H1() take the machine code of P as input parameters and
> correctly compute the mapping from this input to an accept ore reject
> state on the basis of the actual behavior that these inputs actually
> specify.

But H does not decide the halting of P(P). What ever you are hiding by
all that waffle, it's just a way to avoid having to say that H(P,P) ==
false even though P(P) halts.

You've recently tried to imply that it's somehow invalid for is to even
ask for a D such that D(X,Y) == true if and only if X(Y) halts and false
otherwise, because X(Y) is not "an input". But that's just a recent
ruse. You've known how the C-version of the halting problem is defined
for years.

olcott

unread,
May 7, 2022, 7:14:57 PMMay 7
to
On 5/7/2022 5:47 PM, Ben wrote:
> olcott <polc...@gmail.com> writes:
>
>> On 5/6/2022 8:07 PM, Ben wrote:
>>> olcott <polc...@gmail.com> writes:
>>>
>>>> On 5/6/2022 7:11 PM, Ben wrote:
>>>
>>>>> The halting theorem follows, trivially, from lots of simpler theorems,
>>>>> none of which have you bothered to read. In Linz, the theorem is
>>>>> presented as a corollary of a simpler theorem in chapter 11.
>>>>
>>>> 11.3, 11.4, and 11.5. I will look at them.
>>> Goodness! A good move. Why the change of heart?
>>
>> There is enough progress now that I don't have to have an absolutely
>> single-minded focus.
>
> Progress?
>
>> THIS IS AN EASILY VERIFIABLE FACT:
>> Both H() and H1() take the machine code of P as input parameters and
>> correctly compute the mapping from this input to an accept ore reject
>> state on the basis of the actual behavior that these inputs actually
>> specify.
>
> But H does not decide the halting of P(P).


int sum(int N , int M)
{
return (N + M);
}

It is not supposed to in the same way that sum(3,4) is not supposed to
provide the sum of (5,7).

Why is this so difficult for you?

You know that if anyone insisted that sum(3,4) must return the value of
sum(5,7) that they are wrong.

Why is it so hard to understand that H(P,P) must provide the halt status
of its actual input on the basis of the actual behavior specified by
this actual input?

It is just like you are insisting that you know for sure that sum(3,4)
is definitely 12. How nuts is that?

> What ever you are hiding by
> all that waffle, it's just a way to avoid having to say that H(P,P) ==
> false even though P(P) halts.
>
> You've recently tried to imply that it's somehow invalid for is to even
> ask for a D such that D(X,Y) == true if and only if X(Y) halts and false
> otherwise, because X(Y) is not "an input". But that's just a recent
> ruse. You've known how the C-version of the halting problem is defined
> for years.
>


--

Dennis Bush

unread,
May 7, 2022, 7:35:06 PMMay 7
to
Then why do you insist that H(P,P) must return the value of H(Pn,Pn)?

>
> Why is it so hard to understand that H(P,P) must provide the halt status
> of its actual input on the basis of the actual behavior specified by
> this actual input?

The *definition* of the problem states that the actual behavior of the actual input to H(P,P) is P(P).

You *say* there is infinite simulation but there is not *because* the copy of H inside P *will* abort.

If by "the actual behavior of the actual input" you mean "can the decider simulate the input to a final state", then that means that any simulating halt decider that reports non-halting is necessarily correct, which means that Ha3(N,5) == false is necessarily correct because by your definition "the actual behavior of the actual input" to Ha3(N,5) is non-halting.

Or you can just admit that H is unable to meet the requirements as specified:

H(P,P) == true if and only if P(P) halts, and
H(P,P) == false if and only if P(P) does not halt

And yes, H is expected by this definition to decide on non-inputs because the inputs represent non-inputs.

Ben

unread,
May 7, 2022, 7:46:30 PMMay 7
to
olcott <No...@NoWhere.com> writes:

> On 5/7/2022 5:47 PM, Ben wrote:
>> olcott <polc...@gmail.com> writes:
>>
>>> On 5/6/2022 8:07 PM, Ben wrote:
>>>> olcott <polc...@gmail.com> writes:
>>>>
>>>>> On 5/6/2022 7:11 PM, Ben wrote:
>>>>
>>>>>> The halting theorem follows, trivially, from lots of simpler theorems,
>>>>>> none of which have you bothered to read. In Linz, the theorem is
>>>>>> presented as a corollary of a simpler theorem in chapter 11.
>>>>>
>>>>> 11.3, 11.4, and 11.5. I will look at them.
>>>> Goodness! A good move. Why the change of heart?
>>>
>>> There is enough progress now that I don't have to have an absolutely
>>> single-minded focus.
>> Progress?
>>
>>> THIS IS AN EASILY VERIFIABLE FACT:
>>> Both H() and H1() take the machine code of P as input parameters and
>>> correctly compute the mapping from this input to an accept ore reject
>>> state on the basis of the actual behavior that these inputs actually
>>> specify.
>>
>> But H does not decide the halting of P(P).
>
> int sum(int N , int M)
> {
> return (N + M);
> }
>
> It is not supposed to in the same way that sum(3,4) is not supposed to
> provide the sum of (5,7).

You don't get to say. The problem you took on already existed. You've
only recently started this silly H(X,Y) is not supposed to provide the
halting of X(Y) after you where getting nowhere trying to persuade the
world that the wrong answer was the right one (because of what would
happen if...).

This is, I suppose, as close to an admission as you will ever make that
a halt decider that /is/ supposed to report on the halting of the
function call in question cant not exit.

> Why is this so difficult for you?
>
> You know that if anyone insisted that sum(3,4) must return the value
> of sum(5,7) that they are wrong.

Just as I know that Halts(X,Y) == false, even though X(Y) halts, is
wrong. It's wrong simply by definition.

> Why is it so hard to understand that H(P,P) must provide the halt
> status of its actual input on the basis of the actual behavior
> specified by this actual input?

You don't get to choose what H must decide. What the "input" (actually
the arguments) specify is defined by us, no you. We picked the problem,
you failed to find a solution. The behaviour that H(X,Y) must determine
is that of the call X(Y). Your H is wrong by definition.

olcott

unread,
May 7, 2022, 8:19:40 PMMay 7
to
The definition of decider requires it to based its decision on whatever
its input specifies.

Both H(P,P) and H1(P,P) use this exact literal byte string as their
input therefore it seems enormously dishonest of you to refer to the
same literal string using different subscripts indicating a difference
of the same string with itself.

558bec8b4508508b4d0851e840feffff83c40885c07402ebfe5dc3

_P()
[000009d6](01) 55 push ebp
[000009d7](02) 8bec mov ebp,esp
[000009d9](03) 8b4508 mov eax,[ebp+08]
[000009dc](01) 50 push eax // push P
[000009dd](03) 8b4d08 mov ecx,[ebp+08]
[000009e0](01) 51 push ecx // push P
[000009e1](05) e840feffff call 00000826 // call H
[000009e6](03) 83c408 add esp,+08
[000009e9](02) 85c0 test eax,eax
[000009eb](02) 7402 jz 000009ef
[000009ed](02) ebfe jmp 000009ed
[000009ef](01) 5d pop ebp
[000009f0](01) c3 ret // Final state
Size in bytes:(0027) [000009f0]


>>
>> Why is it so hard to understand that H(P,P) must provide the halt status
>> of its actual input on the basis of the actual behavior specified by
>> this actual input?
>
> The *definition* of the problem states that the actual behavior of the actual input to H(P,P) is P(P).

Whomever wrote that definition also knows that

THIS IS SET IN STONE:
All deciders only compute the mapping from their input parameters to an
accept/reject state on the basis of the actual properties actually
specified by this input

THIS LOGICALLY FOLLOWS FROM THAT:
Since a halt decider is a type of decider this means that all halt
deciders only compute the mapping from their input parameters to an
accept/reject state on the basis of the actual behavior actually
specified by this input.

This means that they simply made the false assumption that the correctly
simulated input to every simulating halt decider must always have
exactly the same behavior as the direct execution of this input.

It is a weird exception that they never noticed because they never
bothered to pursue simulating halt deciders applied to the HP to its
logical conclusion.

> You *say* there is infinite simulation but there is not *because* the copy of H inside P *will* abort.
>

I HAVE LITERALLY SAID THIS HUNDREDS OF TIMES
I say that the correctly simulated input to H(P,P) never reaches its
final state (thus never halts) whether or not its simulation is aborted.

> If by "the actual behavior of the actual input" you mean "can the decider simulate the input to a final state", then that means that any simulating halt decider that reports non-halting is necessarily correct,

Although technically correct use of terms I consider this utterly
ridiculous to say that a decider decides when all it does it guess.

I don't consider that a decder has decided anything unless it also
proves that its decision is correct. H(P,P)==false does that.
H1(P,P)==true also does that.

> which means that Ha3(N,5) == false is necessarily correct because by your definition "the

Can we please quite talking about you crackpot H3 that was intentionally
designed to get the wrong answer ???

actual behavior of the actual input" to Ha3(N,5) is non-halting.
>
> Or you can just admit that H is unable to meet the requirements as specified:
>
> H(P,P) == true if and only if P(P) halts, and
> H(P,P) == false if and only if P(P) does not halt
>

The requirements contradict the definition of a decider.
The author of these requirements was not aware of that.

> And yes, H is expected by this definition to decide on non-inputs because the inputs represent non-inputs.

That is exactly the same as requiring sum(3,4) to return 12, quite nuts.

Dennis Bush

unread,
May 7, 2022, 8:48:45 PMMay 7
to
Which in the case of H(P,P) is *defined* to be P(P)

>
> Both H(P,P) and H1(P,P) use this exact literal byte string as their
> input therefore it seems enormously dishonest of you to refer to the
> same literal string using different subscripts indicating a difference
> of the same string with itself.

What I was saying is that you think that H sees infinite simulation which only exists in Pn(Pn)
Which in the case of H(P,P) is *defined* to be P(P)

>
> THIS LOGICALLY FOLLOWS FROM THAT:
> Since a halt decider is a type of decider this means that all halt
> deciders only compute the mapping from their input parameters to an
> accept/reject state on the basis of the actual behavior actually
> specified by this input.

Which in the case of H(P,P) is *defined* to be P(P)

>
> This means that they simply made the false assumption that the correctly
> simulated input to every simulating halt decider must always have
> exactly the same behavior as the direct execution of this input.

There is no assumption. A correct simulation of a machine is DEFINED to have the exact same behavior as the actual machine. What good would a simulation be if that wasn't the case?

>
> It is a weird exception that they never noticed because they never
> bothered to pursue simulating halt deciders applied to the HP to its
> logical conclusion.

Just because H(P,P) is unable to simulate its input to a final state doesn't mean it's correct.


> > You *say* there is infinite simulation but there is not *because* the copy of H inside P *will* abort.
> >
> I HAVE LITERALLY SAID THIS HUNDREDS OF TIMES
> I say that the correctly simulated input to H(P,P) never reaches its
> final state (thus never halts) whether or not its simulation is aborted.

That is false, because the correctly simulated to input to H(P,P) is performed by H1(P,P) which does reach a final state.

If by "whether or not its simulation is aborted" you mean if the H embedded in P is changed, that can't happen as it changes the input. What it sounds like you mean by this is that Hi(Pi,Pi) either does not halt or always returns false for any Hi and the corresponding Pi built from it. Just because all of these unrelated H's return false for their corresponding P's doesn't make them all correct. This is like treating "hello world" and minesweeper the same.

> > If by "the actual behavior of the actual input" you mean "can the decider simulate the input to a final state", then that means that any simulating halt decider that reports non-halting is necessarily correct,
> Although technically correct use of terms I consider this utterly
> ridiculous to say that a decider decides when all it does it guess.

And guessing is exactly what H is doing, and it guesses wrong.

>
> I don't consider that a decder has decided anything unless it also
> proves that its decision is correct. H(P,P)==false does that.
> H1(P,P)==true also does that.

FALSE. H1(P,P)==true proves that H(P,P)==false is wrong. The simulation performed by both is identical up to the point that H aborts. H1 is then able to continue simulating past the point that H aborted and reach a final state, proving that H(P,P) == false is wrong.

If H1(P,P) == true doesn't prove H(P,P) == false incorrect then Ha7(N,5) == true doesn't prove Ha3(N,5) == false incorrect.

> > which means that Ha3(N,5) == false is necessarily correct because by your definition "the
> Can we please quite talking about you crackpot H3 that was intentionally
> designed to get the wrong answer ???
> actual behavior of the actual input" to Ha3(N,5) is non-halting.

I'm not the one saying Ha3 is correct. You are, by your definition of what the right answer should be. That's why I keep talking about it. It's wrong in EXACTLY the same way H is wrong, specifically it aborts too soon. You don't like talking about Ha3 because you can't clearly state why it is wrong without also proving that H is wrong.

> >
> > Or you can just admit that H is unable to meet the requirements as specified:
> >
> > H(P,P) == true if and only if P(P) halts, and
> > H(P,P) == false if and only if P(P) does not halt
> >
> The requirements contradict the definition of a decider.
> The author of these requirements was not aware of that.

Doesn't matter, as that is the definition of the problem. You don't get to say it's wrong. Just because the requirements can't be met (as the proof shows) doesn't mean they're wrong.

> > And yes, H is expected by this definition to decide on non-inputs because the inputs represent non-inputs.
> That is exactly the same as requiring sum(3,4) to return 12, quite nuts.

If sum is required to return the product of its arguments (despite its name), then yes.

olcott

unread,
May 7, 2022, 9:08:33 PMMay 7
to
In this case it is the same as if {dogs} are defined to be {cats}.

>>
>> Both H(P,P) and H1(P,P) use this exact literal byte string as their
>> input therefore it seems enormously dishonest of you to refer to the
>> same literal string using different subscripts indicating a difference
>> of the same string with itself.
>
> What I was saying is that you think that H sees infinite simulation which only exists in Pn(Pn)

All that crazy bullshit about subscripted names of subscripts is
extremely deceptive

I am ONLY referring to this literal string:
558bec8b4508508b4d0851e840feffff83c40885c07402ebfe5dc3
as x86 machine code correctly simulated by H(P,P) and H1(P,P).
In this case it is the same as if {dogs} are defined to be {cats}.

>
>>
>> THIS LOGICALLY FOLLOWS FROM THAT:
>> Since a halt decider is a type of decider this means that all halt
>> deciders only compute the mapping from their input parameters to an
>> accept/reject state on the basis of the actual behavior actually
>> specified by this input.
>
> Which in the case of H(P,P) is *defined* to be P(P)
>

In this case it is the same as if {dogs} are defined to be {cats}.
If anyone assigns non-decider properties to a decider they are wrong in
the same way that it is wrong to assign {cat} properties to a {dog}.

>>
>> This means that they simply made the false assumption that the correctly
>> simulated input to every simulating halt decider must always have
>> exactly the same behavior as the direct execution of this input.
>
> There is no assumption. A correct simulation of a machine is DEFINED to have the exact same behavior as the actual machine. What good would a simulation be if that wasn't the case?
>
>>
>> It is a weird exception that they never noticed because they never
>> bothered to pursue simulating halt deciders applied to the HP to its
>> logical conclusion.
>
> Just because H(P,P) is unable to simulate its input to a final state doesn't mean it's correct.
>
>
>>> You *say* there is infinite simulation but there is not *because* the copy of H inside P *will* abort.
>>>
>> I HAVE LITERALLY SAID THIS HUNDREDS OF TIMES
>> I say that the correctly simulated input to H(P,P) never reaches its
>> final state (thus never halts) whether or not its simulation is aborted.
>
> That is false, because the correctly simulated to input to H(P,P) is performed by H1(P,P) which does reach a final state.

H(P,P) does correctly map the behavior of its inputs to its reject state
this is a verifiable fact.

H1(P,P) does correctly map the behavior of its inputs to its accept
state this is a verifiable fact.

I am probably not going to bother to talk to people that insist on
disagreeing with verified facts.

Richard Damon

unread,
May 7, 2022, 9:09:32 PMMay 7
to
Please give your exact definition of a decider that you are using.



>
> Both H(P,P) and H1(P,P) use this exact literal byte string as their
> input therefore it seems enormously dishonest of you to refer to the
> same literal string using different subscripts indicating a difference
> of the same string with itself.

except that byte string isn't a fully specified program, so you have an
error in you definition.

This input references something outside of it, so that program segment
can have virtually any behavior imaginable.


(Note, call to 0000826 is NOT the same as a "Call H" instruction, as not
all machines have your H at that address.)
But the only ACTUAL PROPERTY that it needs to look at is the behavior of
the program the input represents, whether it halts or not.

Now, if that byte string included the required copy of the code of H,
and that H was actually a difinite program like you claim it is, then
this halting property is actually well defined, we can just run this
program and see if it halts.

Now,

>
> THIS LOGICALLY FOLLOWS FROM THAT:
> Since a halt decider is a type of decider this means that all halt
> deciders only compute the mapping from their input parameters to an
> accept/reject state on the basis of the actual behavior actually
> specified by this input.

Right, would the program (the WHOLE PROGRAM, so we need the WHOLE
PROGRAM) run to a halt when exectuted.

Since P(P) does halt if H(P,P) returns false, we can see that H(P,P)
returning false must be wrong, as it would have needed to have returned
true for that exact byte sequence input.

>
> This means that they simply made the false assumption that the correctly
> simulated input to every simulating halt decider must always have
> exactly the same behavior as the direct execution of this input.

Nope, YOU are making the error, because your logic isn't about *A*
program H.

>
> It is a weird exception that they never noticed because they never
> bothered to pursue simulating halt deciders applied to the HP to its
> logical conclusion.

Nope, not an execptiion, just a flaw in your logic because your H isn't
an actual finite definite algorthm.

>
>> You *say* there is infinite simulation but there is not *because* the
>> copy of H inside P *will* abort.
>>
>
> I HAVE LITERALLY SAID THIS HUNDREDS OF TIMES
> I say that the correctly simulated input to H(P,P) never reaches its
> final state (thus never halts) whether or not its simulation is aborted.

Nope, because you use the wrong definition for too many things.

You H is NOT a computation, because it doesn't have a finite fixed
algorithm, but uses words that requrie it to look into the future with
some sort of crystal ball.

You do not define "Correct Simulation", perhaps because the thing you
are simulating isn't a computation because it is based on your H which
isn't one.


>
>> If by "the actual behavior of the actual input" you mean "can the
>> decider simulate the input to a final state", then that means that any
>> simulating halt decider that reports non-halting is necessarily correct,
>
> Although technically correct use of terms I consider this utterly
> ridiculous to say that a decider decides when all it does it guess.
>
> I don't consider that a decder has decided anything unless it also
> proves that its decision is correct. H(P,P)==false does that.
> H1(P,P)==true also does that.

Then show an ACTUAL proof.

Note, H needs to prove that the P built on it will not halt. Not that H
can not simulate P to its final state. Since H(P,P) is claiming false is
the right answer, its proof needs to be compatible with the H(P,P)
inside P returning that same value.

>
>> which means that Ha3(N,5) == false is necessarily correct because by
>> your definition "the
>
> Can we please quite talking about you crackpot H3 that was intentionally
> designed to get the wrong answer ???
>
> actual behavior of the actual input" to Ha3(N,5) is non-halting.
>>
>> Or you can just admit that H is unable to meet the requirements as
>> specified:
>>
>> H(P,P) == true if and only if P(P) halts, and
>> H(P,P) == false if and only if P(P) does not halt
>>
>
> The requirements contradict the definition of a decider.
> The author of these requirements was not aware of that.

Nok YOUR requirements contradict the definiton of a Halting Decider, (or
any specfic type of decider) as the answer to a XX Decider, must be
based on the XX mapping of the input to the decide, and the Halting
Mapping of P,P is to if P(P) Halts. If you are trying to show that it is
impossible to even properlly ask an H that question, then you have just
admitted that a Halt Decider is impossible, as if you can't even ask the
right question, you can't expect it to be able to give the right answer.

Maybe H correctly computes that alternate mapping you have defined, your
Other Problem mapping, but that just makes your H a POOP decider, not a
Halting Decider.

Richard Damon

unread,
May 7, 2022, 9:22:17 PMMay 7
to
On 5/7/22 8:19 PM, olcott wrote:
Except that isn't the correct string for either Pn or Pa, as we need the
contents of memory address 826 and beyond, or the program isn't actually
specifed by this input.

This is your fatal flaw in your "proof".

Your system is built on broken definitions.

Dennis Bush

unread,
May 7, 2022, 9:26:11 PMMay 7
to
So no rebuttal, just a bad analogy.

> >>
> >> Both H(P,P) and H1(P,P) use this exact literal byte string as their
> >> input therefore it seems enormously dishonest of you to refer to the
> >> same literal string using different subscripts indicating a difference
> >> of the same string with itself.
> >
> > What I was saying is that you think that H sees infinite simulation which only exists in Pn(Pn)
> All that crazy bullshit about subscripted names of subscripts is
> extremely deceptive

No, just the opposite. It makes it clear *exactly* which computation we're talking about, so it prevents YOU from being deceptive.

>
> I am ONLY referring to this literal string:
> 558bec8b4508508b4d0851e840feffff83c40885c07402ebfe5dc3
> as x86 machine code correctly simulated by H(P,P) and H1(P,P).

No you're not. You're also referring to the literal string which is the fixed code of H which aborts as that is part of the program P. So from here on, we'll refer to H as Ha and P as Pa to make that point clear.

For a separate H that never aborts which we'll call Hn, and Pn which calls that Hn, infinite simulation *does* happens so Ha(Pn,Pn) does correctly report non-halting. Your error is that you think this has anything to do with Ha(Pa,Pa) which is the case that matters.
Again, no rebuttal, just a bad analogy.

> >
> >>
> >> THIS LOGICALLY FOLLOWS FROM THAT:
> >> Since a halt decider is a type of decider this means that all halt
> >> deciders only compute the mapping from their input parameters to an
> >> accept/reject state on the basis of the actual behavior actually
> >> specified by this input.
> >
> > Which in the case of H(P,P) is *defined* to be P(P)
> >
> In this case it is the same as if {dogs} are defined to be {cats}.
> If anyone assigns non-decider properties to a decider they are wrong in
> the same way that it is wrong to assign {cat} properties to a {dog}.

And again no rebuttal, just a bad analogy. Given that this is the third time you've done this, I'll take this as an admission of defeat.

> >>
> >> This means that they simply made the false assumption that the correctly
> >> simulated input to every simulating halt decider must always have
> >> exactly the same behavior as the direct execution of this input.
> >
> > There is no assumption. A correct simulation of a machine is DEFINED to have the exact same behavior as the actual machine. What good would a simulation be if that wasn't the case?
> >
> >>
> >> It is a weird exception that they never noticed because they never
> >> bothered to pursue simulating halt deciders applied to the HP to its
> >> logical conclusion.
> >
> > Just because H(P,P) is unable to simulate its input to a final state doesn't mean it's correct.
> >
> >
> >>> You *say* there is infinite simulation but there is not *because* the copy of H inside P *will* abort.
> >>>
> >> I HAVE LITERALLY SAID THIS HUNDREDS OF TIMES
> >> I say that the correctly simulated input to H(P,P) never reaches its
> >> final state (thus never halts) whether or not its simulation is aborted.
> >
> > That is false, because the correctly simulated to input to H(P,P) is performed by H1(P,P) which does reach a final state.
> H(P,P) does correctly map the behavior of its inputs to its reject state
> this is a verifiable fact.

FALSE, because it is counter to the defined mapping for the halting function. Pa(Pa) halts, so Ha(Pa,Pa) == false is wrong.

>
> H1(P,P) does correctly map the behavior of its inputs to its accept
> state this is a verifiable fact.

This is true.

>
> I am probably not going to bother to talk to people that insist on
> disagreeing with verified facts.

At least you won't be talking to yourself.

olcott

unread,
May 7, 2022, 10:20:27 PMMay 7
to
I am only referring to this literal string:
558bec8b4508508b4d0851e840feffff83c40885c07402ebfe5dc3

as an input to H(P,P) and H1(P,P). It is 100% perfectly concrete thus
utterly impervious to even extremely well-crafted attempts at deception
through the strawman error. Any attempt to get around this will be
construed as (and labeled) a bald-faced lie by a bald-faced liar.
It is a verified fact that at least Linz claims that H must report on Ĥ
applied to ⟨Ĥ⟩.


It is also a verified fact that this same requirement directly
contradicts the definition of decider that must map its actual inputs to
an accept/reject state based on the actual behavior of these actual inputs.

When the author or a textbook disagrees with computer science
definitions it is not computer science that is on the losing side of this.

Dennis Bush

unread,
May 7, 2022, 10:36:23 PMMay 7
to
That string is 100% NOT concrete because it doesn't specify the function that it is calling. It therefore doesn't specify a complete computation, so NO that is not the only thing you're referring to. The H that it calls is a part of it and is therefore immutable. So YES, H is Ha and P is Pa because the fixed algorithm of H aborts and P calls this fixed H.

You seem to be using this to say:

For each i: because each Hi(Pi,Pi) == false, and because Hn(Pn,Pn) does not halt, then each Hi(Pi,Pi) == false is correct.

Each Pi is distinct from each other, and each Hi is distinct from each other. That each Hi is unable to simulate the Pi built from it to a final state proves nothing regarding whether each of them is correct to return false. "Hello world" and Minesweeper are not the same program, so one can't be used to make conclusions about the other.
As it is required to.

>
>
> It is also a verified fact that this same requirement directly
> contradicts the definition of decider that must map its actual inputs to
> an accept/reject state based on the actual behavior of these actual inputs.

It does not, because the actual behavior of the actual inputs is defined to be the machine that those inputs represent.

>
> When the author or a textbook disagrees with computer science
> definitions it is not computer science that is on the losing side of this.

It doesn't. You just don't understand the definitions.


olcott

unread,
May 9, 2022, 11:31:16 AMMay 9
to
I did not freaking say that this finite string specifies every freaking
detail of the whole freaking system nitwit. This finite string as x86
code specifies every one of its own bytes.

It therefore doesn't specify a complete computation,

It knows you screwy and deceptive naming conventions on their ass.
These hexadecimal bytes are the stipulated as the input to H and H1.
558bec8b4508508b4d0851e840feffff83c40885c07402ebfe5dc3

> so NO that is not the only thing you're referring to. The H that it calls is a part of it and is therefore immutable. So YES, H is Ha and P is Pa because the fixed algorithm of H aborts and P calls this fixed H.
>

These are verified facts:
H(P,P)==false is provably correct.
Ha(P,P)==true is provably correct.
I have a guy that I want you to arrest, his name is in my head.
I am going to write down the name of some other guy, but I want
you to arrest the guy who is named in my head. I won't tell you
his name.

All halt deciders only compute the mapping from their inputs to their
own accept/reject state on the basis of the actual behavior actually
specified by the correct simulation of this input by the halt decider.

>
>>
>> When the author or a textbook disagrees with computer science
>> definitions it is not computer science that is on the losing side of this.
>
> It doesn't. You just don't understand the definitions.
>
>


Dennis Bush

unread,
May 9, 2022, 12:02:43 PMMay 9
to
Not the whole system, just the computation to be decided on, and that computation includes the FIXED code of H that aborts its simulation, i.e. Ha.

>> It therefore doesn't specify a complete computation,
> It knows you screwy and deceptive naming conventions on their ass.

You're projecting. The naming convention prevents YOU from being deceptive and claiming that P is the same computation no matter what the implementation of the called H is.

The P to be decided on has a fixed algorithm. This means the H it calls / has a copy of also has a fixed algorithm. So we refer to that fixed H as Ha and the fixed P that calls it is referred to as Pa.

Ha(Pa,Pa) does not perform a correct simulation because it doesn't simulate for long enough. Hb(Pa,Pa) does simulate that same input to a final state.

> These hexadecimal bytes are the stipulated as the input to H and H1.
> 558bec8b4508508b4d0851e840feffff83c40885c07402ebfe5dc3

FALSE. The input to a halt decider is the representation of a COMPLETE program/computation, and that is incomplete.

Just because a bunch of completely unrelated H's cannot simulate the completely unrelated P's built on them to a final state doesn't mean that all of them are correct.

> > so NO that is not the only thing you're referring to. The H that it calls is a part of it and is therefore immutable. So YES, H is Ha and P is Pa because the fixed algorithm of H aborts and P calls this fixed H.
> >
> These are verified facts:
> H(P,P)==false is provably correct.
> Ha(P,P)==true is provably correct.

As proved previously, Hb(Pa,Pa) == true proves that Ha(Pa,Pa) == false is wrong. If you disagree then that means you agree that Ha3(N,5) == false is correct because Ha7(N,5) == true doesn't disprove it.
Another bad analogy with no explanation.

>
> All halt deciders only compute the mapping from their inputs to their
> own accept/reject state on the basis of the actual behavior actually
> specified by the correct simulation of this input

Which is performed by an actual UTM, or alternately by a simulator that can simulate the input to a final state.

> by the halt decider.

Assuming the halt decider does a correct simulation

olcott

unread,
May 9, 2022, 12:06:01 PMMay 9
to
Thee is no Pa, Pb, Pc, there is only this P:
558bec8b4508508b4d0851e840feffff83c40885c07402ebfe5dc3

There is no Ha, Hb, Hc, there is only H and H1.

Dennis Bush

unread,
May 9, 2022, 12:30:54 PMMay 9
to
So if that's enough information to decide on, then tell me if this halts:

void F()
{
X()
}

You can't, because X isn't specified. In the same way, the string you give above doesn't specify H, and H is part of P.

The complete code of P must be fixed, which means the H it calls must be fixed.

Given Hn that never aborts, Pn is built from it. Pn(Pn) does not halt due to infinite simulation. You built Ha (which you call H) to detect this so that Ha(Pn,Pn) correctly returns false. Then Pa (which you call P) is built from Ha.

Ha(Pa,Pa) returns false because it *thinks* there is infinite simulation. There is not. Hb, which simulates for k more steps than Ha, can simulate past the point where Ha aborts, and Hb(Pa,Pa) == true, proving that Ha(Pa,Pa) == false is wrong.

>
> There is no Ha, Hb, Hc, there is only H and H1.

There absolutely is, as your wording of "whether or not H aborts" implies. This also means that the P that call each of these is distinct.

olcott

unread,
May 9, 2022, 12:39:59 PMMay 9
to
I am only talking about H(P,P) and H1(P,P) where P is this literal
string as x86 machine language:
558bec8b4508508b4d0851e840feffff83c40885c07402ebfe5dc3

Any replies diverging from this will simply be ignored without comment
as attempts to deceive using the strawman error

Dennis Bush

unread,
May 9, 2022, 12:52:29 PMMay 9
to
Again, not a complete computation, so not enough information to decide on. You seem to think that all "P" constructs are the same no matter how different the H it is built on is.

Just because:

H1(P1,P1) == false
H2(P2,P2) == false
H3(P3,P3) == false
H4(P4,P4) == false
H5(P5,P5) == false
...

Doesn't mean all of them are correct.

>
> Any replies diverging from this will simply be ignored without comment
> as attempts to deceive using the strawman error

Projection. You're the one attempting to deceive by using "P" and "H" to refer to multiple different computations at the same time.

You can't talk about P without talking about the *specific* H that it calls. Ha(Pa,Pa) == false is wrong as proved by Hb(Pa,Pa) == true

olcott

unread,
May 9, 2022, 1:18:28 PMMay 9
to
Within the context of my paper it is a complete computation for H(P,P).
I am updating the paper to include H1(P,P).


>
> Just because:
>
> H1(P1,P1) == false
> H2(P2,P2) == false
> H3(P3,P3) == false
> H4(P4,P4) == false
> H5(P5,P5) == false
> ...
>
> Doesn't mean all of them are correct.
>
>>
>> Any replies diverging from this will simply be ignored without comment
>> as attempts to deceive using the strawman error
>
> Projection. You're the one attempting to deceive by using "P" and "H" to refer to multiple different computations at the same time.
>
> You can't talk about P without talking about the *specific* H that it calls. Ha(Pa,Pa) == false is wrong as proved by Hb(Pa,Pa) == true
>


Dennis Bush

unread,
May 9, 2022, 1:26:57 PMMay 9
to
So if H is the *specific* decider that can detect infinite simulation in Pn(Pn), then we'll refer to it as Ha to clarify that point, and we'll refer to the P that calls it as Pa to clarify.

Ha(Pa,Pa) returns false because it *thinks* there is infinite simulation. There is not. Hb, which simulates for k more steps than Ha, can simulate past the point where Ha aborts. Hb(Pa,Pa) == true after simulating to a final state, proving that Ha(Pa,Pa) == false is wrong.

olcott

unread,
May 9, 2022, 4:18:04 PMMay 9
to
I am talking about the literal string of "H" being applied to this
literal string: 558bec8b4508508b4d0851e840feffff83c40885c07402ebfe5dc3

and

The literal string of "H1" being applied to this literal string:
558bec8b4508508b4d0851e840feffff83c40885c07402ebfe5dc3

Perhaps you were unaware that literal strings do not vary and are thus
not variables.

Dennis Bush

unread,
May 9, 2022, 4:27:15 PMMay 9
to
And to complete the computation being evaluated, what is the *exact*, FIXED algorithm of H? If it is Ha, then Ha(Pa,Pa) == false is wrong as demonstrated by Hb(Pa,Pa) == true.

If H is using some other algorithm, then specify the *exact* algorithm.

olcott

unread,
May 9, 2022, 4:51:57 PMMay 9
to
H and H1 are both literal byte strings that emulate their literal byte
string input in pure x86 emulation mode until the behavior of this
emulated literal byte string input shows that it would never reach its
own final state (0xc3 ret instruction).

Dennis Bush

unread,
May 9, 2022, 4:59:11 PMMay 9
to
So in other words, the fixed algorithm of H looks for what it thinks is infinite simulation. So H is Ha, which means P is Pa.

Hb can then be constructed to simulate for k more steps than Ha and calculate Hb(Pa,Pa) == true, proving Ha(Pa,Pa) == false wrong.

olcott

unread,
May 9, 2022, 5:20:02 PMMay 9
to
Begin Local Halt Decider Simulation
machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
...[000009d6][00211368][0021136c] 55 push ebp // enter P
...[000009d7][00211368][0021136c] 8bec mov ebp,esp
...[000009d9][00211368][0021136c] 8b4508 mov eax,[ebp+08]
...[000009dc][00211364][000009d6] 50 push eax // Push P
...[000009dd][00211364][000009d6] 8b4d08 mov ecx,[ebp+08]
...[000009e0][00211360][000009d6] 51 push ecx // Push P
...[000009e1][0021135c][000009e6] e840feffff call 00000826 // Call H
...[000009d6][0025bd90][0025bd94] 55 push ebp // enter P
...[000009d7][0025bd90][0025bd94] 8bec mov ebp,esp
...[000009d9][0025bd90][0025bd94] 8b4508 mov eax,[ebp+08]
...[000009dc][0025bd8c][000009d6] 50 push eax // Push P
...[000009dd][0025bd8c][000009d6] 8b4d08 mov ecx,[ebp+08]
...[000009e0][0025bd88][000009d6] 51 push ecx // Push P
...[000009e1][0025bd84][000009e6] e840feffff call 00000826 // Call H
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

The fact that P calls the same function from its same machine address
with identical input parameters conclusively proves that P is stuck in
infinite recursion.

Dennis Bush

unread,
May 9, 2022, 5:30:45 PMMay 9
to
First, it's not recursion, infinite or otherwise. It's nested simulation, and the conditions that are part of the simulation are relevant.

And it's not infinite nested simulation because Hb simulates Pa past the point where Ha aborts, sees that the embedded copy of Ha aborts, and sees Pa halt. So Ha is wrong.

wij

unread,
May 9, 2022, 5:51:51 PMMay 9
to
Your coding is invalid, because H is now shown to exist.

wij

unread,
May 9, 2022, 5:53:58 PMMay 9
to
Your coding is invalid, because H is not shown to exist (call what or who?).

Jeff Barnett

unread,
May 9, 2022, 6:12:12 PMMay 9
to
On 5/9/2022 3:19 PM, olcott wrote:

SNIP
Let's say that H looks like

Procedure H(args...)
Declare foo Own integer initially 10,000;
foo <- foo - 1;
If foo = 0 then signal ("halt 10000");
do stuff .....
Return ;
End H;

Then your simulation is total crap. Put up (show H, your coding is known
untrustworthy) or shut up (this option would be most appreciated). If
you don't know what "Own" is, ask Ben. So far, he's been charitable with
his time and might help you. Or you can try Google.

[By the way, there was an ambiguity about Own in an Algol spec that
might be in play here since you claim that H is in a recursive loop.
Fortunately, that will not effect the point of the above, it will just
strengthen the effect no matter what the interpretation.]
--
Jeff Barnett

olcott

unread,
May 9, 2022, 6:18:31 PMMay 9
to