Re: Notions of computation

From: Ben Rudiak-Gould (benrg_at_darkweb.not-this-part.com)
Date: 03/01/04


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

On 25 Feb 2004 12:20:45 GMT, Lauri Alanko <la@iki.fi> 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* (http://www.muppetlabs.com/~breadbox/bf/),
which resembles a Turing machine (though it substitutes a program
counter for the TM's states). The full distribution is here:

    http://esoteric.sange.fi/essie2/download/lazy-k/

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
runs.

-- Ben