Re: Halting Problem proofs appear to be bogus!

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.

Show all headers | View raw

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

Thread

Halting Problem proofs appear to be bogus! Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 14:24 +0100
  Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 14:34 +0100
    Re: Halting Problem proofs appear to be bogus! Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 14:39 +0100
      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! wij <wyniijj@gmail.com> - 2021-07-16 08:38 -0700
            Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 11:04 -0500
              Re: Halting Problem proofs appear to be bogus! wij <wyniijj@gmail.com> - 2021-07-16 09:25 -0700
                Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 12:03 -0500
                Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 19:50 +0100
        Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 15:46 +0100
      Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 15:40 +0100
        Re: Halting Problem proofs appear to be bogus! Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 15:42 +0100
          Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-17 01:06 +0100
            Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-17 10:52 -0500
      Re: Halting Problem proofs appear to be bogus! Andy Walker <anw@cuboid.co.uk> - 2021-07-16 16:12 +0100
        Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 10:52 -0500
          Re: Halting Problem proofs appear to be bogus! wij <wyniijj@gmail.com> - 2021-07-16 09:11 -0700
            Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 11:15 -0500
    Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 09:13 -0500
      Re: Halting Problem proofs appear to be bogus! wij <wyniijj@gmail.com> - 2021-07-16 08:32 -0700
      Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-17 01:03 +0100
        Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-17 10:46 -0500
          Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-18 02:32 +0100
            Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-19 10:10 -0500
              Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-20 01:35 +0100
                Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-20 09:24 -0500
                Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-21 01:28 +0100
              Re: Halting Problem proofs appear to be bogus! Richard Damon <Richard@Damon-Family.org> - 2021-07-19 20:48 -0700
  Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-16 15:27 +0100
    Re: Halting Problem proofs appear to be bogus! Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 15:36 +0100
      Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 10:02 -0500
        Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-16 22:09 +0100
      Re: Halting Problem proofs appear to be bogus! wij <wyniijj@gmail.com> - 2021-07-16 08:46 -0700
      Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-16 22:07 +0100
        Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 16:20 -0500
          Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-16 22:25 +0100
            Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 16:32 -0500
              Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-17 11:48 +0100
    Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 09:44 -0500
      Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-16 22:10 +0100
  Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 09:32 -0500

csiph-web