Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | sci.logic |
| Subject | Re: Infinitely Recursive input on HP Proofs |
| Date | 2018-01-17 01:09 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <87o9lt47gd.fsf@bsb.me.uk> (permalink) |
| References | (3 earlier) <8737ehx3zz.fsf@bsb.me.uk> <8cb5d54a-10a7-48c4-8cb1-fcc81ba7e4d3@googlegroups.com> <878to6v4za.fsf@bsb.me.uk> <2_-dnUrLt96SBcDHnZ2dnUU7-fHNnZ2d@giganews.com> <f9d28ff7-1661-4386-a136-0329a36137d9@googlegroups.com> |
George Greene <greeneg@email.unc.edu> writes: <snip> > The ACTUAL correction would read something like > qx Wm Wm ⊢* Ĥ y1 qn y2 , > since Linz's notation ALWAYS starts with the state where you are beginning. > You are just assuming continuation from the previous/last state, > which is correct, but again, the question is HOW TO WRITE it clearly, > and Linz just fails massively. Linz has a notation that could have been used to clear this up but it's even more cumbersome: q_(A,0) for state 0 of machine A. And while it makes it clear what states belong to which machine that also obscures the fact the all the machines in the construction share a lot of states and transitions. Do you say that q_(H,i) = q_(H',i) for all n states of H, or do you allow them to be distinct provided the state transitions are preserved by the correspondence between them? It makes no odds, of course, since all that matters is the behaviour, but when talking about states and transitions and traces you have to say one way or the other. Basically, the description is at the wrong level. The level that matters is of computations and compositions of computations. The lambda calculus works at the right level for this, but there is so much more technical material to cover before students feel that a lambda form really encapsulates the idea of an effective procedure that any advantage this presentation may have is undone. TM's are so simple to explain and so obviously capture the basic idea of doing something mechanically that they are the natural choice. What is needed is a presentation that uses TMs but that works at a level higher than the states and the transitions. You can make it formal, but you do that when explaining general constructs like A | B (A then B) which is a TM whose delta function takes the final state (or states) of A to the initial state of B. Even this detail is fiddly, but once you have it out of the way, you are talking at a higher level, much as you like to talk about one machine calling another. The other basic construct used in the proof is A ? B : C which is a machine that "does" B from A's accepting states and C from it's rejecting ones (so A | B is really A ? B : B). By the way, I usually try to avoid talking about calling a machine because it suggests a function call that could, in theory, be nested and that returns to somewhere. Obviously you can model that with TM's, but a more natural computing metaphor is just a jump or goto. <snip> -- Ben.
Back to sci.logic | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-16 13:25 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-16 14:09 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-17 20:05 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-17 20:28 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-17 21:09 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-17 21:15 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-18 09:37 +0000
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 10:50 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 07:57 -0800
Re: Infinitely Recursive input on HP Proofs Peter Percival <peterxpercival@hotmail.com> - 2018-01-18 16:28 +0000
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 10:22 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-18 10:30 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 10:51 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-17 01:09 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-18 08:18 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 10:01 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-18 10:22 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-21 20:58 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-22 15:45 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-22 18:18 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-19 01:04 +0000
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 17:54 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-18 19:12 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 19:32 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-18 20:06 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 20:20 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-18 21:10 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-20 00:06 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 19:36 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-18 18:50 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 19:38 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-20 00:00 +0000
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-20 00:12 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-21 07:19 -0800
Re: Infinitely Recursive input on HP Proofs Jim Burns <james.g.burns@att.net> - 2018-01-21 21:32 -0500
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-22 15:22 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-22 17:31 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-22 02:40 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-22 14:59 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-23 01:58 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-22 18:17 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-22 18:34 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-22 19:02 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-22 21:30 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-22 21:35 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-23 11:43 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-23 08:31 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-23 20:30 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-23 14:11 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-24 01:20 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-23 17:56 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-25 02:04 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-24 18:14 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-25 02:38 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-24 18:48 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-25 04:07 +0000
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-23 22:05 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-23 22:16 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-24 19:43 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-24 20:17 -0800
Re: Infinitely Recursive input on HP Proofs grahamcooper7@gmail.com - 2018-01-24 20:57 -0800
Re: Infinitely Recursive input on HP Proofs grahamcooper7@gmail.com - 2018-01-24 21:00 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-25 11:31 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-25 07:28 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-23 22:09 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-23 22:27 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-24 19:48 -0800
Re: Infinitely Recursive input on HP Proofs Peter Percival <peterxpercival@hotmail.com> - 2018-01-21 17:41 +0000
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-22 01:18 +0000
Re: Infinitely Recursive input on HP Proofs Peter Percival <peterxpercival@hotmail.com> - 2018-01-22 12:38 +0000
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-21 20:49 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-21 20:51 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-22 15:24 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-22 17:32 -0800
Re: Infinitely Recursive input on HP Proofs Mikko <mikko.levanto@outlook.com> - 2018-01-23 20:15 +0200
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-23 14:13 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-22 15:40 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-22 18:10 -0800
csiph-web