Re: Notions of computation

From: Ben Rudiak-Gould (
Date: 03/01/04

Date: Mon, 01 Mar 2004 01:32:20 GMT

On 25 Feb 2004 12:20:45 GMT, Lauri Alanko <> wrote:

>I have to point out, however, that my question wasn't about how to
>design such an emulator. The general principles are fairly easy to
>figure out (although your exposition is very helpful). It's just that
>I would like to avoid the trouble of actually carrying the design out,
>since someone must have done so already. So what I'm really looking
>for is an actual, complete non-trivial Turing machine specification
>and an actual, complete lambda term that emulates it. Preferably both
>in directly machine-interpretable format.

Well... it's not quite what you want, but a couple years ago I
implemented several small languages as lambda terms, plus a compiler
down to SKI combinators and a graph-reduction interpreter. One of the
small languages was Brainf* (,
which resembles a Turing machine (though it substitutes a program
counter for the TM's states). The full distribution is here:

Look in ./eg for the implementation. It's more silly hack than CS
theory, but it is written along the lines of torbenm's post, and it

-- Ben