This week we’ll venture in the realm of theory for a change, starting with Turing machines.
In case some of you don’t know what a Turing machine is, here is the Wikipedia definition: “A theoretical device that manipulates symbols contained on a strip of tape.” It is not a practical computing device, but rather “a thought experiment representing a computing machine.”
And why bring this up? A guy named Mike Davey has actually built a classic Turing machine that really works!
Unlike Turing’s thought experiment, this one doesn’t have an infinite tape but instead uses a 1,000-foot roll of 35mm film leader (that’s infinite enough for practical purposes).
The write head that creates symbols on the tape is a black, erasable marker and erasing symbols is done by a felt pad that is lowered onto the tape when needed. The symbols on the tape are “read” by a camera and the whole apparatus is driven by a Parallax Propeller microcontroller.
The entire project, both hardware and software, is open source and I want one!
There’s a type of Turing Machine that most people in IT will have heard of: Cellular Automata (CA). These are computational systems based on grids that can have one, two, three or more dimensions. The cells that make up the grid have two or more states and to begin there is some starting configuration of cells in various states. A set of rules determine the next state of each cell in the grid with the resultant state being dependent on the cell’s own states and the states of its neighbors (usually the states of its immediate neighbors). Normally the states of all the cells change simultaneously so time in this system moves forward in discrete steps.
For example, in the classic Conway’s Game of Life, a simple orthogonal grid in two dimensions constitutes the world. The states of the eight neighbors adjacent to each cell are examined and the sum of their states determines the cell’s next state. In Life the rules are very simple, but the results can be spectacular, often with complex patterns forming, moving, growing and dying.
If you should want more Turing machine stuff check out the demonstrations on Wolfram Research’s site, the home of Mathematica, the amazing legendary mathematical computation program.
Wolfram offers a free player that will execute Mathematica Notebooks (collections of formulae that are ready to be executed) and the site offers 26 Turing machine demonstrations.
I’d also advise checking out Stephen Wolfram’s 2002 book, “A New Kind of Science“, wherein Mathematica’s creator argues that “it is possible to view every process that occurs in nature or elsewhere as a computation.”The science of Turing machines is at the heart of this work.
This treatise is heady stuff and should you opt to buy Wolfram’s book rather than peruse it online, make sure you keep a firm hold of the tome; at 1,197 pages it could cause serious damage to your toes if dropped.
To end this week, I leave you with some speculative physics based on the idea of CAs and which is firmly in Wolfram’s theoretical territory: The idea that universe is actually one vast cellular automaton. This theory was proposed in 1967 by Konrad Zuse, who also designed the first high-level programming language and formed a very early computer company in 1946 funded by patents licensed to the then very young IBM.
I shall leave you to follow that rabbit hole, wherever it might take you.
Gibbs’s universe is Ventura, Calif. Your calculations to gearhead@gibbs.com.
