Wednesday, February 17, 2010

Parallel Computing: The End of the Turing Madness. Part I (repost)

This is a repost of a previous article. I still feel the same way about Turing, sorry.

Part III

Hail, Turing

Alan Turing is, without a doubt, the most acclaimed of all computer scientists. He is considered to be the father of modern computer science. Soon after his untimely death in 1954 at the age of 41, the computer science community elevated him to the status of a god. Books are written, movies are made and statues are erected in his memory. Turing is so revered that the most coveted prize in computer science, the A. M. Turing Award, was named after him. It is worth noting that Turing’s sexual inclinations and religious convictions did little to diminish his notoriety. Homosexual and atheist movements around the world have wasted not time in transforming the man into a martyr and the sad history of his life into a veritable cause célèbre. The end result is that nothing negative may be said about Turing. It is all right to talk about the Von Neumann bottleneck but mentioning that the bottleneck was already part and parcel of the Turing machine is taboo. The adulation of Turing is such that criticizing him or his ideas is guaranteed to deal a deathblow to the career of any scientist who would be so foolish.

Unabashedly Bashing Turing and Loving It

It is a good thing that I don’t lose any sleep over my reputation in either the scientific community or the computer industry, otherwise I would be in a world of hurt. I am free to bash Turing and his supporters to my heart’s content. I am free to point out that the emperor is buck-naked and ugly even while everyone around me is fawning at his non-existent clothes. As someone with a strong iconoclastic bent, I admit that I enjoy it. Free speech is a wonderful thing. I have argued forcefully and unabashedly in the past that academia’s strange and pathological obsession with Turing is the primary cause of the software reliability and productivity crisis. I now argue even more forcefully that the parallel programming crisis can be directly traced to our having swallowed Turing’s erroneous ideas on computing, hook, line and sinker. Had the computer science community adopted the correct computing model from the start, there would be no crisis and you would not be reading this article and getting offended by my irreverent treatment of Mr. Turing. In fairness to Turing, my criticism is directed mostly toward those who have turned the man into the infallible god that he never was and never claimed to be.

The Not So Universal UTM

Unfortunately for Turing’s admirers, for many years now, the laws of physics have been quietly conspiring against their hero. Sequential processors have reached the limits of their performance due to heat dissipation problems. The computer industry is thus forced to embrace parallel processing as the only way out of its predicament. Parallelism is a good thing but it turns out that programming parallel processors is much easier said than done. In fact, it is such a pain that the big players in the multicore industry are spending hundreds of millions of dollars in research labs around the world in the hope of finding a viable solution. They have been at it for decades without any hint of success in sight. Worse, the leaders of the industry, out of sheer desperation, are now turning to the very people who got everybody into this mess in the first place, none other than the Turing worshippers in academia. It would be funny if it weren’t so pathetic.

Consider that Turing’s ideas on computing, especially the Universal Turing machine (UTM), were strongly influenced by his love of mathematics. He was, first and foremost, a mathematician and, like Babbage and Lady Ada a century before him, he saw the computer primarily as a tool for solving serial math problems. It is highly unlikely that he ever thought of the concept of parallel processing or the idea that a computer might be used for anything other than problem solving and the execution of instruction sequences. The time has come for the computer industry to realize that the UTM is the quintessential sequential computer and, as such, it is ill suited as a model for parallel computing. It is time to devise a truly universal computing machine, an anti-UTM machine if you will, one that can handle both sequential and concurrent processing with equal ease.

Smashing the Turing Machine

The Turing machine cannot be said to be universal because it is a strictly sequential machine by definition whereas the universe is inherently parallel. It is certainly possible to use a UTM to emulate parallel processes. Programmers have been emulating parallelism in such applications as neural networks, video games and cellular automata for decades. However, the emulation is not part of the Turing computing model. It is an ad hoc abstraction that a programmer can use to pretend that he or she is performing parallel processing even though the underlying model is sequential. Programmers get away with the pretense because processors are extremely fast. Slow the processor down to a few hundred Hertz and the illusion of parallelism disappears.

One can always argue that having two or more Turing machines running side by side is an example of parallel computation. However, two Turing machines running independently cannot be construed as representing one Universal Turing machine, as defined by Turing. Parallelism is not synonymous with temporal independence. On the contrary, a truly parallel system is one in which all events can be unambiguously determined as being either concurrent or sequential. Even if one could extend the definition of the UTM to include multiple parallel machines, deciding which operations are performed concurrently requires even more ad hoc additions such as a communication channel between the two machines. Alternatively, one can imagine a Turing like machine with an infinite number of read/write heads on a single infinitely long tape. Still, the Turing model does not provide a deterministic mechanism for the detection of either concurrency or sequentiality and the problem becomes worse with the addition of multiple heads. There is only one way to solve the parallel programming crisis. We must smash the un-universal Turing machine and invent a truly universal alternative.

In Part II of this two-part article, I will describe what I mean by a true universal computing machine and do a direct comparison with the UTM.

See Also:

How to Solve the Parallel Programming Crisis
Parallel Computing: Why the Future Is Non-Algorithmic

1 comment:

amanfromMars said...

"It is highly unlikely that he ever thought of the concept of parallel processing or the idea that a computer might be used for anything other than problem solving and the execution of instruction sequences."


I would imagine the exact opposite and conclude that he thought of everything else being realised and computerised/virtually drive, Louis.

Which locked him into a a very small unknown world in a world of many crazy mad secrets for who would understand his thoughts if they were unknown and a cynical oppressive stranger or duped robotic assassin to AI?