Turing Machine Implemented in Life 268
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)
Re:aaah! Real numbers! (Score:2)
In a nutshell (I'm glossing over details a little here), everything you consider to be a digital computer is just a form of Turing Machine, and all Turing Machines are equivalent in capability (assuming they have infinite memory), as long as you don't care about how fast they are. In other words, you could emulate a Linux box using the Life Turing Machine if you had enough memory. It would be very slow.
Anyway, as far as the halting problem is concerned, the main thing that interests people studying Turing Machines/programs is whether the head moving back & forth over the tape ever stops - in other words, will it get to the 'end' of the program. This isn't the same thing as 'failing' as you would normally consider. This is why a compiler can't determine whether a program halts. For example, if we consider C, the following program neither halts nor fails:
main()
{
while (1);
}
Whereas this program 'fails' and halts:
main()
{
int foo = 0;
int bar = 10 / foo;
}
and this program doesn't 'fail', but it also halts:
main()
{
int foo = 2;
int bar = 10 / foo;
}
All these programs compile, but only the last 2 halt. Although a person can look at a simple program and tell if it halts, the Halting Problem proof (which I can't remember) shows us that is not algorithmically possible to determine if a program halts without actually running it, and even then, we only can show that a program halts, but not that it will never halt (since we'd have to run it an infinitely long time to demonstrate that it doesn't halt).
This proof actually has very broad applications in mathematics beyond computer science. It has also been used to show that given a set of primitive 'axioms' (like the basic axioms of Euclidean geometry), it is possible to construct truths which cannot be proven by the same set of axioms. It's been about 10 years, but if you're really interested, read the book "The Emperor's New Mind" by Roger Penrose, an extremely insteresting & informative survey of 20th century math & science. It's somewhat flawed by Penrose's personal intellectual biases (for example, he refuses to accept that randomness has any important role in the way that intelligence/conciousness works), but its packed with nerd food.
Re:Turing was a fool (Score:2)
In that case, it was being used in an entirely question-begging sense.
Turing Equivalence (Score:2)
Not quite. You're forgetting the eensy detail about having an infinite Life grid (or Turing tape) to work with. But for practical purposes (except that there aren't many practical uses for Turing emulation) yes, digital computers do the same stuff. That's a big reason why people still learn about Turing machines.
Hmm... if you could create a physical Life grid (not necessarily infinte, but it would have to be really big) it might be able to solve NP-complete problems quickly due to massive parallelism (each cell being a very simple ALU & 1 bit memory).
Re:Turing was a fool (Score:2)
Re:Luxury! (Score:1)
Re:Turing was a fool (Score:1)
No, because it just happened to be. You're really going need to be clear about the meaning of a "necessary condition" if we're going to avoid talking at cross purposes.
When you were a kid, you didn't know shit about the world. The teacher passed out pointed out green leaves and you, in your infantile mind, saw no necessity for it to be so. Now having learnt about chlorophyll, you do. So were you unintelligent before? After?
No, you're not getting it. Your concept of "chlorophyll" is necessarily connected to chlorophyll because of a causal chain of events between the set of objects which are chlorophyll and the idea of it in your brain. And it has to be that way. The lookup table's entry for chlorophyll might or might not be causally related to the set of objects which are chlorophyll, but certainly don't have to be in any systematic way. Therefore, the lookup table is just a lookup table, and its set of ordered pairs cannot be interpreted as meaningful utterances.
There are more promising arguments for artificial intelligence, but surely there must be something intuitively wrong to you about a criterion of intelligence that doesn't distinguish between human beings and lookup tables?
Re:A thought (Score:1)
And since both of *those* are implemented in the laws of physics, then shouldn't physics be used as the base model of computation?
No.
Why? Because the model of computation that we already have has more power to explain computation. Just because you can build a computer out of Life patterns does not mean that those patterns are inherently computational. You could build a computer out of Legos if you wanted to, or photons, or anything else. You could argue that the "most simple" material used to construct your computer was the "most basic" and therefore "most true" model for a computer. But that would not give you any more insight into what a computer is.
What does give you this insight is not the knowledge of what the computer is made out of, but how the components function and work together to do the computing process. The "count-the-neighbors, add births, remove deaths" rules for life give none of this information.
That a Turing Machine can be implemented in Life is very interesting, but it must be understood that Turing Machines in Life universes are engineered objects, and that this engineering requires quite a bit of additional knowledge than the simple rules for the Life universe.
Re:Turing was a fool (Score:2)
You mean I have no recourse to answering this question apart from metaphysics? Gimme a break! I can give it food to see how it responds, shine light on it, etc. And you think these things don't mean a thing? That is possible for a sea slug to be unresponsive, but yet capable of abstract mathematical thought?
No serious researcher gets bothers to defend metaphysics anymore. You are fighting a battle lost a hundred years ago.
Re:This is really old news. (Score:2)
Re:That means that you can do Brainfuck with Life (Score:1)
Correction to myself (Score:1)
Re:This is really old news. (Score:1)
Correction: It is well known that it was theoretically possible to simulate a Turing Machine in the Life universe. A Turing Machine had never been fully implemented before, but various Life patterns had been discovered or engineered which could carry out the functions of various components of a Turing Machine. But the entire thing had never been put together, it being a monstrously complex and unbelievably huge pattern.
Re:First typographical error! (Score:1)
Re:First typographical error! (Score:1)
Recursion... (Score:2)
Re:Turing was a fool (Score:1)
I in no way believe that your table-method is a feasible mechanism for creating an intelligence. However, if it was implemented, and was completely 100% indistinguishable using any and all conversational techniques from a real intelligent person, then it should be deemed intelligent.
But, like I said, I am almost 100% sure that your proposed method for producing such intelligence is fundamentally flawed and impossible.
Responses which do not mean anything are not evidence of intelligence.Understand that what your describing does not satisfy the conditions of the Turing test. You are arguing that because it cannot always come up with an intelligent response, it is not intelligent. Turing would completely agree with you, as would I. So far this is completely valid according to the Turing test.
So now, exclusively consider if you can't tell the difference. No more "It's not feasible", or "You would be able to tell the difference" statement. If to all the tests you apply and that can be applied, it appears to be intelligent, is it? If not, why?
Then you should probably avoid cheap Chinese restaurants.Invalid argument. I said "cannot be distinguished", and I suspect a simple analysis (DNA or other chemical analysis) would determine what I was eating. Therefore, I would be able to distinguish your "unknown" thing from a duck unless it was a duck.
Re:Turing was a fool (Score:1)
As you probably figure out now, Turing's test is not meant to be "fool-proof". Rather, it is a test that is meant to be good enough. If a machine passes the Turing's test, then it is reasonable to consider it as intelligence. But not all intelligence machines will necessary pass the Turing's test. Also, keep in mind that the test is meant to be executed a lot of times by different judges asking questions which could be simply "off-the-wall" (i.e. out of the machine's areas of expertise). Passing the "pure" Turing's test is not as easy as it seems.
Turing is no fool. At least, he already accounts for inhuman-like intelligence in his infamous test.
Re:Turing was a fool (Score:2)
It is this offhand dismissal of this large body of work that deserves to criticized. Go ask streetlawyer about that. He appears to know lots, having spoken to so many researchers.
Re:Turing and stuff (Score:1)
Not wanting the Enemy to bomb you is the mother of lots of fun stuff... :)
-c
Re:Turing was a fool (Score:2)
IMHO, the only way to adequately refute the Turing Test as a measure of intelligence is to refute Turing's theory on what intelligence is. Turing defined intelligence recursivly, an intelligent thing is one which can convince another intelligent thing of it's intelligence. If yout take "human" as the benchmark of what is intelligent, then any computer that can convice a significant cross section of humanity of its intelligence is intelligent. The Turing Test is intimatley linked to Turing's theory on what intelligence is, and is the perfect test for what Turing defined as intelligent. To discredit the Turing test you first have to disprove his definition. The trick is that in order to really do that you have to have an alternative definition. So just come up with an encompassing definition of intelligence, then you can build a test for it. Of course to be accepted, your definition will have to be considered intelligent by those who study intelligence. So for all intents and purposes your new defintion of intelligence will have to pass a Turings Test for intelligence, in order to be accepted as intelligent... Which kinda argues in the guy's favor.
Re:Turing was a fool (Score:1)
As for your duck example, what if I were to then demonstrate that it was NOT a duck? Would it still be a duck? Would it just cease to be a duck? Or would it just prove that it was never a duck in the first place?
Re:Turing was a fool (Score:1)
As for your duck example, what if I were to then demonstrate that it was NOT a duck? Would it still be a duck? Would it just cease to be a duck? Or would it just prove that it was never a duck in the first place?
Re:Turing was a fool (Score:1)
I said nothing about being human.
Philosophical questions regarding what it is to be human are irrelevent. The question is, ONLY how to determine if something is intelligent.
Do not equate being human and intelligence. I didn't.
Screwed up logic (Score:1)
Re:Turing was a fool (Score:1)
I imagine that BMazurek probably also believes that what we call 'conciousness' is also an illusion, an aritifact of the emergent behavior we call intelligence (as I do). Some people won't except that idea, and hold to the 'weak AI' position, which more or less says that what is commonly considered conciousness or intelligence is something beyond what can currently be defined by science, and that an algorithmic computer cannot ever be intelligent, since it is impossible to model intelligence algorithmically (it is called 'weak AI' because they do believe that algorithmic computers can be used to achieve certain subsets of behavior that can be useful (expert systems, vision, etc.), but cannot achieve 'conciousness'). People like Penrose use the Halting Problem and work by Euler to justify this position 'mathematically', but only with an extreme amount of handwaving (in my opinion).
The problem I have with Turing Test opponents is that they have no proper means of determining if something is 'intelligent', or if they do have such means, they invariably would exclude 99% of the Earth's current human population by setting impossibly high standards. In they end it boils down to faith, in that they say, "Humans are intelligent because I know I'm intelligent, and since I'm a human, all other humans are intelligent, too", which is certainly one way of 'proving' humans are intelligent (to an individual), but useless for determining if non-humans (living or otherwise) are also intelligent.
First typographical error! (Score:1)
Rob (or Hemos), get back to that terminal and fix that!
Re:This is really old news. (Score:1)
Actually Conway himself published this result in 1983 For a reference see: Winning Ways for Your Mathematical Plays (1983 Berlekamp,ER Conway,JH Guy,RK, Academic Press ,New York)
But does it pass the Turing test? (Score:1)
The Turing Test Page [ucsd.edu]
Now for the obligatory joke... (Score:3)
*goes back to trying to get QMail up*
Re:First typographical error! (Score:1)
http://www.google.com/search?q=cache:www.rendell.
Re:arrgh (Score:2)
The Church-Turing principle only claims that there is no computer that can solve more problems than a Turing Machine. Clearly there are computers that can run faster than the fastest TM, but that's irrelevant. I'm not sure why this guy is implying otherwise; maybe he's just caught up in the "quantum computing" hype.
Re:Turing and stuff (Score:2)
Just wish I could find a functioning link to this one. Anyway, given Turing's insight, and the period the paper would almost have to be novel and original. Why its still classified, who knows? Maybe the offical secrets office or whatever they call themselves. What strkes me about WWII is that almost everything we now do with signals and communication comes out of that one time. Well okay, maybe not satellite and digital, but even so, the foundations were laid then. Lot of innovation in a very short time.
Re:That means that you can do Brainfuck with Life (Score:2)
Re:Turing was a fool (Score:2)
Secondly, no one ever takes what he says about AI as gospel. He is an early pioneer into the science of cognitive awareness. That is like saying that we take everything that Newton said as the utter fact without striving for more. There is so much more out there, he was just one famous name that did a lot of ground breaking work.
Also, The turing machine is a mathematical model of a computer that can do anything, but because it involves an infinite in the formula it is more or less impossible to tangibly create.
And also, who are you to declare what would have come into existence? Are you omnipotent? I sure hope not, because if omnipotence is handed out to those as closed-minded and ill informed as yourself than I'm surprised the universe hasn't folded into a singularity yet.
Re:arrgh (Score:2)
Think about it, it works.
Re:Speaking of great insights (Score:2)
If insight was indeed a communal process, frogleaps in science would be commonplace. You wouldnot *have* a list of brilliant scientists to list, like you did. The fact that you do proves that someone (Einstein, Archimedes...) made that frogleap. That was the insight. The people around them set the stage, defined the problem, then poured over their solutions, validating them and ultimately making them famous; but they didnot provide any insight...
Re:Does Wash U still use the Turing Machine emulat (Score:2)
Anyway, since I found the above program a little too constraining, I just put one together in MS Access in about fifteen minutes. It's really pretty trivial, especially if you understand the significance of TMs to begin with.
If you're lazy, a simple Google search [google.com] turns up many other prospects.
Re:Ironic, isn't it... (Score:2)
Re:okay, what's the real link? (Score:2)
Pope
Freedom is Slavery! Ignorance is Strength! Monopolies offer Choice!
Re:Turing was a fool (Score:2)
Web Life Board (Score:2)
Here's a link [nada.kth.se] to a pretty cool applet that shows exactly how CA works in real time.
This applet will even let you choose the size of the matrix you want to play with, set your own start pattern, and count generations as it goes. (It also shows the famous r-pentonimo we've all come to know and love)
Re:Turing was a fool (Score:2)
Therefore, anyone who could fake it would be quite intelligent indeed.
Heck, just watch the moderation on my posts sometime!
---
pb Reply or e-mail; don't vaguely moderate [ncsu.edu].
Another neat Turing Machine (Score:3)
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.)
Re:Turing was a fool (Score:3)
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.
Re:aaah! Real numbers! (Score:2)
When talking about Turing machines, no assumptions are made about efficiency. Just because any real, physical computer has restrictions on the number of operations it can perform in a given period of time doesn't mean that you have to place the same restriction on a theoretical Turing machine. Yes, quantum mechanical Turing machines can do some things in fewer steps than their classical equivalents, but the number of steps is usually not a consideration. For the purpose of theoretical discussion, classical Turing machines do just fine. While quantum computing is an extremely important development for the people talking about how fast you can calculate something, they're pretty much irrelevant for the people talking about whether or not you can calculate something.
Possibilities (Score:2)
Re:This is really old news. (Score:2)
"John von Neumann proved years ago that a universal Turing machine could be realized in two dimensions, and Conway constructed a universal Turing machine in his two-dimensional Life world" (D.C.Dennett "Fast Thinking" The Intentional Stance, 1989).
DCD went on to support 2D intelligence along with a couple of arguments on how speed is necessary to be intelligent.
BTW, to refute the parent post, Life is an interesting simulation BECAUSE of its predictability. From any one state, one can determine ANY of the future states. It is NOT backwards predictable (as you might imagine). This has meaning for us because we live in a world that isn't future predictable but IS past predictable (we know our history but not our future).
---
Re:Here we go... (Score:2)
It's both a play on "Alpha-Bits" cereal and on the notion of the infinite - sorry, unbounded - tape. I think that makes about as much sense as the delightful "frog and mouse" allegory that you linked.
I thought Aleph-Nought is the cardinality of the natural numbers. What do you think it is?
Ironic, isn't it... (Score:2)
proof, not conjecture (Score:2)
How do you construct such a thing? By building up abstractions. You construct "wires" from gliders and mirrors and define basic logic gates. For storage, delay lines (composed of gliders and movable mirrors) are one choice. To put everything together, writing a program that compiles logic into an initial state is probably a good idea.
Re:Speaking of cellular automata... (Score:3)
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...
Life on Polyhedra (Score:2)
Permutation City (Score:2)
For those who don't know, it is a novel by Greg Egan [netspace.net.au] about an alternate reality created simply by encoding the rules of its existence in cellular automata. It's a great read if you're into this sort of stuff.
--
Bush's assertion: there ought to be limits to freedom
Speaking of cellular automata... (Score:5)
Check out this article [forbes.com] from Forbes on Life; Turing Machines aren't the only things that can come out of Life programs.
Cardinality (Score:3)
arrgh (Score:2)
Re:First typographical error! (Score:2)
--
Wow! You're right!! (Score:2)
---
Rob Flynn
MacOS Turing machine emulator (Score:2)
I never could have done the homework for my computability and logic class without it. Debugging turing machines on paper is a bitch!
--
Does Wash U still use the Turing Machine emulator? (Score:3)
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
Re:Possibilities (Score:2)
It's long been known that it is possible to implement a Turing machine in Life, because it is possible to implement AND and OR logic gates.
Wake me up when they program the Turing machine itself to run Life. :)
Re:Speaking of cellular automata... (Score:2)
Peer review *validates* scientific and engineering works. It does not create them.
Here we go... (Score:2)
"You made a Turing machine out of cereal?"
"You made a Turing machine out of a popular magazine?"
"You made a Turing machine out of the quality that distinguishes a vital and functional being from a dead body?"
--
This is really old news. (Score:4)
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.
Re:Simplest Possible..? (Score:2)
==================
By the time you have reached perfection, there's nobody around you to share it with.
rendell.co.uk (Score:2)
It's amazing how people (in all aspects of life) assume that someone else is wrong, just because someone else's suggestion does not match the person's preconceived notion of what they should be hearing -- especially without even bothering to check of they are right or not.
rendell.uk.co contains the correct page [rendell.uk.co] (as evinced by Googol [google.com], even though it is currently slashdotted). "rendell.co.uk" has no nameserver lookup, and "www.rendell.co.uk" is a completely unrelated site and does not [rendell.co.uk] mention Turing machines at all.
The domain "rendell.uk.co" is registered to Paul Rendell, as of 10 July 2000, and the domain "rendell.co.uk" to Webhound Ltd., as of 16 Sep 1999.
To use a cliche, "People hear what they want to hear"
Slashdotted (Score:2)
The Turing Machine Program
The program I chose is one that duplicates a pattern of 1's. With 2 1's on the tape to the right of the reading position it takes 16 cycles to stop with 4 1's on the tape. This takes over one hour on my computer.
The state transition table for this program is as:
State
Input Symbol 0
Input Symbol 1
Input Symbol 2
0 Find next v=1
D:R, V:0, NS:2
D:R, V:2, NS:1
D:L, V:2, NS:0
1 Write 2*v=2
D:L, V:2, NS:0
-
D:R, V:2, NS:1
2 Convert v=2 to v=1
Halt
-
D:R, V:1, NS:2
Where:
D = Direction
V = Value of symbol to write
NS = next state
A P240 gun has been placed to insert the instruction "D:R, V:0, NS:0" when the blocking glider is deleted, which it is in the initial pattern above. This starts up the Turing Machine.
Back to Turing Machine Main Page
Re:Here we go... (Score:2)
To implement the Turing machine's infinite tape in a cereal, of course, you wouldn't use Life cereal, you'd use Aleph-Nought-Bits...
(If you don't know what Aleph-Nought is, please don't even think about moderating this post...)
Re:arrgh (Score:5)
Re:Speaking of cellular automata... (Score:2)
Nope. I am not trolling. I have worked with Stephen's colleagues. I have used SMP (The Mathematica predecessor he wrote while still at CalTech). I have used Mathematica extensively.
Stephen is a smart guy, certainly way smarter than I am. But his "genius" is seriously over-rated, particularly by whoever writes his press releases. Those I know who have actually worked with Stephen are more impressed by his ego than by his insights (Dick Feynman being a notable exception).As for Mathematica being "one of the most amazing computer programs ever produced," well, I dunno. Certainly an ambitious attempt. But whenever I've needed to get real work done, I found that while Mathematica could (in principle) do it, it simply was too overwrought and cumbersome to be competitive with other available solutions. ...and Mathematica was far from a "solo" effort.
A thought (Score:2)
Re:A thought (Score:2)
Re:arrgh... lets straighten this out (Score:2)
Quoting from your link:I also never claimed that the C-T Thesis has been proven; in fact, I strongly suspect that it is unprovable. Like you said, it's a "rule of thumb," but I am not aware of any violations of it.
Re:Speaking of great insights (Score:3)
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.Use Google's copy instead of his (Score:4)
Google's cached copy of the explination of how the machine works [google.com]
This makes my brain hurt, but wow, I find it amazing that someone took the time to create this. Bravo!
-inq
For all who can't get to the site (Score:5)
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:)
fixed point combinator (Score:2)
Perhaps you already know this, but I can't sit idly by while you cast aspersions on a most interesting function, the fixed-point combinator:
It returns the fixed point of any function expressible in lambda calculus. If that doesn't have an important logical meaning, I don't know what does!
Luxury! (Score:5)
And you tell the youth of today - they won't believe you.
Re:This is really old news. (Score:2)
Now, I think the bigger issue here is the reading along the tape: at some point you either move the 'head' that reads it, or the tape itself, neither which you can directly build from wires and gates. And given the way life works, the latter is probably near impossible since you don't know what's on the tape and therefore cannot accurately move it, meaning that the head is moving along the tape. Which means that the collection of atoms that make up the head have to read the tape, take the date out of the head to a storage area, then recreate itself some 'bytes' from it's original position, all while maintaining the connection to the storage area AND maintaining the integrity of the tape.
Most likely, sending the data can be done using flyers, so that there need not be a length of surviving atoms between the mutable head and the medium. (Flyers have 4 phases , so they can at least store a 1 or 0 depending how that flyer is sent off). Moving the head is a bit tricker and once the site is not /.'ed, I'll check it out.
Re:Turing was a fool (Score:2)
Turing's "simulation game" (nowadays known as the "Turing test") avoids the issues of a descriptive definition by focussing on an operational definition.
If you consider his operational definition to be the wrong way to define intelligence, then perhaps you can share your profound insights into the nature of intelligence with the slashdot readers by providing your definition for us to criticise.
Re:This is really old news. (Score:4)
Re:Turing and stuff (Score:2)
I've never heard of that. But Turing's Teatise on the Enigma [home.cern.ch] was declassified a few years ago by the NSA. An introduction and history of that book is available at the Turing site [turing.org.uk]. That same site has a bibliography [turing.org.uk], and yet still no mention of material still classified.
That is not any proof that there still isn't classified material. When someone at the US National Archives sent me a copy of Turing's Treatise in 1997, that was a surprise. But while there might still be some undiscovered work by Turing. I'd be surprised if there is anything still classified.
Re:This is really old news. (Score:3)
The requirement of an infinite tape (or, rather, a non-terminating one) is only required for the machine to emulate every single possible terminating automaton possible; for a finite subset, the length of the tape (and the number of states in the machine) is bounded.
Re:A thought (Score:3)
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.
Game of Life prime number seive... (Score:3)
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.
Re:Turing was a fool (Score:2)
As for the Chinese bit... well, according to the latest census forms, your 'race' depends not on your ancestry, but on which 'culture' you claim. You could very well be Chinese, as far as the government's concerned, if you think you are....
---
Re:Turing was a fool (Score:2)
Turing was attempting to advance the argument about intelligence with an operational definition. Whether you agree with the definition of or not, it appears that you would rather take on faith the idea that "it can all be faked".
If you really believed that, then it appears to me that you believe in ineluctable truths. You may as well believe that there's a pink dragon in your room and nobody can convince you otherwise.
That means that you can do Brainfuck with Life (Score:2)
Re:Speaking of cellular automata... (Score:4)
Simplest Possible..? (Score:4)
Friends, I urge you to check out the lambda calculus or combinatory logic [www.cwi.nl] . 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!
Re:Turing was a fool (Score:2)
Why and why not?
Re:Turing was a fool (Score:2)
A new way to distribute DeCSS and talk to aliens.. (Score:5)
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?
Re:Turing was a fool (Score:2)
It's interesting to note that having claimed that humans are distinct from computers, you acknowledge now that there is a circumstance in which you can't tell them apart.
So the question to you now is this: Is shoving bits around one of those circumstances? Why or why not?
Please answer the question.
Re: (Score:2)
Re:Turing was a fool (Score:2)
Re:Turing was a fool (Score:2)
Most people, if you challenge them to define intelligence (and ask them if a computer is intelligent) will immediately start to try to find a definition that is based on the difference between humans and machines. You seem to be doing this.
Consider this: if you're determined to prove that machines are fundamentally different from humans in some way that makes them ineligable for intelligence, then you have to also prove that humans are not themselves simply elaborate finite state machines. I don't think you can do this.
Re:Turing was a fool (Score:2)
Is there a necessary condition now?
When you were a kid, you didn't know shit about the world. The teacher passed out pointed out green leaves and you, in your infantile mind, saw no necessity for it to be so. Now having learnt about chlorophyll, you do.
So were you unintelligent before? After?
A computer too can discover and learn about such things, in rather limited and specific instances. It matters not whether you want to call it intelligence or not. This is already reality.
You are just lucky to be living in a time when this distinction can still be maintained, largely.
Re:Turing was a fool (Score:2)
Re:arrgh (Score:2)