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

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

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

On Thu, 5 May 2022 16:30:41 -0500
olcott <polcott2@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

On 5/5/2022 4:39 PM, Mr Flibble wrote:
> On Thu, 5 May 2022 16:30:41 -0500
> olcott <polcott2@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
>

Yes what you said is equally true:
https://www.sciencedirect.com/science/article/pii/S235222082100050X

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

On Thu, 5 May 2022 16:48:21 -0500
olcott <polcott2@gmail.com> wrote:

> On 5/5/2022 4:39 PM, Mr Flibble wrote:
> > On Thu, 5 May 2022 16:30:41 -0500
> > olcott <polcott2@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
> >
>
> 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?

/Flibble

On 5/5/2022 4:53 PM, Mr Flibble wrote:
> On Thu, 5 May 2022 16:48:21 -0500
> olcott <polcott2@gmail.com> wrote:
>
>> On 5/5/2022 4:39 PM, Mr Flibble wrote:
>>> On Thu, 5 May 2022 16:30:41 -0500
>>> olcott <polcott2@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
>>>
>>
>> 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?
>
> /Flibble
>

Right, so it proves that you are right and Ben is wrong.
What Turing wrote in 1936 is now known as 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

olcott <polcott2@gmail.com> writes:

> On 5/5/2022 4:53 PM, Mr Flibble wrote:
>> On Thu, 5 May 2022 16:48:21 -0500
>> olcott <polcott2@gmail.com> wrote:
>>
>>> On 5/5/2022 4:39 PM, Mr Flibble wrote:
>>>> On Thu, 5 May 2022 16:30:41 -0500
>>>> olcott <polcott2@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]
>>>>
>>>
>>> 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)

On 5/5/2022 8:34 PM, Ben wrote:
> olcott <polcott2@gmail.com> writes:
>
>> On 5/5/2022 4:53 PM, Mr Flibble wrote:
>>> On Thu, 5 May 2022 16:48:21 -0500
>>> olcott <polcott2@gmail.com> wrote:
>>>
>>>> On 5/5/2022 4:39 PM, Mr Flibble wrote:
>>>>> On Thu, 5 May 2022 16:30:41 -0500
>>>>> olcott <polcott2@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]
>>>>>
>>>>
>>>> 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.)
>

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

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

On Fri, 06 May 2022 02:34:35 +0100
Ben <ben.usenet@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

Mr Flibble <flibble@reddwarf.jmc> writes:

> On Fri, 06 May 2022 02:34:35 +0100
> Ben <ben.usenet@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.

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.

olcott <polcott2@gmail.com> writes:

> On 5/5/2022 8:34 PM, Ben wrote:
>> olcott <polcott2@gmail.com> writes:
>>
>>> On 5/5/2022 4:53 PM, Mr Flibble wrote:
>>>> On Thu, 5 May 2022 16:48:21 -0500
>>>> olcott <polcott2@gmail.com> wrote:
>>>>
>>>>> On 5/5/2022 4:39 PM, Mr Flibble wrote:
>>>>>> On Thu, 5 May 2022 16:30:41 -0500
>>>>>> olcott <polcott2@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]
>>>>>>
>>>>>
>>>>> 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.)
>
> 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

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

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

On 5/5/2022 8:50 PM, Ben wrote:
> Mr Flibble <flibble@reddwarf.jmc> writes:
>
>> On Fri, 06 May 2022 02:34:35 +0100
>> Ben <ben.usenet@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.
>
> 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.

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

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

On Fri, 06 May 2022 03:50:46 +0100
Ben <ben.usenet@bsb.me.uk> wrote:

> Mr Flibble <flibble@reddwarf.jmc> writes:
>
> > On Fri, 06 May 2022 02:34:35 +0100
> > Ben <ben.usenet@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

On Fri, 6 May 2022 16:09:13 +0300
Mikko <mikko.levanto@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

On Thu, 5 May 2022 23:01:29 -0600
Jeff Barnett <jbb@notatt.com> wrote:

> On 5/5/2022 8:50 PM, Ben wrote:
> > Mr Flibble <flibble@reddwarf.jmc> writes:
> >
> >> On Fri, 06 May 2022 02:34:35 +0100
> >> Ben <ben.usenet@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.
> >
> > 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.
>
> 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 .....

Gas.

/Flibble

On 2022-05-06 13:59:44 +0000, Mr Flibble said:

> On Fri, 6 May 2022 16:09:13 +0300
> Mikko <mikko.levanto@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

On 5/6/2022 11:16 AM, Mikko wrote:
> On 2022-05-06 13:59:44 +0000, Mr Flibble said:
>
>> On Fri, 6 May 2022 16:09:13 +0300
>> Mikko <mikko.levanto@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

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

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

On 5/6/2022 8:56 AM, Mr Flibble wrote:
> On Fri, 06 May 2022 03:50:46 +0100
> Ben <ben.usenet@bsb.me.uk> wrote:
>
>> Mr Flibble <flibble@reddwarf.jmc> writes:
>>
>>> On Fri, 06 May 2022 02:34:35 +0100
>>> Ben <ben.usenet@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. It is currently understood
that Turing's 1936 paper does establish what is now known as 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

On 5/6/2022 8:59 AM, Mr Flibble wrote:
> On Fri, 6 May 2022 16:09:13 +0300
> Mikko <mikko.levanto@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
>

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.

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

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

--
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 <flibble@reddwarf.jmc> writes:

> On Fri, 06 May 2022 03:50:46 +0100
> Ben <ben.usenet@bsb.me.uk> wrote:
>
>> Mr Flibble <flibble@reddwarf.jmc> writes:
>>
>> > On Fri, 06 May 2022 02:34:35 +0100
>> > Ben <ben.usenet@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.

olcott <polcott2@gmail.com> writes:

> On 5/6/2022 8:56 AM, Mr Flibble wrote:
>> On Fri, 06 May 2022 03:50:46 +0100
>> Ben <ben.usenet@bsb.me.uk> wrote:
>>
>>> Mr Flibble <flibble@reddwarf.jmc> writes:
>>>
>>>> On Fri, 06 May 2022 02:34:35 +0100
>>>> Ben <ben.usenet@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.

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

On 5/6/2022 7:11 PM, Ben wrote:
> olcott <polcott2@gmail.com> writes:
>
>> On 5/6/2022 8:56 AM, Mr Flibble wrote:
>>> On Fri, 06 May 2022 03:50:46 +0100
>>> Ben <ben.usenet@bsb.me.uk> wrote:
>>>
>>>> Mr Flibble <flibble@reddwarf.jmc> writes:
>>>>
>>>>> On Fri, 06 May 2022 02:34:35 +0100
>>>>> Ben <ben.usenet@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.
>

11.3, 11.4, and 11.5. I will look at them.

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

olcott <polcott2@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?

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