How
simple can a Touring machine get before it's not a universal Turing
machine? Wolfram research sponsored a contest to find out, and
the results are here.
To understand what Wolfram means by a two-dimensional Turing Machine, here is a good introduction.
The whole subject of computability has spawned large numbers of books
and articles, many of which can be found in the library's databases
(look at those listed under "Computer Science"). The best known
problem in computability is related to the Halting problem, and is
known as the P vs. NP problem. The Clay Mathematics Institute is offering a cool million bucks to the first person who can solve this problem.
For the Java literate: Here are several java source files (and directions) that implement a Turing machine.
And just as everybody thought that they were done with cellular automata, here's an example of a Turing machine implemented inside the Game of Life. So it can be done, but should it? And if it should be done, should it be allowed to replicate?
Deep background:
Turing's work on computability rose from the "Entscheidungsproblem"
that Hilbert proposed. His most famous work on the subject is his
paper "On Computable Numbers, with an Application to the Entscheidungsproblem." Wikipedia has a subject entry on both computable numbers and computable functions.
|
