Re: Halting Problem proofs appear to be bogus!

From	Mr Flibble <flibble@reddwarf.jmc>
Newsgroups	comp.theory
Subject	Re: Halting Problem proofs appear to be bogus!
Message-ID	<20210716154219.00004cba@reddwarf.jmc> (permalink)
References	<20210716142416.00003996@reddwarf.jmc> <871r7ys7pd.fsf@bsb.me.uk> <20210716143926.000052ae@reddwarf.jmc> <87v95aqq3o.fsf@bsb.me.uk>
Organization	Jupiter Mining Corp
Date	2021-07-16 15:42 +0100

Show all headers | View raw

On Fri, 16 Jul 2021 15:40:27 +0100
Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:

> Mr Flibble <flibble@reddwarf.jmc> writes:
> 
> > 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).  
> 
> No.  T[P] /might/ be recursive, but then again it might not be.  Any
> argument based on the blank assumption that T[P] is recursive is
> flawed.  T must be permitted to make it decision based on the widest
> possible use of it's argument or the sketch is pointlessly
> restrictive.

No. It is recursive.

[snip]

/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