Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: Halting Problem proofs appear to be bogus! |
| Date | 2021-07-16 14:34 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <871r7ys7pd.fsf@bsb.me.uk> (permalink) |
| References | <20210716142416.00003996@reddwarf.jmc> |
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? Further, this argument must fail for any of the actual proofs that are based on Turing machine because TMs have not functions, not calls and no recursion. -- Ben.
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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