Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > sci.logic > #170332

Re: Infinitely Recursive input on HP Proofs

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>

Show all headers | View raw


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


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