XPost: comp.theory, comp.ai.philosophy, comp.software-eng
From: flibble@reddwarf.jmc
On Fri, 16 Jul 2021 09:36:15 -0500
olcott wrote:
> On 7/16/2021 8:39 AM, Mr Flibble wrote:
> > On Fri, 16 Jul 2021 14:34:54 +0100
> > Ben Bacarisse wrote:
> >
> >> Mr Flibble 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
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
