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



Relevant Pages

  • Re: William Dembski - "Dennett on Competence without Comprehension"
    ... A Turing machine is a machine. ... "Compressability" would be a better definition of complexity. ... the relation between nature and intelligent design. ... falling into an infinite loop", and to make the problem interesting we ...
    (talk.origins)
  • Re: William Dembski - "Dennett on Competence without Comprehension"
    ... a contribution that Dennett ... treats as proof that a reductionist, materialist understanding of life ... Seems obvious that Turing had to have a "Turing machine" in his mind ... wouldn't try to design the longest-running program; ...
    (talk.origins)
  • Re: William Dembski - "Dennett on Competence without Comprehension"
    ... treats as proof that a reductionist, materialist understanding of life ... any competence exhibited by a Turing machine would, on its face, ... wouldn't try to design the longest-running program; ... under "Mathematics" and treat this as any other mathematical ...
    (talk.origins)
  • Re: William Dembski - "Dennett on Competence without Comprehension"
    ... treats as proof that a reductionist, materialist understanding of life ... any competence exhibited by a Turing machine would, on its face, ... wouldn't try to design the longest-running program; ... under "Mathematics" and treat this as any other mathematical ...
    (talk.origins)
  • Re: William Dembski - "Dennett on Competence without Comprehension"
    ... treats as proof that a reductionist, materialist understanding of life ... Seems obvious that Turing had to have a "Turing machine" in his mind ... wouldn't try to design the longest-running program; ...  intelligence must precede complexity because complexity ...
    (talk.origins)