Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | sci.logic, comp.theory |
| Subject | Re: What is the deal with the Halting Theorem? |
| Date | 2018-02-10 16:32 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <87sha8n695.fsf@bsb.me.uk> (permalink) |
| References | <p5ldr4$i7$1@dont-email.me> <1a665018-d02a-4b71-be09-ce46310610bd@googlegroups.com> <jMidnYuO7KkVl-LHnZ2dnUU7-fWdnZ2d@giganews.com> |
Cross-posted to 2 groups.
Pete Olcott <Pete@NoEmail.address> writes: > On 2/10/2018 2:15 AM, grahamcooper7@gmail.com wrote: >> On Saturday, February 10, 2018 at 10:19:52 AM UTC+10, Newberry wrote: >>> For every decider we can construct a "counter-example", i.e. a program >>> constructed from the decider such that it will do the opposite of what >>> the decider says. So there is no universal decider, right? Right, but >>> there is s decider that can prove that it cannot prove that the >>> counter-example halts. [It cannot prove that the counter-example does >>> not halt.] In fact I claim that there exists a decider that can >>> dichotomize the entire space of programs: either it can prove that P >>> halts on q, or it can prove that it cannot prove that P halts on q. >>> >>> I am 80% sure I am right. Prove me wrong. >> >> >> That's fuzzy logic! >> >> Halt Loop Neither >> >> >> but TMs are ENUMERABLE and DETERMINISTIC >> > > Definition of Turing Machine H (state transition sequence) > H.q0 Wm W ⊢* H.qy > H.q0 Wm W ⊢* H.qn This is not a definition of TM. And without extra annotation it is not even a specification for what H should do. How may times must yo ube told? The notation is not hard and you are using in key places so you keep saying things you don't mean to say. > Definition of Turing Machine Ĥx (state transition sequence) > Ĥx.q0 Wm ⊢* Ĥx.qx Wm Wm ⊢* Ĥx.qy // NO LOOP > Ĥx.q0 Wm ⊢* Ĥx.qx Wm Wm ⊢* Ĥx.qn // NO LOOP HERE EITHER > > H [Ĥx] [Ĥx] I will take you literally from now on, since you have not taken my advice to learn the notation and to specify the actual behaviour of H. > It is not fuzzy logic at all the above specified evaluation sequence > is precisely defined in the language of Turing Machine Descriptions > from the initial finite strings to the syntactic logical consequence > of Ĥx.qy or Ĥx.qn. Indeed. It is precisely defined by a definition you know (almost) nothing about. Almost anything you now go on to say about any machine in the H class actually does will be wrong. > The first few steps after qx are necessarily specified thus > Ben was wrong that they are not specified. You lie again. Please quote me where I say that (if I did, I want to correct the record). I said you don't know what any machine in the H class actually does or how it does it. For any one machine in that class, something defines what and how it behaves but you don't know (and there may be infinitely many possibilities). I suspect this is linked to the nonsense above where you say that the notation you are misusing defines TM. > A TM can only decide > halting on the basis of tracing what the entire state transition > sequence of the TMD would be up to the point that this TMD halts > or demonstrates non-halting behavior. If this is a metaphor (and you've hedged your bets here by saying that the decider need not actually simulate the trace) then you are just saying that a decider must make the correct decision -- by working out, somehow, what then execution trace would be. It must transition to qy or qn based on what the input TM would do, and that is all. But so what? We all knew that from the start. Oddly, having said that it need not actually simulate the trace you then deny the one thing you /do/ know that it does -- transition to qy or qn. You manage to pack an extraordinary density of mistakes into very short posts. > I prove that right here: > http://www.liarparadox.org/H_evaluates_S.pdf > The necessary evaluation sequence of H [S] "ENN" proves that H > must trace every single state transition of [S] up to the point > where S halts or demonstrates non halting behavior. You have proved nothing here. Sadly, the web allows any old rubbish to be published unchallenged, but with luck, hapless students who might find you writings know that. At least on the blog, the errors don't bother me. By the way, do you have permission to copy the illustrations form Linz's book, or is it's covered by fair use? At least one post seemed to be using them. > You have to actually carefully study what I am saying to understand > what I am saying. Simply presuming that what I am saying because you > have seen it all before will not work. Yes. Something we agree on. -- Ben.
Back to sci.logic | Previous | Next — Previous in thread | Find similar | Unroll thread
What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-09 16:19 -0800
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 02:05 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-10 00:31 -0600
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 12:19 +0000
Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-10 18:26 -0800
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-12 09:19 -0800
Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-10 00:15 -0800
Re: What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-10 06:49 -0800
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 18:23 +0000
Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-10 15:37 -0800
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-12 09:16 -0800
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-12 17:40 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-12 20:48 -0600
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-13 04:46 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-13 14:16 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-13 20:46 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-13 19:26 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 13:54 +0000
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-14 15:24 +0000
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-14 00:21 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-13 19:36 -0600
Re: What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-13 18:05 -0800
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-13 22:12 -0600
Re: What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-13 21:10 -0800
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-13 21:35 -0800
Re: What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-13 23:36 -0800
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 14:54 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 09:00 -0600
Re: What is the deal with the Halting Theorem? Newberry <newberryxy@gmail.com> - 2018-02-14 08:29 -0800
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 10:46 -0600
Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-14 21:37 -0800
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-14 21:49 -0800
Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-16 11:52 -0800
Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-16 11:54 -0800
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 12:52 -0800
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 14:05 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-15 07:02 -0800
Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-15 07:09 -0800
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 10:41 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 15:20 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 10:56 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 17:05 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 11:29 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 17:35 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 11:55 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 13:44 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 07:21 -0800
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-16 15:39 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 09:08 -0800
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 17:25 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-16 11:38 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 17:49 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-16 12:03 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 18:23 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 10:33 -0800
Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-16 16:49 -0800
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-16 18:20 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 10:28 -0800
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 18:55 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 12:46 -0800
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-16 20:53 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-16 13:36 -0800
Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-28 13:22 -0800
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-28 15:46 -0600
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-16 20:44 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-16 15:53 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 17:29 +0000
Re: What is the deal with the Halting Theorem? Jim Burns <james.g.burns@att.net> - 2018-02-14 08:42 -0500
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 09:35 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 20:14 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 17:10 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 13:39 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-15 06:47 -0800
Re: What is the deal with the Halting Theorem? Jim Burns <james.g.burns@att.net> - 2018-02-14 20:55 -0500
Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-14 08:27 -0800
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 14:52 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 09:47 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 20:12 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 17:05 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 13:53 +0000
Re: What is the deal with the Halting Theorem? peteolcott <peterolcott2@gmail.com> - 2018-02-15 06:51 -0800
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 15:16 +0000
Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-15 08:36 -0800
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 11:14 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 17:19 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-15 10:43 -0600
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-15 16:57 +0000
Re: What is the deal with the Halting Theorem? bursejan@gmail.com - 2018-02-15 09:24 -0800
Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-16 11:58 -0800
Re: What is the deal with the Halting Theorem? George Greene <greeneg@email.unc.edu> - 2018-02-14 21:33 -0800
Re: What is the deal with the Halting Theorem? Peter Percival <peterxpercival@hotmail.com> - 2018-02-14 14:45 +0000
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-14 02:24 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-13 22:18 -0600
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-14 05:32 +0000
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-14 00:30 -0600
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-14 14:07 +0000
Re: What is the deal with the Halting Theorem? grahamcooper7@gmail.com - 2018-02-13 18:04 -0800
Re: What is the deal with the Halting Theorem? Pete Olcott <Pete@NoEmail.address> - 2018-02-10 09:06 -0600
Re: What is the deal with the Halting Theorem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 16:32 +0000
csiph-web