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