Re: Halting Problem proofs appear to be bogus!

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.theory
Subject	Re: Halting Problem proofs appear to be bogus!
Date	2021-07-17 01:06 +0100
Organization	A noiseless patient Spider
Message-ID	<87mtqlolc4.fsf@bsb.me.uk> (permalink)
References	<20210716142416.00003996@reddwarf.jmc> <871r7ys7pd.fsf@bsb.me.uk> <20210716143926.000052ae@reddwarf.jmc> <87v95aqq3o.fsf@bsb.me.uk> <20210716154219.00004cba@reddwarf.jmc>

Show all headers | View raw

Mr Flibble <flibble@reddwarf.jmc> writes:

> 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.

I suppose if anyone else is reading this, they will just have to pick a
side!

-- 
Ben.

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