Slashdot Mirror
Turing Machine Implemented in Life
PixelJuice writes "Paul Rendell has implemented a Turing Machine in Life here. Perverted, but still kind of impressive. The site also contains a few useful links to Turing Machine principles and Life components." Normally I save this sort of stuff for the quickies, but this is to out there. I can't believe this works... but wow. (CT:Link seems to have gond thud. But thanks for the hate mail reminding me not to forget the letter v. I never knew a single letter deserved so many 4 letter words. Makes me love this job oh so much)
... "Could you imagine a Beowulf Cluster of these things?"
*goes back to trying to get QMail up*
There was a story on Slashdot recently about a Turing Machine implementation in Minesweeper. The paper is here (in yucky pdf format).
His proof is very similar to the Life proof -- which makes sense, because when you think about it, Minesweeper is a lot like Life. (That's 'Life' with a capital 'L'... I'm not trying be profound here.)
MSK
Therefore, it is not my position that machines can always fake intelligence. But I can accept the operational definition, becuase I know that sometimes we don't make judgements based on the full data. If I can make a quick judgement that someone is intelligent based upon meagre evidence, then a machine could satisfy it.
You may say I am not looking hard enough and you will be correct. Then my question is, which you you contend: that we can always look hard enough past fakery, or fakery will always win?
In fact, I don't see the necesity of believing either statement at all.
I have read the Forbes article. Initially, I was intrigued. As Stephen revealed bits of his work, I kept recalling the famous G.H. Hardy quote
Stephen has left the open, peer reviewed world of academia to pursue his highly proprietary , solo research effort. We know how well this works for software, we shall see how that works for math...
"one treats others with courtesy not because they are gentlemen or gentlewomen, but because you are" --G. Henrichs
This may have appeared recently on /. when I wasn't paying attention, but just in case...
Check out this article from Forbes on Life; Turing Machines aren't the only things that can come out of Life programs.
That makes sense. The cardinality of the set of integer points on a grid is the same as integer points on a line. Therefore you can map the grid positions to tape positions indefinitely. Good point.
Back in the early '80's the Washington University (wustl) Computer Science Department used a neat Turing Machine emulator in its introductory CS classes. One of those things that makes absolutely no sense when you are doing it, but three years later you wake up and say "_that's_ what that was for!!!".
Does anyone know if this emulator still exists? If so, has it been ported to Windows or Linux (or MS-DOS for that matter - it originally ran under the UCSD p-System!)?
Just a bit of off-topic curosity.
sPh
If I remember correctly from what the prof said, when the game was invented they set up the rules in such a way so that it was hard to predict the outcome of a given configuration. There could be other rules than an organism living only if it is next to one or two of its own kind. That rule was chosen simply because it makes life hard to predict.
From there somebody showed that you could make wires and gates using these rules and we know you can make a turing machine from (infinite number of) wires and gates. So an infinite life board can be used as a turing machine.
A Turing machine is just about the simplest model for a computing device that is possible. It consists of an infinitely long tape with symbols on it and a head that can read and write on the tape as well as move to the left and right. There are a finite number of symbols and the head (pointer?) can exist in a finite number of states. Upon encountering a symbol while in a particular state, the machine will write a symbol and then move to the left or right (or halt). It can be proven that all computable problems can be solved with a machine of this nature and, in fact, our present, modern CPU's are really just elaborate abstractions of Turing machines. For a good explanation of this, try Gary William Flake's "Computational Beauty of Nature" or "The Emperor's New Mind" by Roger Penrose.
In Soviet Russia, hot grits put YOU down THEIR pants.
While it is true that the peer review process is, as you say, the validator and not the initiator of insight, the vast major of advances in insight come from interaction with peers. Contrary to the myth, there d*mn few examples of the "lone genius." Einstein, Liebniz, Darwin, Newton, Galileo, Watson & Crick, Gauss, Archimedes....all don't qualify. Mendel is about the only one I can think of who does.
The "stereotypical mad scientist" is so popular because it is an incredibly useful device for narrative -- it spares having to explain to the audience how the "McGuffin" (to use Hitchcock's term) came about. Also, the "mad scientist" or "lone inventor" is a comforting myth for non-technical types, so it is in the self-interest of technical innovators to nurture the myth, even if it is utterly untrue."one treats others with courtesy not because they are gentlemen or gentlewomen, but because you are" --G. Henrichs
Google's cached copy of the explination of how the machine works
This makes my brain hurt, but wow, I find it amazing that someone took the time to create this. Bravo!
-inq
Here's a dump...it's bad formatting tho.
The Alan Turing Internet Scrapbook
Computable Numbers, 1936
and the Turing Machine
maintained by
Andrew Hodges Alan Turing
home page Scrapbook index Short Biography Bibliography My Books
-----
Mathematical Logic
In 1935 a course by the Cambridge mathematician M. H. A. (Max) Newman introduced Alan Turing to the frontier of research in mathematical logic.
Logic is not well represented on the Web, and unfortunately the Gödel home page doesn't tell you anything about Kurt Gödel's 1931 work that completely rewrote the agenda in the foundations of mathematics. This is just mentioned at the end of a worthwhile MacTutor summary of the Beginnings of Set Theory.
You can also read the famous 1900 speech by the German mathematician David Hilbert which did much to set the agenda for twentieth century mathematical research. Hilbert's later question about the 'decidability' of mathematical assertions set the stage for Turing's work.
This Encyclopaedia Britannica article on Logic discusses the background to decidability in mathematical logic.
I strongly recommend Martin Davis's new book The Universal Computer, the road from Leibniz to Turing as a complement to my own work.
Turing Machines and Computability
Responding to Hilbert's question about 'decidability' in mathematics, until then unanswered, Turing had the idea now called a Turing machine as his formalization of a what had informally been described as a 'method,' or in Turing's favourite expression, a 'rule of thumb.'
The Turing machine concept involves specifying a very restricted set of logical operations which are, however, sufficient to encompass anything that in modern terms would be called an algorithm.
The American Mathematical Society has a page explaining the Turing machine concept.
Turing argued that his formalism was sufficiently general to encompass anything that a human being could do when carrying out a definite method.
The Universal Machine
He had the further idea of the Universal Turing Machine, capable of simulating the operation of any Turing machine.
A Universal machine is a Turing machine with the property of being able to read the description of any other Turing machine, and to carry out what that other Turing machine would have done. Turing gave an exact description of such a UTM in his paper (though with a few bugs).
Another one was given by Roger Penrose in his book The Emperor's New Mind, and you can see this on Roman Verostko's page.
After 1945 Turing was able to embody the idea of the universal machine in his plan for an electronic computer: this is described on another Scrapbook Page.
Turing Machines Today
In my book I described the concept of the Turing machine in terms of the ideas which existed in 1935. But in fact it's now almost impossible not to think of a Turing machine as a computer program, and the Universal Turing Machine as the computer on which different programs can be run.
We are now so familiar with the idea of the computer as a fixed piece of hardware, requiring only fresh software to make it do entirely different things, that it is hard to imagine the world without it.
But Turing imagined the Universal Turing Machine ten years before it could be implemented in electronics.
Now, by a twist of history, the computer itself can be used to simulate the working of a Turing machine, and one can actually see on the screen what in 1936 was only possible in Turing's imagination.
Go to another Scrapbook page for
a Turing machine simulated in Java.
You can make it run a sequence of steps while on-line.
You can also copy the Java code and adapt it yourself.
Java Computability Toolkit - a 1998 release
A new Web resource is available from SUNY Institute of Technology at Rome, NY. It is a freely downloadable Turing machine simulator in Java. The writers say: 'It is built with collaboration and user-friendliness in mind and will always be free!' Go to the JCT site.
Turing's World
For an older full-scale Turing machine simulator, with a mass of documentation, there is Turing's World software.
This page by Kari Coleman develops a serious Turing's World algorithm for a decision problem in first-order logic, and thus exhibits the use of the Turing machine within the context of mathematical logic to which Turing originally applied it. The coded algorithm is downloadable.
Other Turing Machine Descriptions and Simulations On-Line
For a good description of Turing machines (but with outdated links) see this page by David Matuszek
Amother interesting description, including a Java simulator, is given on this page by Andreas Ehrencrona
There are other websites with information on (downloadable) Turing machine simulators.
These are maintained by:
Suzanne Skinner (another Applet)
David Matz (for Microsoft Windows)
Cristian Cheran (for Microsoft Windows)
Stefan Milius (in German. Java to download, not to run on-line.)
David Woodruff (in C).
SUNY Binghamton (Java simulation with documentation)
Turing Machines in DNA?
Alan Turing's definition of a Turing machine was not intended as a blueprint for how one would actually build practical computing machinery. The very primitive actions of reading and writing and moving one step at a time are like atoms of computation, and the atomic level is too time-consuming for what is needed in practice. However it appears that there is one modern field in which this atomic level of simplicity may be just what is needed. This is explored by Ehud Shapiro in a June 1999 paper on using the Turing machine model for a DNA computer. See his page for further information, press reports and links.
Turing Machines in Real Life
Paul Rendell has a page on building Turing machines in Conway's Game of Life.
The Uncomputable
Turing's definition of computability entailed the fact that uncomputable numbers and functions can be exhibited explicitly. The most famous uncomputable function, which Turing defined himself in 1936, is one that distinguishes between halting and non-halting Turing machines. Turing used this to answer Hilbert's question in the negative: there can be no one definite method that can decide all mathematical questions.
A version of the halting problem is given on a page by Mike Yates, which explains Turing's development of Cantor's diagonal method, and gives a proof of the essential result.
Mike Yates has a special connection with this problem. He was the first research student of Robin Gandy, who was in turn Alan Turing's first. Mike Yates was also greatly stimulated by Max Newman's knowledge of mathematical logic, and found him a great encourager just as Alan Turing did. He became Robin Gandy's collaborator, and is now the editor of the remaining volume of Turing's Collected Works, in which an annotated edition of Turing's 1936 paper On Computable Numbers will appear.
Another uncomputable function arises from the Busy Beaver problem, which is fully described with many links to other work on computability on this page by Michael Somos.
Computability, Complexity...
Turing machines, in providing a sort of atomic structure for the concept of computation, have led to new mathematical investigations. One development of the last 25 years, which Turing did not himself foresee, is that of classifying different problems in terms of their complexity, defined in terms of Turing machines.
A Nottingham University undergraduate course on computability and complexity (16 lectures) is now available on-line thanks to Dr A. N. Walker.
.. and quantum computing
Turing machines, regarded as the foundation of 'classical' computing, also provided the model in the 1980s for the new theory of quantum computing.
Computability and the Philosophy of Mind
Alan Turing described his concept of the Turing machine in terms of 'states of mind', and his work has important implications for the philosophy of Mind.
This Rutgers University course by Charles F. Schmidt has an extensive discussion of computability and artificial intelligence. It also has an excerpt from Turing's original 1936/7 paper on this page.
As indicated on the Scrapbook page on Mind and Matter, it is not surprising that Turing immediately drew this connection in his original 1936-7 paper. Turing's interest in the nature of Mind preceded his knowledge of mathematical logic, and had a powerful emotional base.
It is also notable that the Turing machine picture of computability has a definite physical sense to it, being based on what people actually do. This also reflects Turing's prior interest in physics, as well as his do-it-yourself engineering sense.
After the Second World War, Turing took a strong line that computers would be able to perform anything that people do in thinking (see this Scrapbook Page.) In my book I took the view that in taking this line Turing was simply developing to its full extent the idea of the Turing machine imitating 'states of mind'; and this is not only the generally accepted view, but the view that Turing himself argued in his post-war writings.
Accordingly it seemed to me that by 1936 Turing had rejected his youthful ideas about free will and the role of quantum-mechanical physics. As I put it, Christopher Morcom had died a second death, as Turing set out to explore the world of computability.
However I now think the development of Turing's ideas was more subtle. Although he certainly became fascinated by the role of computation after 1936, I suggest that until about 1941 Turing left open the idea that the uncomputable might play a role in human thought. Then he changed his mind. My reasons for this shift of judgment are set out in a new short text:
My own new text on Alan Turing as a philosopher of Mind appeared in November 1997. It is Turing, no. 3 of a series The Great Philosophers published by Phoenix (London) and Routledge (New York). It includes a substantial amount of Turing's original writing, and in particular big chunks of On computable numbers. My commentary explains how the Turing machine concept is related to Turing's philosophy of Mind, relating Turing's thought to Roger Penrose's ideas about computability.
More details, an extract from the text,
translations, and reviews.
Amazon page with information and review.
Church's Thesis and Turing's Thesis
A new Scrapbook Page will be prepared to link to items now on the Web which address the significance of computability. For the moment, note the article by B. J. Copeland in the Stanford Encyclopaedia of Philosophy. This has worthwhile criticism of the many loose statements to be found in present-day literature of what Turing achieved and claimed. However in my view Copeland's analysis is itself skewed by his 'super-Turing-machines' agenda (see the following section), and this article could well give a highly misleading impression of what Turing had to say about the scope of computability.
Logical Consequences for Alan Turing
Turing spent most of the next two years at Princeton University, based in the powerful research group in mathematical logic headed by Alonzo Church.
The work he did in 1937-8, his most difficult and most abstruse, charted new territory in trying to bring uncomputable numbers into some kind of order.
This page by Barry Cooper, University of Leeds, describes some modern research on the lines that Turing started.
To do this, Turing extended his concept of the Turing machine with abstract constructions he called 'oracles.' These would perform uncomputable operations. Turing explicitly wrote:
We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine.
This has not stopped the philosopher B. J. Copeland from advancing the claim that Turing would have supported a project to 'construct' such oracle-machines, which he calls 'super-Turing-machines.' He holds out the prospect of 'the biggest revolution in computing since 1948.' See this Scrapbook Page for my comment on this remarkable announcement, and this page for my discussion of Copeland's claim that Turing was leaving room for such a possibility in his 1950 paper.
Alan Turing had the chance to stay at Princeton in 1938, but he returned to Britain and at about the time of the Munich agreement began helping the British government with the problem of deciphering German communications.
Turing's work in logic had in fact stimulated an interest in ciphers, as well as in actual physical machinery.
No-one could have guessed where this would lead, not even Ludwig Wittgenstein with whom Turing argued about the philosophy of mathematics. See Wittgenstein's Lectures on the Foundations of Mathematics, Cambridge, 1939 for a transcript.
Turing and Wittgenstein did not discuss the philosophy of Mind, then or later. Many people have wondered what they would have said to each other. John Casti has written an imaginary conversation, The Cambridge Quintet, involving such a dialogue; see also a page of comment by Chris Mitchell.
More mathematics, real and imaginary
Turing's work at Princeton, as described in my book, also involved work on complex analysis and the Riemann zeta function. Its wide-ranging mixture of topics has inspired a passage in the novel Cryptonomicon by the science-fiction writer Neal Stephenson, which you can read in in this excerpt.
The extended dialogue written for Turing there is rather more thoughtful in content than anything usually found in fiction. It certainly outdoes the feeble 'I'm researching Riemann' statement attributed to Turing in Robert Harris's thriller novel Enigma. (soon to appear as a film Enigma with screenplay by Tom Stoppard who I hope will do rather better.)
The real Alan Turing in late August 1939, sailing at Bosham, Sussex. Behind him is Fred Clayton, another young Fellow of King's College, and between them the two refugee boys Bob and Karl from Austria whom he and Fred helped to get asylum in Britain.
While they were there the pact between Hitler and Stalin was signed and war became inevitable.
The Loss of Logic
The coming of war meant that Turing never again concentrated on mathematical logic, and he did not follow up the ideas he had in 1937-38 on 'ordinal logics.'
The war was to take Alan Turing to the heart of the world's affairs, and soon he was combining his logical ideas of computability with the leading edge of practical technology. He grasped this chance with great enthusiasm.
But the war also exiled him from the opportunity to develop his pure-mathematical ideas at the height of his powers.
Last updated 10 September 2000.
I am always grateful for feedback and suggestions for new links: andrew@synth.co.uk
--
That's it. I can safely say I did not understand what a Turing Machine is after reading it tho:)
'Course, when I were a lad, we never 'ad any of this game o' life nonsense, no, we'd be hand coding turing machines with orange peel and lumps of coal. And for backups we used to 'ave to brand the machine state on our own arms, and then our dad would hack 'em off at the shoulder before rubbing salt into the wound and laughing like a madman. And if we so much as complained, we'd be making punch cards out of our own saliva for a week.
And you tell the youth of today - they won't believe you.
Life, however, I wouldn't necessarily say is simpler than a Turing machine. A Turing machine has more state change rules and states, but only a 1D tape. Life has fixed states and state change rules, but a 2D grid. They seem to just be different ways to do the same thing.
One of the first programs I compiled to run on my first Linux PC back in '94 was 'xlife'. This was a superb implementation of Conway's life, and came with some quite complex patterns.
The most memorable was the prime number seive. This consisted of two trains heading away from a central point in perpendicular directions, leaving a trail of mirrors. A third train produced a glider which would bounce back and forth between the mirrors.
A slow-period glider gun at the origin fires a stream of gliders diagonally between the two rows of mirrors. For any non prime number, the new glider will hit one of the bouncing gliders and be destroyed, leaving the bouncing glider intact. The result is that only prime numbered gliders from the central gun can escape.
There was also a cute pseudo-random sequence generator.
Friends, I urge you to check out the lambda calculus or combinatory logic . Both of these are simpler (IMO), complete, and are a good complement to turing machines for certain kinds of problems. Here's combinatory logic, for instance:
K a b => a
S a b c => a c (b c)
That's it. All computable functions can be built out of Ss and Ks defined this way... holy mindfuck, Batman!
OK, this is really sick, I know...
:( ...
So you have a Turing machine running in a life grid. It'll need a bit more memory, but the hard part is done.
Next you port Bochs to the Turing machine.
Then you run DeCSS under Bochs.
Finally, you get a contract to tile some large area, and tile it with black and white tiles corresponding to some snapshot of the Life matrix.
I don't want to know how big the matrix would have to be though
Another thought - seeing that Conway's rules seem to be the simplest possible set which allows the formation of complex dynamic structures, howabout etching life patterns into deep space probes?