On 7/16/2021 8:39 AM, Mr Flibble wrote:
> On Fri, 16 Jul 2021 14:34:54 +0100
> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>
>> Mr Flibble <flibble@reddwarf.jmc> writes:
>>
>>> All extant halting problem proofs appear to be predicated on a
>>> misunderstanding of the following contradiction:
>>
>> I don't think you've read any actual proofs, let along all of them.
>> Why you would even say such a thing?
>>
>>> Suppose T[R] is a Boolean function taking a routine
>>> (or program) R with no formal or free variables as its
>>> argument and that for all R, T[R] — True if R terminates
>>> if run and that T[R] = False if R does not terminate.
>>> Consider the routine P defined as follows
>>>
>>> rec routine P
>>> §L :if T[P] goto 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.
>>>
>>> [Strachey 1965]
>>>
>>> T is indeed unable to decide P but for the wrong reason: T[P] is
>>> recursive
>>
>> T[P] is not recursive. Maybe you don't understand what the CPL means?
>
> Of course it is recursive, such is obvious even to the casual reader
> who is unfamiliar with the CPL language (a clue: read the paragraph
> before the definition of P again).
>

"Recursive" has a very different meaning in computer science than it
does in software engineering.

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

>>
>> Further, this argument must fail for any of the actual proofs that are
>> based on Turing machine because TMs have not functions, not calls and
>> no recursion.
>
> Depends on whether or not there is an isomorphic equivalence.
>
> /Flibble
>
>

--
Copyright 2021 Pete Olcott

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

On Fri, 16 Jul 2021 09:36:15 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 7/16/2021 8:39 AM, Mr Flibble wrote:
> > On Fri, 16 Jul 2021 14:34:54 +0100
> > Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> >
> >> Mr Flibble <flibble@reddwarf.jmc> writes:
> >>
> >>> All extant halting problem proofs appear to be predicated on a
> >>> misunderstanding of the following contradiction:
> >>
> >> I don't think you've read any actual proofs, let along all of them.
> >> Why you would even say such a thing?
> >>
> >>> Suppose T[R] is a Boolean function taking a routine
> >>> (or program) R with no formal or free variables as its
> >>> argument and that for all R, T[R] — True if R terminates
> >>> if run and that T[R] = False if R does not terminate.
> >>> Consider the routine P defined as follows
> >>>
> >>> rec routine P
> >>> §L :if T[P] goto 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.
> >>>
> >>> [Strachey 1965]
> >>>
> >>> T is indeed unable to decide P but for the wrong reason: T[P] is
> >>> recursive
> >>
> >> T[P] is not recursive. Maybe you don't understand what the CPL
> >> means?
> >
> > Of course it is recursive, such is obvious even to the casual reader
> > who is unfamiliar with the CPL language (a clue: read the paragraph
> > before the definition of P again).
> >
>
> "Recursive" has a very different meaning in computer science than it
> does in software engineering.

By "recursion" I am referring to a function that calls itself either
directly or indirectly; in the case of [Strachey 1965] the recursion is
indirect:

T[P] -> P -> T[P] -> P -> T[P] ... ...

/Flibble

On 7/16/2021 10:38 AM, wij wrote:
> On Friday, 16 July 2021 at 22:39:59 UTC+8, Mr Flibble wrote:
>> On Fri, 16 Jul 2021 09:36:15 -0500
>> olcott <No...@NoWhere.com> wrote:
>>
>>> On 7/16/2021 8:39 AM, Mr Flibble wrote:
>>>> On Fri, 16 Jul 2021 14:34:54 +0100
>>>> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>>>>
>>>>> Mr Flibble <fli...@reddwarf.jmc> writes:
>>>>>
>>>>>> All extant halting problem proofs appear to be predicated on a
>>>>>> misunderstanding of the following contradiction:
>>>>>
>>>>> I don't think you've read any actual proofs, let along all of them.
>>>>> Why you would even say such a thing?
>>>>>
>>>>>> Suppose T[R] is a Boolean function taking a routine
>>>>>> (or program) R with no formal or free variables as its
>>>>>> argument and that for all R, T[R] — True if R terminates
>>>>>> if run and that T[R] = False if R does not terminate.
>>>>>> Consider the routine P defined as follows
>>>>>>
>>>>>> rec routine P
>>>>>> §L :if T[P] goto 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.
>>>>>>
>>>>>> [Strachey 1965]
>>>>>>
>>>>>> T is indeed unable to decide P but for the wrong reason: T[P] is
>>>>>> recursive
>>>>>
>>>>> T[P] is not recursive. Maybe you don't understand what the CPL
>>>>> means?
>>>>
>>>> Of course it is recursive, such is obvious even to the casual reader
>>>> who is unfamiliar with the CPL language (a clue: read the paragraph
>>>> before the definition of P again).
>>>>
>>>
>>> "Recursive" has a very different meaning in computer science than it
>>> does in software engineering.
>> By "recursion" I am referring to a function that calls itself either
>> directly or indirectly; in the case of [Strachey 1965] the recursion is
>> indirect:
>>
>> T[P] -> P -> T[P] -> P -> T[P] ... ...
>>
>> /Flibble
>
> // program P.c
> //-------------------
> void P();
>
> inline bool H(Func p) {
> // Rewrite H here.
> // The rewrite can be in very different but functionally equivalent ways (isomorphic).
> }
>
> void P() {
> if(H(P)) {
> for(;;) {}; // If H(P)==true, P is in infinite loop.
> }
> };
>
> If there is high-level "recursive call" it is made within H itself (may be your T), nothing to
> do with P. And this is why "undecidable" is called, H will not halt.
>

#include <stdint.h>
#define u32 uint32_t

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

Since there is no such actual thing as Func p that is currently fully
elaborated yet there is such as thing as the machine address of the
machine language code of the C function P mine can be fully understood
whereas your leaves out to many details.

In my system H is written in C returns u32 and is based on a full x86
emulator:

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

--
Copyright 2021 Pete Olcott

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