# Re: Notions of computation

**From:** Ben Rudiak-Gould (*benrg_at_darkweb.not-this-part.com*)

**Date:** 03/01/04

**Next message:**André Betz: "Converter TM -> Rule110"**Previous message:**Piotr Wyderski: "Re: Distance between equations"**Next in thread:**Mark Kvale: "Re: Notions of computation"**Maybe reply:**Mark Kvale: "Re: Notions of computation"**Reply:**Suresh Venkat: "Re: Notions of computation"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

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

**Next message:**André Betz: "Converter TM -> Rule110"**Previous message:**Piotr Wyderski: "Re: Distance between equations"**Next in thread:**Mark Kvale: "Re: Notions of computation"**Maybe reply:**Mark Kvale: "Re: Notions of computation"**Reply:**Suresh Venkat: "Re: Notions of computation"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]