Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #3125
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Newsgroups | comp.theory, comp.ai.philosophy, comp.software-eng, sci.math.symbolic |
| Subject | Re: Halting Problem proofs appear to be bogus! |
| Message-ID | <20210716153956.0000250e@reddwarf.jmc> (permalink) |
| References | <20210716142416.00003996@reddwarf.jmc> <871r7ys7pd.fsf@bsb.me.uk> <20210716143926.000052ae@reddwarf.jmc> <N4adnczkJ__DBGz9nZ2dnUU7-WnNnZ2d@giganews.com> |
| Organization | Jupiter Mining Corp |
| Date | 2021-07-16 15:39 +0100 |
Cross-posted to 4 groups.
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
Back to comp.software-eng | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 09:36 -0500
Re: Halting Problem proofs appear to be bogus! Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 15:39 +0100
Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 11:04 -0500
csiph-web