This is the mail archive of the guile@cygnus.com mailing list for the guile project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: turing completeness



    Klaus> I recently heard that scheme is turing complete, but saw no
    Klaus> explanation.  Anyone here may explain what that means?
    Klaus> What languages are not turing-complete?

Are you referring to the fact that a Scheme program can do all
computations that a Turing machine can do?  I think they usually say
"turing equivalent" to refer to that.

There is a famous statement known as "Sussman's theorem" which states
that "any hunk of metal is equivalent to a turing machine".  This is
because profound computation can be done (inefficiently) by many
different types of dynamical systems, such as cellular automata.

This is tangential to what you were asking, but I find it quite cute,
especially after I spent some time evolving cellular automata to try
to do useful computations.  While I was working on that project I
frequently thought about how dynamical systems (and just about any
systems) do computation.