On 7/10/2021 12:00 PM, Mr Flibble wrote:
> I agree with Olcott that a halt decider can NOT be part of that which
> is being decided (see [Strachey 1965]) which, if Olcott is correct,
> falsifies a collection of proofs (which I don't have the time to
> examine) which rely on that mistake. The mistake Olcott seems to be
> making is inferring that just because those proofs are invalid then that
> somehow means that the halting problem itself is not undecidable.
>
> /Flibble
>

[An impossible program] C. Strachey
The Computer Journal, Volume 7, Issue 4, January 1965, Page 313,
https://doi.org/10.1093/comjnl/7.4.313

https://academic.oup.com/comjnl/article/7/4/313/354243

No I never made that mistake, My goal since 2004 has always been to
simply prove that the proofs are incorrect. Here is my original 2004
claim that everyone has disagreed with in more than 15,000 messages
since 2004:

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

--
Copyright 2021 Pete Olcott

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

On 7/10/2021 12:12 PM, Mr Flibble wrote:
> On Sat, 10 Jul 2021 12:08:02 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> The Halting Problem can only exist because
>> of this same sort of pathological self-reference.
>
> ^ that is your mistake: the halting problem still exists even if a
> collection of proofs have a mistake.
>
> Does [Turing 1937] rely on a decider being part of that which is
> being decided? Wikipedia suggests not:
>
> "Turing's proof departs from calculation by recursive functions and
> introduces the notion of computation by machine."
>
> /Flibble
>

*I agree that I have not solved the halting problem*
At most I have only proved that the conventional proofs of the
undecidability of the halting problem that rely on the Strachey form,
are incorrect. This seems to include all textbook proofs.

[An impossible program] C. Strachey
The Computer Journal, Volume 7, Issue 4, January 1965, Page 313,
https://doi.org/10.1093/comjnl/7.4.313

Now seems to be a good time to finally look at the Turing proof.
https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
I am not sure if the above linked copy has the later published correction.

If the Turing proof is isomorphic to the Strachey form, I don't know
what it left to prove that the halting problem is undecidable.

Goldbach's Conjecture is merely undecided and thus not undecidable.
https://en.wikipedia.org/wiki/Goldbach%27s_conjecture

Busy Beaver only seems intractable not undecidable.
https://en.wikipedia.org/wiki/Busy_beaver

--
Copyright 2021 Pete Olcott

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

On 7/10/2021 1:23 PM, Mr Flibble wrote:
> On Sat, 10 Jul 2021 13:06:35 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 7/10/2021 12:12 PM, Mr Flibble wrote:
>>> On Sat, 10 Jul 2021 12:08:02 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> The Halting Problem can only exist because
>>>> of this same sort of pathological self-reference.
>>>
>>> ^ that is your mistake: the halting problem still exists even if a
>>> collection of proofs have a mistake.
>>>
>>> Does [Turing 1937] rely on a decider being part of that which is
>>> being decided? Wikipedia suggests not:
>>>
>>> "Turing's proof departs from calculation by recursive functions and
>>> introduces the notion of computation by machine."
>>>
>>> /Flibble
>>>
>>
>> *I agree that I have not solved the halting problem*
>> At most I have only proved that the conventional proofs of the
>> undecidability of the halting problem that rely on the Strachey form,
>> are incorrect. This seems to include all textbook proofs.
>
> You need to reign in the ego, mate, Strachey deserves the credit not
> you unless you are claiming that you have independently reached the same
> conclusion as Strachey without being aware of Strachey until recently?
>
> /Flibble
>

All of the textbooks cite the Strachey form as proof that the halting
problem is undecidable. Ben, Mike and Kaz agree that the Strachey form
proves that the halting problem is undecidable.

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

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

When Strachey says:
"this contradiction shows that the function T cannot exist."

He is saying that he just proved that a universal halt decider {function
T} does not exist.

--
Copyright 2021 Pete Olcott

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

On 7/10/2021 1:59 PM, Mr Flibble wrote:
> On Sat, 10 Jul 2021 13:45:38 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 7/10/2021 1:38 PM, Mr Flibble wrote:
>>> On Sat, 10 Jul 2021 13:32:40 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 7/10/2021 1:23 PM, Mr Flibble wrote:
>>>>> On Sat, 10 Jul 2021 13:06:35 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>
>>>>>> On 7/10/2021 12:12 PM, Mr Flibble wrote:
>>>>>>> On Sat, 10 Jul 2021 12:08:02 -0500
>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>
>>>>>>>> The Halting Problem can only exist because
>>>>>>>> of this same sort of pathological self-reference.
>>>>>>>
>>>>>>> ^ that is your mistake: the halting problem still exists even
>>>>>>> if a collection of proofs have a mistake.
>>>>>>>
>>>>>>> Does [Turing 1937] rely on a decider being part of that which is
>>>>>>> being decided? Wikipedia suggests not:
>>>>>>>
>>>>>>> "Turing's proof departs from calculation by recursive functions
>>>>>>> and introduces the notion of computation by machine."
>>>>>>>
>>>>>>> /Flibble
>>>>>>>
>>>>>>
>>>>>> *I agree that I have not solved the halting problem*
>>>>>> At most I have only proved that the conventional proofs of the
>>>>>> undecidability of the halting problem that rely on the Strachey
>>>>>> form, are incorrect. This seems to include all textbook proofs.
>>>>>
>>>>> You need to reign in the ego, mate, Strachey deserves the credit
>>>>> not you unless you are claiming that you have independently
>>>>> reached the same conclusion as Strachey without being aware of
>>>>> Strachey until recently?
>>>>>
>>>>> /Flibble
>>>>>
>>>>
>>>> All of the textbooks cite the Strachey form as proof that the
>>>> halting problem is undecidable. Ben, Mike and Kaz agree that the
>>>> Strachey form proves that the halting problem is undecidable.
>>>>
>>>> rec routine P
>>>> §L:if T[P] go to L
>>>> Return §
>>>>
>>>> If T[P] = True the routine P will loop, and it will
>>>> only terminate if T[P] = False. In each case T[P] has
>>>> exactly the wrong value, and this contradiction shows
>>>> that the function T cannot exist.
>>>>
>>>> When Strachey says:
>>>> "this contradiction shows that the function T cannot exist."
>>>>
>>>> He is saying that he just proved that a universal halt decider
>>>> {function T} does not exist.
>>>
>>> No he isn't; he is saying that a decider can not be part of what is
>>> being decided which is quite different.
>>
>> So when Strachey says:
>> "this contradiction shows that the function T cannot exist."
>>
>> Strachey does not mean
>> {this contradiction shows that the function T cannot exist.}
>
> He means T cannot decide on P if T is called from within P; i.e. the
> "pathological self reference" you keep going on about.
>
> /Flibble
>

Yes and he and everyone else here besides you and I believes that this
proves that the halting problem is undecidable.

--
Copyright 2021 Pete Olcott

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

On Sat, 10 Jul 2021 14:09:07 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 7/10/2021 1:59 PM, Mr Flibble wrote:
> > On Sat, 10 Jul 2021 13:45:38 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >
> >> On 7/10/2021 1:38 PM, Mr Flibble wrote:
> >>> On Sat, 10 Jul 2021 13:32:40 -0500
> >>> olcott <NoOne@NoWhere.com> wrote:
> >>>
> >>>> On 7/10/2021 1:23 PM, Mr Flibble wrote:
> >>>>> On Sat, 10 Jul 2021 13:06:35 -0500
> >>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>
> >>>>>> On 7/10/2021 12:12 PM, Mr Flibble wrote:
> >>>>>>> On Sat, 10 Jul 2021 12:08:02 -0500
> >>>>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>>>
> >>>>>>>> The Halting Problem can only exist because
> >>>>>>>> of this same sort of pathological self-reference.
> >>>>>>>
> >>>>>>> ^ that is your mistake: the halting problem still exists even
> >>>>>>> if a collection of proofs have a mistake.
> >>>>>>>
> >>>>>>> Does [Turing 1937] rely on a decider being part of that which
> >>>>>>> is being decided? Wikipedia suggests not:
> >>>>>>>
> >>>>>>> "Turing's proof departs from calculation by recursive
> >>>>>>> functions and introduces the notion of computation by
> >>>>>>> machine."
> >>>>>>>
> >>>>>>> /Flibble
> >>>>>>>
> >>>>>>
> >>>>>> *I agree that I have not solved the halting problem*
> >>>>>> At most I have only proved that the conventional proofs of the
> >>>>>> undecidability of the halting problem that rely on the Strachey
> >>>>>> form, are incorrect. This seems to include all textbook
> >>>>>> proofs.
> >>>>>
> >>>>> You need to reign in the ego, mate, Strachey deserves the credit
> >>>>> not you unless you are claiming that you have independently
> >>>>> reached the same conclusion as Strachey without being aware of
> >>>>> Strachey until recently?
> >>>>>
> >>>>> /Flibble
> >>>>>
> >>>>
> >>>> All of the textbooks cite the Strachey form as proof that the
> >>>> halting problem is undecidable. Ben, Mike and Kaz agree that the
> >>>> Strachey form proves that the halting problem is undecidable.
> >>>>
> >>>> rec routine P
> >>>> §L:if T[P] go to L
> >>>> Return §
> >>>>
> >>>> If T[P] = True the routine P will loop, and it will
> >>>> only terminate if T[P] = False. In each case T[P] has
> >>>> exactly the wrong value, and this contradiction shows
> >>>> that the function T cannot exist.
> >>>>
> >>>> When Strachey says:
> >>>> "this contradiction shows that the function T cannot exist."
> >>>>
> >>>> He is saying that he just proved that a universal halt decider
> >>>> {function T} does not exist.
> >>>
> >>> No he isn't; he is saying that a decider can not be part of what
> >>> is being decided which is quite different.
> >>
> >> So when Strachey says:
> >> "this contradiction shows that the function T cannot exist."
> >>
> >> Strachey does not mean
> >> {this contradiction shows that the function T cannot exist.}
> >
> > He means T cannot decide on P if T is called from within P; i.e. the
> > "pathological self reference" you keep going on about.
> >
> > /Flibble
> >
>
> Yes and he and everyone else here besides you and I believes that
> this proves that the halting problem is undecidable.
When I read Strachey's letter I didn't get the impression that that was
his conclusion; merely that T cannot decide on P if called from within
P .. i.e. the "Impossible Program".

/Flibble

On 7/10/2021 2:14 PM, Mr Flibble wrote:
> On Sat, 10 Jul 2021 14:09:07 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 7/10/2021 1:59 PM, Mr Flibble wrote:
>>> On Sat, 10 Jul 2021 13:45:38 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 7/10/2021 1:38 PM, Mr Flibble wrote:
>>>>> On Sat, 10 Jul 2021 13:32:40 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>
>>>>>> On 7/10/2021 1:23 PM, Mr Flibble wrote:
>>>>>>> On Sat, 10 Jul 2021 13:06:35 -0500
>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>
>>>>>>>> On 7/10/2021 12:12 PM, Mr Flibble wrote:
>>>>>>>>> On Sat, 10 Jul 2021 12:08:02 -0500
>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>
>>>>>>>>>> The Halting Problem can only exist because
>>>>>>>>>> of this same sort of pathological self-reference.
>>>>>>>>>
>>>>>>>>> ^ that is your mistake: the halting problem still exists even
>>>>>>>>> if a collection of proofs have a mistake.
>>>>>>>>>
>>>>>>>>> Does [Turing 1937] rely on a decider being part of that which
>>>>>>>>> is being decided? Wikipedia suggests not:
>>>>>>>>>
>>>>>>>>> "Turing's proof departs from calculation by recursive
>>>>>>>>> functions and introduces the notion of computation by
>>>>>>>>> machine."
>>>>>>>>>
>>>>>>>>> /Flibble
>>>>>>>>>
>>>>>>>>
>>>>>>>> *I agree that I have not solved the halting problem*
>>>>>>>> At most I have only proved that the conventional proofs of the
>>>>>>>> undecidability of the halting problem that rely on the Strachey
>>>>>>>> form, are incorrect. This seems to include all textbook
>>>>>>>> proofs.
>>>>>>>
>>>>>>> You need to reign in the ego, mate, Strachey deserves the credit
>>>>>>> not you unless you are claiming that you have independently
>>>>>>> reached the same conclusion as Strachey without being aware of
>>>>>>> Strachey until recently?
>>>>>>>
>>>>>>> /Flibble
>>>>>>>
>>>>>>
>>>>>> All of the textbooks cite the Strachey form as proof that the
>>>>>> halting problem is undecidable. Ben, Mike and Kaz agree that the
>>>>>> Strachey form proves that the halting problem is undecidable.
>>>>>>
>>>>>> rec routine P
>>>>>> §L:if T[P] go to L
>>>>>> Return §
>>>>>>
>>>>>> If T[P] = True the routine P will loop, and it will
>>>>>> only terminate if T[P] = False. In each case T[P] has
>>>>>> exactly the wrong value, and this contradiction shows
>>>>>> that the function T cannot exist.
>>>>>>
>>>>>> When Strachey says:
>>>>>> "this contradiction shows that the function T cannot exist."
>>>>>>
>>>>>> He is saying that he just proved that a universal halt decider
>>>>>> {function T} does not exist.
>>>>>
>>>>> No he isn't; he is saying that a decider can not be part of what
>>>>> is being decided which is quite different.
>>>>
>>>> So when Strachey says:
>>>> "this contradiction shows that the function T cannot exist."
>>>>
>>>> Strachey does not mean
>>>> {this contradiction shows that the function T cannot exist.}
>>>
>>> He means T cannot decide on P if T is called from within P; i.e. the
>>> "pathological self reference" you keep going on about.
>>>
>>> /Flibble
>>>
>>
>> Yes and he and everyone else here besides you and I believes that
>> this proves that the halting problem is undecidable.
>
> When I read Strachey's letter I didn't get the impression that that was
> his conclusion; merely that T cannot decide on P if called from within
> P .. i.e. the "Impossible Program".
>
> /Flibble
>

None-the-less everyone else does get that impression.
All of the textbook halting problem undecidability proofs rely on the
Strachey form as their entire basis.

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

--
Copyright 2021 Pete Olcott

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

On Sat, 10 Jul 2021 14:32:10 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 7/10/2021 2:14 PM, Mr Flibble wrote:
> > On Sat, 10 Jul 2021 14:09:07 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >
> >> On 7/10/2021 1:59 PM, Mr Flibble wrote:
> >>> On Sat, 10 Jul 2021 13:45:38 -0500
> >>> olcott <NoOne@NoWhere.com> wrote:
> >>>
> >>>> On 7/10/2021 1:38 PM, Mr Flibble wrote:
> >>>>> On Sat, 10 Jul 2021 13:32:40 -0500
> >>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>
> >>>>>> On 7/10/2021 1:23 PM, Mr Flibble wrote:
> >>>>>>> On Sat, 10 Jul 2021 13:06:35 -0500
> >>>>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>>>
> >>>>>>>> On 7/10/2021 12:12 PM, Mr Flibble wrote:
> >>>>>>>>> On Sat, 10 Jul 2021 12:08:02 -0500
> >>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
> >>>>>>>>>
> >>>>>>>>>> The Halting Problem can only exist because
> >>>>>>>>>> of this same sort of pathological self-reference.
> >>>>>>>>>
> >>>>>>>>> ^ that is your mistake: the halting problem still exists
> >>>>>>>>> even if a collection of proofs have a mistake.
> >>>>>>>>>
> >>>>>>>>> Does [Turing 1937] rely on a decider being part of that
> >>>>>>>>> which is being decided? Wikipedia suggests not:
> >>>>>>>>>
> >>>>>>>>> "Turing's proof departs from calculation by recursive
> >>>>>>>>> functions and introduces the notion of computation by
> >>>>>>>>> machine."
> >>>>>>>>>
> >>>>>>>>> /Flibble
> >>>>>>>>>
> >>>>>>>>
> >>>>>>>> *I agree that I have not solved the halting problem*
> >>>>>>>> At most I have only proved that the conventional proofs of
> >>>>>>>> the undecidability of the halting problem that rely on the
> >>>>>>>> Strachey form, are incorrect. This seems to include all
> >>>>>>>> textbook proofs.
> >>>>>>>
> >>>>>>> You need to reign in the ego, mate, Strachey deserves the
> >>>>>>> credit not you unless you are claiming that you have
> >>>>>>> independently reached the same conclusion as Strachey without
> >>>>>>> being aware of Strachey until recently?
> >>>>>>>
> >>>>>>> /Flibble
> >>>>>>>
> >>>>>>
> >>>>>> All of the textbooks cite the Strachey form as proof that the
> >>>>>> halting problem is undecidable. Ben, Mike and Kaz agree that
> >>>>>> the Strachey form proves that the halting problem is
> >>>>>> undecidable.
> >>>>>>
> >>>>>> rec routine P
> >>>>>> §L:if T[P] go to L
> >>>>>> Return §
> >>>>>>
> >>>>>> If T[P] = True the routine P will loop, and it will
> >>>>>> only terminate if T[P] = False. In each case T[P] has
> >>>>>> exactly the wrong value, and this contradiction shows
> >>>>>> that the function T cannot exist.
> >>>>>>
> >>>>>> When Strachey says:
> >>>>>> "this contradiction shows that the function T cannot exist."
> >>>>>>
> >>>>>> He is saying that he just proved that a universal halt decider
> >>>>>> {function T} does not exist.
> >>>>>
> >>>>> No he isn't; he is saying that a decider can not be part of what
> >>>>> is being decided which is quite different.
> >>>>
> >>>> So when Strachey says:
> >>>> "this contradiction shows that the function T cannot exist."
> >>>>
> >>>> Strachey does not mean
> >>>> {this contradiction shows that the function T cannot exist.}
> >>>
> >>> He means T cannot decide on P if T is called from within P; i.e.
> >>> the "pathological self reference" you keep going on about.
> >>>
> >>> /Flibble
> >>>
> >>
> >> Yes and he and everyone else here besides you and I believes that
> >> this proves that the halting problem is undecidable.
> >
> > When I read Strachey's letter I didn't get the impression that that
> > was his conclusion; merely that T cannot decide on P if called from
> > within P .. i.e. the "Impossible Program".
> >
> > /Flibble
> >
>
> None-the-less everyone else does get that impression.
> All of the textbook halting problem undecidability proofs rely on the
> Strachey form as their entire basis.
>
> http://www.liarparadox.org/sipser_165.pdf
Then you might be on to something but you need to stop implying the
halting problem itself is not undecidable in your posts as it doesn't
help your case (and is the reason I have been dismissive of your posts
in the past).

/Flibble

On 7/10/2021 2:30 PM, Peter wrote:
> olcott wrote:
>> On 7/10/2021 12:12 PM, Mr Flibble wrote:
>>> On Sat, 10 Jul 2021 12:08:02 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> The Halting Problem can only exist because
>>>> of this same sort of pathological self-reference.
>>>
>>> ^ that is your mistake: the halting problem still exists even if a
>>> collection of proofs have a mistake.
>>>
>>> Does [Turing 1937] rely on a decider being part of that which is
>>> being decided?  Wikipedia suggests not:
>>>
>>> "Turing's proof departs from calculation by recursive functions and
>>> introduces the notion of computation by machine."
>>>
>>> /Flibble
>>>
>>
>> *I agree that I have not solved the halting problem*
>> At most I have only proved that the conventional proofs of the
>> undecidability of the halting problem that rely on the Strachey form,
>> are incorrect. This seems to include all textbook proofs.
>>
>> [An impossible program] C. Strachey
>> The Computer Journal, Volume 7, Issue 4, January 1965, Page 313,
>> https://doi.org/10.1093/comjnl/7.4.313
>>
>> Now seems to be a good time to finally look at the Turing proof.
>> https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
>> I am not sure if the above linked copy has the later published
>> correction.
>>
>> If the Turing proof is isomorphic to the Strachey form, I don't know
>> what it left to prove that the halting problem is undecidable.
>
> There is more than one proof.  I was taught, not the the halting problem
> for TMs is unsolvable, but that the halting problem for register
> machines is unsolvable.  The reason being, I suppose, that the course
> was taught by one of the inventors of the register machine.  [There are
> a variety of register machines, this one had an unlimited number of
> registers and the instructions

All of the proofs seem to boil down to this one idea:

An impossible program
C. Strachey
The Computer Journal, Volume 7, Issue 4, January 1965, Page 313,
https://doi.org/10.1093/comjnl/7.4.313

> add 1 to register R,
> subtract 1 from register R (so long as it doesn't hold 0),
> if R doesn't hold 0 go to instruction i.
> See Shepherdson & Sturgis, 'Computability of recursive functions',
> /JACM/, vol 10, no 2, 1963, pp217-255.]
>
>>
>> Goldbach's Conjecture is merely undecided and thus not undecidable.
>> https://en.wikipedia.org/wiki/Goldbach%27s_conjecture
>>
>> Busy Beaver only seems intractable not undecidable.
>> https://en.wikipedia.org/wiki/Busy_beaver
>>
>>
>>
>
>

--
Copyright 2021 Pete Olcott

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

On 7/10/2021 2:35 PM, Mr Flibble wrote:
> On Sat, 10 Jul 2021 14:32:10 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 7/10/2021 2:14 PM, Mr Flibble wrote:
>>> On Sat, 10 Jul 2021 14:09:07 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 7/10/2021 1:59 PM, Mr Flibble wrote:
>>>>> On Sat, 10 Jul 2021 13:45:38 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>
>>>>>> On 7/10/2021 1:38 PM, Mr Flibble wrote:
>>>>>>> On Sat, 10 Jul 2021 13:32:40 -0500
>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>
>>>>>>>> On 7/10/2021 1:23 PM, Mr Flibble wrote:
>>>>>>>>> On Sat, 10 Jul 2021 13:06:35 -0500
>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>
>>>>>>>>>> On 7/10/2021 12:12 PM, Mr Flibble wrote:
>>>>>>>>>>> On Sat, 10 Jul 2021 12:08:02 -0500
>>>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>>>
>>>>>>>>>>>> The Halting Problem can only exist because
>>>>>>>>>>>> of this same sort of pathological self-reference.
>>>>>>>>>>>
>>>>>>>>>>> ^ that is your mistake: the halting problem still exists
>>>>>>>>>>> even if a collection of proofs have a mistake.
>>>>>>>>>>>
>>>>>>>>>>> Does [Turing 1937] rely on a decider being part of that
>>>>>>>>>>> which is being decided? Wikipedia suggests not:
>>>>>>>>>>>
>>>>>>>>>>> "Turing's proof departs from calculation by recursive
>>>>>>>>>>> functions and introduces the notion of computation by
>>>>>>>>>>> machine."
>>>>>>>>>>>
>>>>>>>>>>> /Flibble
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> *I agree that I have not solved the halting problem*
>>>>>>>>>> At most I have only proved that the conventional proofs of
>>>>>>>>>> the undecidability of the halting problem that rely on the
>>>>>>>>>> Strachey form, are incorrect. This seems to include all
>>>>>>>>>> textbook proofs.
>>>>>>>>>
>>>>>>>>> You need to reign in the ego, mate, Strachey deserves the
>>>>>>>>> credit not you unless you are claiming that you have
>>>>>>>>> independently reached the same conclusion as Strachey without
>>>>>>>>> being aware of Strachey until recently?
>>>>>>>>>
>>>>>>>>> /Flibble
>>>>>>>>>
>>>>>>>>
>>>>>>>> All of the textbooks cite the Strachey form as proof that the
>>>>>>>> halting problem is undecidable. Ben, Mike and Kaz agree that
>>>>>>>> the Strachey form proves that the halting problem is
>>>>>>>> undecidable.
>>>>>>>>
>>>>>>>> rec routine P
>>>>>>>> §L:if T[P] go to L
>>>>>>>> Return §
>>>>>>>>
>>>>>>>> If T[P] = True the routine P will loop, and it will
>>>>>>>> only terminate if T[P] = False. In each case T[P] has
>>>>>>>> exactly the wrong value, and this contradiction shows
>>>>>>>> that the function T cannot exist.
>>>>>>>>
>>>>>>>> When Strachey says:
>>>>>>>> "this contradiction shows that the function T cannot exist."
>>>>>>>>
>>>>>>>> He is saying that he just proved that a universal halt decider
>>>>>>>> {function T} does not exist.
>>>>>>>
>>>>>>> No he isn't; he is saying that a decider can not be part of what
>>>>>>> is being decided which is quite different.
>>>>>>
>>>>>> So when Strachey says:
>>>>>> "this contradiction shows that the function T cannot exist."
>>>>>>
>>>>>> Strachey does not mean
>>>>>> {this contradiction shows that the function T cannot exist.}
>>>>>
>>>>> He means T cannot decide on P if T is called from within P; i.e.
>>>>> the "pathological self reference" you keep going on about.
>>>>>
>>>>> /Flibble
>>>>>
>>>>
>>>> Yes and he and everyone else here besides you and I believes that
>>>> this proves that the halting problem is undecidable.
>>>
>>> When I read Strachey's letter I didn't get the impression that that
>>> was his conclusion; merely that T cannot decide on P if called from
>>> within P .. i.e. the "Impossible Program".
>>>
>>> /Flibble
>>>
>>
>> None-the-less everyone else does get that impression.
>> All of the textbook halting problem undecidability proofs rely on the
>> Strachey form as their entire basis.
>>
>> http://www.liarparadox.org/sipser_165.pdf
>
> Then you might be on to something but you need to stop implying the
> halting problem itself is not undecidable in your posts as it doesn't
> help your case (and is the reason I have been dismissive of your posts
> in the past).
>
> /Flibble
>

Like I already explained in much more words with many more key details,
if none of these conventional (Strachey based) undecidability proofs are
correct then that doesn't seem to leave any other proof of halting
undecidability:

Goldbach's Conjecture is merely undecided and thus not undecidable.
https://en.wikipedia.org/wiki/Goldbach%27s_conjecture

Busy Beaver only seems intractable thus not undecidable.
https://en.wikipedia.org/wiki/Busy_beaver

It is probably a good time for me to take a first look at the actual
Turing proof. I merely need to verify that it is isomorphic to the
Strachey form.

--
Copyright 2021 Pete Olcott

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

On 7/10/2021 4:39 PM, Mr Flibble wrote:
> On Sat, 10 Jul 2021 16:12:12 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 7/10/2021 2:35 PM, Mr Flibble wrote:
>>> On Sat, 10 Jul 2021 14:32:10 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 7/10/2021 2:14 PM, Mr Flibble wrote:
>>>>> On Sat, 10 Jul 2021 14:09:07 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>
>>>>>> On 7/10/2021 1:59 PM, Mr Flibble wrote:
>>>>>>> On Sat, 10 Jul 2021 13:45:38 -0500
>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>
>>>>>>>> On 7/10/2021 1:38 PM, Mr Flibble wrote:
>>>>>>>>> On Sat, 10 Jul 2021 13:32:40 -0500
>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>
>>>>>>>>>> On 7/10/2021 1:23 PM, Mr Flibble wrote:
>>>>>>>>>>> On Sat, 10 Jul 2021 13:06:35 -0500
>>>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>>>
>>>>>>>>>>>> On 7/10/2021 12:12 PM, Mr Flibble wrote:
>>>>>>>>>>>>> On Sat, 10 Jul 2021 12:08:02 -0500
>>>>>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> The Halting Problem can only exist because
>>>>>>>>>>>>>> of this same sort of pathological self-reference.
>>>>>>>>>>>>>
>>>>>>>>>>>>> ^ that is your mistake: the halting problem still exists
>>>>>>>>>>>>> even if a collection of proofs have a mistake.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Does [Turing 1937] rely on a decider being part of that
>>>>>>>>>>>>> which is being decided? Wikipedia suggests not:
>>>>>>>>>>>>>
>>>>>>>>>>>>> "Turing's proof departs from calculation by recursive
>>>>>>>>>>>>> functions and introduces the notion of computation by
>>>>>>>>>>>>> machine."
>>>>>>>>>>>>>
>>>>>>>>>>>>> /Flibble
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> *I agree that I have not solved the halting problem*
>>>>>>>>>>>> At most I have only proved that the conventional proofs of
>>>>>>>>>>>> the undecidability of the halting problem that rely on the
>>>>>>>>>>>> Strachey form, are incorrect. This seems to include all
>>>>>>>>>>>> textbook proofs.
>>>>>>>>>>>
>>>>>>>>>>> You need to reign in the ego, mate, Strachey deserves the
>>>>>>>>>>> credit not you unless you are claiming that you have
>>>>>>>>>>> independently reached the same conclusion as Strachey
>>>>>>>>>>> without being aware of Strachey until recently?
>>>>>>>>>>>
>>>>>>>>>>> /Flibble
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> All of the textbooks cite the Strachey form as proof that the
>>>>>>>>>> halting problem is undecidable. Ben, Mike and Kaz agree that
>>>>>>>>>> the Strachey form proves that the halting problem is
>>>>>>>>>> undecidable.
>>>>>>>>>>
>>>>>>>>>> rec routine P
>>>>>>>>>> §L:if T[P] go to L
>>>>>>>>>> Return §
>>>>>>>>>>
>>>>>>>>>> If T[P] = True the routine P will loop, and it will
>>>>>>>>>> only terminate if T[P] = False. In each case T[P] has
>>>>>>>>>> exactly the wrong value, and this contradiction shows
>>>>>>>>>> that the function T cannot exist.
>>>>>>>>>>
>>>>>>>>>> When Strachey says:
>>>>>>>>>> "this contradiction shows that the function T cannot exist."
>>>>>>>>>>
>>>>>>>>>> He is saying that he just proved that a universal halt
>>>>>>>>>> decider {function T} does not exist.
>>>>>>>>>
>>>>>>>>> No he isn't; he is saying that a decider can not be part of
>>>>>>>>> what is being decided which is quite different.
>>>>>>>>
>>>>>>>> So when Strachey says:
>>>>>>>> "this contradiction shows that the function T cannot exist."
>>>>>>>>
>>>>>>>> Strachey does not mean
>>>>>>>> {this contradiction shows that the function T cannot exist.}
>>>>>>>
>>>>>>> He means T cannot decide on P if T is called from within P; i.e.
>>>>>>> the "pathological self reference" you keep going on about.
>>>>>>>
>>>>>>> /Flibble
>>>>>>>
>>>>>>
>>>>>> Yes and he and everyone else here besides you and I believes that
>>>>>> this proves that the halting problem is undecidable.
>>>>>
>>>>> When I read Strachey's letter I didn't get the impression that
>>>>> that was his conclusion; merely that T cannot decide on P if
>>>>> called from within P .. i.e. the "Impossible Program".
>>>>>
>>>>> /Flibble
>>>>>
>>>>
>>>> None-the-less everyone else does get that impression.
>>>> All of the textbook halting problem undecidability proofs rely on
>>>> the Strachey form as their entire basis.
>>>>
>>>> http://www.liarparadox.org/sipser_165.pdf
>>>
>>> Then you might be on to something but you need to stop implying the
>>> halting problem itself is not undecidable in your posts as it
>>> doesn't help your case (and is the reason I have been dismissive of
>>> your posts in the past).
>>>
>>> /Flibble
>>>
>>
>> Like I already explained in much more words with many more key
>> details, if none of these conventional (Strachey based)
>> undecidability proofs are correct then that doesn't seem to leave any
>> other proof of halting undecidability:
>>
>> Goldbach's Conjecture is merely undecided and thus not undecidable.
>> https://en.wikipedia.org/wiki/Goldbach%27s_conjecture
>>
>> Busy Beaver only seems intractable thus not undecidable.
>> https://en.wikipedia.org/wiki/Busy_beaver
>>
>> It is probably a good time for me to take a first look at the actual
>> Turing proof. I merely need to verify that it is isomorphic to the
>> Strachey form.
>
> You are still missing the point: even if [Turing 1937] has the same
> mistake you still cannot prove that the halting problem itself is not
> undecidable just because that particular proof is invalid.
>
> /Flibble
>

None-the-less once the halting problem is no longer provably undecidable
computation loses its definite limits.

The key other aspect of this is that the Tarski undefinability theorem
can be understood to fail for the same reason that the halting theorem
fails.

This can have an explosive effect on AI research. Davidson's truth
conditional semantics can finally be anchored in a formal mathematical
notion of truth.

--
Copyright 2021 Pete Olcott

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

On 7/10/2021 4:52 PM, Mr Flibble wrote:
> On Sat, 10 Jul 2021 16:46:28 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 7/10/2021 4:39 PM, Mr Flibble wrote:
>>> On Sat, 10 Jul 2021 16:12:12 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 7/10/2021 2:35 PM, Mr Flibble wrote:
>>>>> On Sat, 10 Jul 2021 14:32:10 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>
>>>>>> On 7/10/2021 2:14 PM, Mr Flibble wrote:
>>>>>>> On Sat, 10 Jul 2021 14:09:07 -0500
>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>
>>>>>>>> On 7/10/2021 1:59 PM, Mr Flibble wrote:
>>>>>>>>> On Sat, 10 Jul 2021 13:45:38 -0500
>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>
>>>>>>>>>> On 7/10/2021 1:38 PM, Mr Flibble wrote:
>>>>>>>>>>> On Sat, 10 Jul 2021 13:32:40 -0500
>>>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>>>
>>>>>>>>>>>> On 7/10/2021 1:23 PM, Mr Flibble wrote:
>>>>>>>>>>>>> On Sat, 10 Jul 2021 13:06:35 -0500
>>>>>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> On 7/10/2021 12:12 PM, Mr Flibble wrote:
>>>>>>>>>>>>>>> On Sat, 10 Jul 2021 12:08:02 -0500
>>>>>>>>>>>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> The Halting Problem can only exist because
>>>>>>>>>>>>>>>> of this same sort of pathological self-reference.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> ^ that is your mistake: the halting problem still exists
>>>>>>>>>>>>>>> even if a collection of proofs have a mistake.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Does [Turing 1937] rely on a decider being part of that
>>>>>>>>>>>>>>> which is being decided? Wikipedia suggests not:
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> "Turing's proof departs from calculation by recursive
>>>>>>>>>>>>>>> functions and introduces the notion of computation by
>>>>>>>>>>>>>>> machine."
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> /Flibble
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> *I agree that I have not solved the halting problem*
>>>>>>>>>>>>>> At most I have only proved that the conventional proofs
>>>>>>>>>>>>>> of the undecidability of the halting problem that rely
>>>>>>>>>>>>>> on the Strachey form, are incorrect. This seems to
>>>>>>>>>>>>>> include all textbook proofs.
>>>>>>>>>>>>>
>>>>>>>>>>>>> You need to reign in the ego, mate, Strachey deserves the
>>>>>>>>>>>>> credit not you unless you are claiming that you have
>>>>>>>>>>>>> independently reached the same conclusion as Strachey
>>>>>>>>>>>>> without being aware of Strachey until recently?
>>>>>>>>>>>>>
>>>>>>>>>>>>> /Flibble
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> All of the textbooks cite the Strachey form as proof that
>>>>>>>>>>>> the halting problem is undecidable. Ben, Mike and Kaz
>>>>>>>>>>>> agree that the Strachey form proves that the halting
>>>>>>>>>>>> problem is undecidable.
>>>>>>>>>>>>
>>>>>>>>>>>> rec routine P
>>>>>>>>>>>> §L:if T[P] go to L
>>>>>>>>>>>> Return §
>>>>>>>>>>>>
>>>>>>>>>>>> If T[P] = True the routine P will loop, and it will
>>>>>>>>>>>> only terminate if T[P] = False. In each case T[P] has
>>>>>>>>>>>> exactly the wrong value, and this contradiction shows
>>>>>>>>>>>> that the function T cannot exist.
>>>>>>>>>>>>
>>>>>>>>>>>> When Strachey says:
>>>>>>>>>>>> "this contradiction shows that the function T cannot
>>>>>>>>>>>> exist."
>>>>>>>>>>>>
>>>>>>>>>>>> He is saying that he just proved that a universal halt
>>>>>>>>>>>> decider {function T} does not exist.
>>>>>>>>>>>
>>>>>>>>>>> No he isn't; he is saying that a decider can not be part of
>>>>>>>>>>> what is being decided which is quite different.
>>>>>>>>>>
>>>>>>>>>> So when Strachey says:
>>>>>>>>>> "this contradiction shows that the function T cannot exist."
>>>>>>>>>>
>>>>>>>>>> Strachey does not mean
>>>>>>>>>> {this contradiction shows that the function T cannot exist.}
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> He means T cannot decide on P if T is called from within P;
>>>>>>>>> i.e. the "pathological self reference" you keep going on
>>>>>>>>> about.
>>>>>>>>>
>>>>>>>>> /Flibble
>>>>>>>>>
>>>>>>>>
>>>>>>>> Yes and he and everyone else here besides you and I believes
>>>>>>>> that this proves that the halting problem is undecidable.
>>>>>>>
>>>>>>> When I read Strachey's letter I didn't get the impression that
>>>>>>> that was his conclusion; merely that T cannot decide on P if
>>>>>>> called from within P .. i.e. the "Impossible Program".
>>>>>>>
>>>>>>> /Flibble
>>>>>>>
>>>>>>
>>>>>> None-the-less everyone else does get that impression.
>>>>>> All of the textbook halting problem undecidability proofs rely on
>>>>>> the Strachey form as their entire basis.
>>>>>>
>>>>>> http://www.liarparadox.org/sipser_165.pdf
>>>>>
>>>>> Then you might be on to something but you need to stop implying
>>>>> the halting problem itself is not undecidable in your posts as it
>>>>> doesn't help your case (and is the reason I have been dismissive
>>>>> of your posts in the past).
>>>>>
>>>>> /Flibble
>>>>>
>>>>
>>>> Like I already explained in much more words with many more key
>>>> details, if none of these conventional (Strachey based)
>>>> undecidability proofs are correct then that doesn't seem to leave
>>>> any other proof of halting undecidability:
>>>>
>>>> Goldbach's Conjecture is merely undecided and thus not undecidable.
>>>> https://en.wikipedia.org/wiki/Goldbach%27s_conjecture
>>>>
>>>> Busy Beaver only seems intractable thus not undecidable.
>>>> https://en.wikipedia.org/wiki/Busy_beaver
>>>>
>>>> It is probably a good time for me to take a first look at the
>>>> actual Turing proof. I merely need to verify that it is isomorphic
>>>> to the Strachey form.
>>>
>>> You are still missing the point: even if [Turing 1937] has the same
>>> mistake you still cannot prove that the halting problem itself is
>>> not undecidable just because that particular proof is invalid.
>>>
>>> /Flibble
>>>
>>
>> None-the-less once the halting problem is no longer provably
>> undecidable computation loses its definite limits.
>
> No, a lack of a proof showing that the halting problem is undecidable
> does NOT imply that the halting problem is not undecidable; that still
> needs to be proven.
>
> [snip]
>
> /Flibble
>