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-16 15:46 +0100
Organization	A noiseless patient Spider
Message-ID	<87pmviqpte.fsf@bsb.me.uk> (permalink)
References	<20210716142416.00003996@reddwarf.jmc> <871r7ys7pd.fsf@bsb.me.uk> <20210716143926.000052ae@reddwarf.jmc> <N4adnczkJ__DBGz9nZ2dnUU7-WnNnZ2d@giganews.com>

Show all headers | View raw

olcott <NoOne@NoWhere.com> writes:

> 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.
>
> https://en.wikipedia.org/wiki/Recursive_language

I wonder why you think that's helpful.  Neither Flibble nor I was using
it in that sense.  That sense is simply not applicable to either of our
posts.

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