Re: Notions of computation
From: Ben RudiakGould (benrg_at_darkweb.notthispart.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 nontrivial Turing machine specification
>and an actual, complete lambda term that emulates it. Preferably both
>in directly machineinterpretable 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 graphreduction 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/lazyk/
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 ]
Relevant Pages
