Happy Birthday, Turing's universal machine
Solving the unsolvable
It's just 71 years ago this month that a seminal paper from Alan Turing was published, which helped pave the way to today's multi-billion dollar IT industry and confer on Turing the title of father of modern computer science.
As is often the case in scientific endeavour, Turing was actually working on an entirely different task when he stumbled on a way to create a general-purpose computer.
The paper that encapsulated this machine? On Computable Numbers with an Application to the Entscheidungsproblem.
The Entscheidungsproblem - which translated from German literally means "decision problem" - referred to a mathematical challenge laid down by German mathematician David Hilbert.
The Entscheidungsproblem goes to the very heart of Hilbert's thoughts on the nature of mathematics. At the start of the twentieth century deep questions were being asked about science and the tools used to think about scientific problems. In the same way that Einstein's work had challenged orthodox views of physics, so Hilbert and others questioned mathematics.
Hilbert posed three fundamental questions: is mathematics "complete", is it "consistent," and - the Entscheidungsproblem - is it "decidable". The first two were answered - negatively - in 1931 by the Austrian mathematician Kurt Godel.
Turing scuppered Hilbert's final question with his 1937 paper although the American mathematician Alonzo Church - later Turing's professor at Princeton - came up with a similar negative analysis a year earlier. The two approaches are generally combined as the Church-Turing Theorem.
Turing's real insight was, of course, the concept of a "Universal (or Turing) machine." He conceived the Universal Machine as a way to demonstrate that it was impossible to solve the Entscheidungsproblem.
But he had also stumbled on what was effectively the blue print for a general-purpose computer and this almost certainly justifies his status as the founder of modern computing.
> Windows IS the universal OS.
Windows isn't universal. You mentioned Linux but you forgot many others, the MAC OS for instance. Isn't that around 5% penetration? Plus, there are several versions of Windows. What's the %age penetration of Vista, Win98, NT, 2000, XP, 3.1, 3.0? Shall I power up my Atari ST or my TSR-80? How about my ZX81? None of those run Windows (Ok, the TRS-80 runs MS Basic, but its still *not* Windows).
> It's Darwinism at work - the best of breed succeeds.
So you're equating Windows to bacteria and viruses then. They've succeeded better than anything.
Mine's the one with the role of punched paper tape in the pocket.
yes, it is still true
Yes. It is still all ones and zeroes. A hell of a lot of them to be sure, so yes the model still applies, no matter how fine your gui. And a TM can have states that are connected to every other state and branched to on particular transition conditions ... so your events are there as well ... and your massively parallel supercomputer.
The interesting question is whether a quantum computer is still a turing machine of the same kind ... the jury still seems to be out on that one.
Is it still true?
At school I was taught that a turing machine could do anything a modern computer could do.. but is it still true? It seems to me to work only for a simple procedural computer. Multiprocessor architectures, event driven programming.. even interrupts don't seem to work for a machine based on a ticker tape. I can get the idea of a VGA screen imagined (although the turing machines we were taught about had no memory, they were just decision trees), but how then to handle the user doing something as complex as dragging a window if they can't see it?
OTOH I'm prepared to believe that what I was taught at school was a turing machine was not in fact the whole story, and he had already thought about all this and come up with reasonable answers.