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)
To understand the halting problem, you first have to understand what a Turing Machine is. As mentioned in posts above, a Turing machine is an infinitely long "tape" (magnetic, hole-punch, whatever) which can be filled with "symbols" (instructions, data, whatever). In addition, there is a "head" which can move back and forth over the tape and read a symbol or write to it. The Turing Machine "runs" by reading some starting symbol on the tape carrying out the instruction that symbol represents. As you can imagine from the structure of the Turing Machine, there aren't too many instructions that are capable of being performed - move left or right n units, or basic increment & decrement operations to symbols themselves.
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.
In that case, it was being used in an entirely question-begging sense.
-- the most controversial site on the Web
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).
And YOU are not intelligent. It's actually a bundle of neurons deep within your cerebrum. You are a meatspace cellular automaton.
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.
MSK
Now surely, somebody has used some kind of diagonalisation to implement the game of life on a Turing machine. How powerful does the hardware need to be to run a single Life->TM->Life stack at faster than glacial speed?
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.
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.
I don't need a million points of light, just two points of multi-mode fiber and a 10 Gig-E router.
... "Could you imagine a Beowulf Cluster of these things?"
*goes back to trying to get QMail up*
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.
MSK
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.
get a life... (or a brainfuck or a aw shucks now you got me all confusified)
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.
Dacels Jewelers can't be trusted.
Think about it, it works.
MSK
I respectfully disagree; I particularly disagree with your definition of 'insight'. Insight is that spark of brilliance that cuts through a problem and either reduces it down to its essense or, ultimately, solves it. This is not a communal process. It's something that takes genius. True, unadulterated genius.
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...
We used a TM simulator in my "Philosophy and Computers" class. It had an unnecessarily clever name, and an unnecessarily clever interface. It also ran only on MacOS. Anybody know the one I'm talking about? It's right on the tip of my tongue.
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 turns up many other prospects.
MSK
we're just all hoping that artificial intelligence will make up for a lack of natural intelligence.
yeah, .co is Colombia for fsck's sake. What's this guy trying to pull?
Pope
Freedom is Slavery! Ignorance is Strength! Monopolies offer Choice!
It doesn't mean much now, it's built for the future.
I don't see how you, being human, is not a necessary condition for there being a spinal cord. And having qualified by statement, restricting attention to those with functional spinal cords and functional knees and legs. Then it is necessarily true that such knees would jerk. It is not "just happens" to be true. The chain of causation is very strong in such a case.
Here's a link 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)
Ah, but you'd think that being able to fake intelligence would be much harder to do than merely being intelligent.
;)
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.
pb Reply or e-mail; don't vaguely moderate.
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 know this is kinda redundant, but...
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.
Bugrit! Millenium hand and shrimp!
Wow, a Turing machine implemented in game-of-Life. You could program it to do anything. You could even make a spell checker run in Life! :)
I too remember that begin old news many years ago too
"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).
---
---
I'm just an ordinary man with nothing to lose.
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?
Kinda interesting that this discussion on artificial intellegence has so many people calling each other idiots.
No, I don't trust in god. He'll have to pay up front, like everybody else.
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.
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
I wrote some code to run life on 3d surfaces. http://www.speakeasy.org/~morse/life
Cool, so now Permutation City can be real?
For those who don't know, it is a novel by Greg Egan 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
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.
Link has been /.ed, what the hell is a turing machine?
Dirty Pirate Hooker
their, they're - know knead two bee sew peeved... ;-)
--
"It's tough to be bilingual when you get hit in the head."
I almost couldn't tell that it wasn't a REAL broken link ...
Oh hmm....
---
Rob Flynn
---
Rob Flynn
Pidgin
It's called Turing's World, and it was written by John Barwise and John Etchemendy, philosophers at Stanford.
I never could have done the homework for my computability and logic class without it. Debugging turing machines on paper is a bitch!
--
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
"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?"
--
--
Mod up a post Rob doesn't like and you'll never mod again
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.
==================
By the time you have reached perfection, there's nobody around you to share it with.
==================
By the time you have reached perfection, there's nobody around you to share it with.
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 (as evinced by Googol, 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 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"
This is from my cache [can't post front page - just an image]:
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
Free Anne Tomlinson!!
Since a turing machine can be implemented in Life, this means Life is equivalent to a turing machine. Since Life is simpler than a TM, doesn't this actually mean Life should be used as the base model of computation, rather than a TM?
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.
MSK
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:)
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!
'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.
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.
I've never heard of that. But Turing's Teatise on the Enigma was declassified a few years ago by the NSA. An introduction and history of that book is available at the Turing site. That same site has a bibliography, 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.
Prime numbers are exactly what Alan Greenspan says they are -S. Minsky
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.
So he designed something that he didn't think would have much Real Life application. Welcome to math. Boole thought he was designing the most 'pure' math possible, something which would have no conceivable use whatsoever... and now Boolean Logic is the basis for most of the world's digital computing devices.
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....
---
Good judgment comes from experience.
Experience comes from bad judgment.
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.
This means that since you can do a turing machine, you can do my favorite language Brainfuck with Life. I am still waiting for M$ to bring out Visual Brainfuck (VB for you folks), to make the interface stuff easier... This might be a breakthrough.
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!
Why and why not?
They may well be functionally equivelent. However, that hardly makes them the same. If you wish to label that painted goose as a duck, feel free. But I submit that you just aren't looking close enough.
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?
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.
The link appears to be pointing to a clean default installation of Apache. Paul has outdone himself doing a Turing port soo quick.
To Terminate, or not to Terminate, that's the question - SCSIROB
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.
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.