Re: Notions of computation

• Previous message: Ian A. Mason: "Re: Notions of computation"
• In reply to: Lauri Alanko: "Notions of computation"
• Next in thread: Lauri Alanko: "Re: Notions of computation"
• Reply: Lauri Alanko: "Re: Notions of computation"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: 25 Feb 2004 12:50:01 +0100

Lauri Alanko <la@iki.fi> writes:

> Firstly, as everybody knows, there are multiple equivalent ways of
> formalizing the same notion of computation: Turing machines, partial
> recursive functions, lambda calculus, combinatory logic, etc. Of
> these, Turing machines are the most popular expository tool for
> discussing computability theory.
>
> Why is this?

Partly for historical reasons and partly because there are
easily-defined and interesting subsets of Turing machines, such as
finite-automata, push-down automata, and bounded-tape machines.

> Of the above options, TMs are not only the farthest
> removed from practical programming, but they are also the only ones
> that don't have a convenient syntactic notion of composition. Yet such
> basic facts as "the union of recursive languages is recursive" and "if
> a language and its complement are recursively enumerable, then the
> language is recursive" etc. are proven by composing machines that
> recognize those languages.

Not only that, but TM's are notoriously difficult to program in
compared to, say, the pure untyped lambda calculus.

> Second question. Though the above equivalences are well-known, I still
> haven't found very concrete proofs. Only general "in principle"
> -proofs that usually work by constructing horrendous Gödel numbers
> that you would never want to be deal with in practice. Can someone
> suggest where to look for a _fully specified_ (ie. directly
> implementable) translation between Turing machines and lambda terms?

It is easy to emulate a Turing machine in lambda calculus, but the
converse is very hard. Here is a simple emulation of a TM in lambda
calculus:

 Step 1: Representation of tape.

 We represent the tape as two lists: one for the tape at and to the
 right of the pointer and another (reversed) for the tape to the left
 of the pointer. An empty list is represented as \xy.x and a list
 starting with the symbol k in front of the list l is (\xy.y k l). We
 leave the representation of symbols open, but it could, e.g., be
 \xy.x for 0 and \xy.y for 0. The empty list must be interpreted as
 unbounded uninitialized tape by the TM emulator. Uninitialized can
 be 0 or a separate symbol, depending on the tape alphabet.

 Step 2: Representation of states.

 Each state has N actions (where N is the number of different
 symbols), so we represent a state as a function that takes the two
 tape-halves and a (continuation) function c and calls c with the two
 new tape halves and the number of the next state. The TM program is
 represented as a list of states s_1, s_2,...,s_n, using the
 representation \x.x s_1 s_2 ... s_n, so a state number i is
 represented as \x_1...x_n.x_i. Examples of states are shown below.

   A stopping state does not call the continuation but simply returns
   the tape halves as a pair: stop = \lrc.\x.(x l r).

   A state that writes 0 to the current tape position and continues
   with state s is: \lrc.c l (r (\xy.y u r) (\kr.\xy.y 0 r)) s. Note
   that we test if r is empty and extend it in this case. Otherwise,
   we add 0 to what is to the right of the current symbol.

   A state that jumps to either s_1 or s_2 depending on whether the
   symbol at the current tape position is 0 or 1 (using the above
   representation for 0 and 1) is: \lrc.c l r (r s_1 (\kr.k s_1 s_2).
   This interprets uninitialized tape as 0's.

   A state that moves the tape pointer right and continues with state
   s is: \lrc.r (c (\xy.y 0 l) r s) (\kr.c (\xy.y k l) r s). Note
   that we again test for empty tape and interpret unitialized as 0.

   A state that moves the tape pointer left and continues with state s
   is: \lrc.l (c l (\xy.y 0 r) s) (\kl.c l (\xy.y k r) s). Note the
   symmetry with the above.

 Step 3: Emulating the TM.

 We construct a lambda term T that takes four arguments: The TM
 program t, the left part l of the tape, the right part r of the tape
 and the number s of the next state. The function is recursive, so we
 use the Y combinator:

   T = \t. Y (\e.\lrs. s t l r e)

 We first extract the current state by applying s to t. We apply this
 to l, r and the continuation e, which is the evaluation loop. The
 above is the entire TM emulator. It is almost trivial, as we have
 built the hard part into the representation of the states.

> Thirdly. One property of the class of computable functions is that it
> includes its own universal function: there is such a thing as a
> universal Turing machine, and an LC evaluator written in LC, and of
> course a universal recursive function Phi(x,y)=phi_x(y) where phi_i
> enumerates all recursive functions.
>
> Are there other interesting classes of computable functions that also
> include their own universal function? Ie. are there sensible
> non-Turing-complete languages in which their own evaluator can be
> written?

If a language includes the primitive recursive functions, then the
existence of a self-evaluator implies Turing-completeness. So such
languages are either very simple or Turing complete.

        Torben

• Previous message: Ian A. Mason: "Re: Notions of computation"
• In reply to: Lauri Alanko: "Notions of computation"
• Next in thread: Lauri Alanko: "Re: Notions of computation"
• Reply: Lauri Alanko: "Re: Notions of computation"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]