Saturday, June 21, 2008

Parallel Computing: The End of the Turing Madness. Part II

Part I

Don’t Read My Stuff

I want to preface this post by pointing out that I don’t blog for the benefit of the computer science community. As dear as Project COSA is to me, I would rather see it fail if its success must depend on academic approval. If what I write about Alan Turing offends you, then don’t read my stuff. It’s not meant for you. And don’t send me emails to tell me that you don't like it because I don’t care. If I am a kook in your opinion, you are an idiot in mine. That makes us even. I just thought that I would get this little misunderstanding out of the way so I can continue to enjoy my freedom of expression on the Internet. It’s a beautiful thing. To the rest of you who are interested in what I have to say about Turing, I apologize for the delay in posting the second part of this article.

Turing Is the Problem, Not the Solution

In part I, I wrote that Alan Turing is a naked emperor. Consider that the computer industry is struggling with not just one but three major crises [note: there is also a fourth crisis having to do with memory bandwidth]. The software reliability and productivity crises have been around since the sixties. The parallel programming crisis has just recently begun to wreak havoc. It has gotten to the point where the multicore vendors are starting to panic. Turing’s ideas on computation are obviously not helping; otherwise there would be no crises. My thesis, which I defend below, is that they are, in fact, the cause of the industry’s problems, not the solution. What is needed is a new computing model, one that is the very opposite of what Turing proposed, that is, one that models both parallel and sequential processes from the start.


UBM vs. UTM

I have touched on this before in my seminal work on software reliability but I would like to elaborate on it a little to make my point. The computing model that I am proposing is based on an idealized machine that I call the Universal Behaving Machine or UBM for short. It assumes that a computer is a behaving machine that senses and reacts to changes in its environment.
Please read the paragraph on The Hidden Nature of Computing before continuing. Below, I contrast several characteristics of the UBM with those of the UTM. The Turing machine does not provide for it but I will be gracious and use multithreading as the Turing version of parallel processing.

Although multithreading is not part of the UTM, this is the mechanism that multicore processor vendors have adopted as their parallel processing model. Turing’s supporters will argue that parallelism can be simulated in a UTM without threads and they are correct. However, as I explain below, a simulation does not change the sequential nature of the Turing computing model. For an explanation of “non-algorithmic”, see my recent blog entry on the subject.

Simulation Does Not a Computing Model Make

True universality requires that a computing model should handle both serial and parallel computations and events by definition. In other words, both types of computation should be inherent parts of the model. One of the arguments that I invariably get from Turing’s supporters is that the Turing machine is a universal computing model because you can use it to simulate anything, even a parallel computer. This is a rather lame argument because observing that a Turing machine can be used to simulate a parallel computer does not magically transform it into a parallel computing model. This would be like saying that, since a Turing machine can be used to simulate a video game or a chess computer, that it is therefore a video game or a chess-computing model. That is absurd. Simulation does not a model make. Whenever one uses one mechanism to simulate another, one climbs to a new level of abstraction, a new model, one that does not exist at the lower level.

To Model or to Simulate, That Is the Question

The Turing machine is a model for a mechanism that executes a sequence of instructions. It does not model a parallel computer, or a tic-tac-toe program or a spreadsheet or anything else, even if it can be used to simulate those applications. The simulation exists only in the mind of the modeler, not in the underlying mechanism. The fallacy of universality is even more transparent when one realizes that a true parallel machine like the UBM does not have to simulate a Turing machine the way the UTM has to simulate the UBM. The reason is that the UBM can duplicate any computation that a Turing machine can perform. In other words, the UTM is an inherent part of the UBM but the opposite is not true.

The Beginning of the End of the Turing Madness

Thomas Kuhn wrote in his book, “The Structure of Scientific Revolutions” that scientific progress occurs through revolutions or paradigm shifts. Max Planck, himself a scientist, said that "a new scientific truth does not triumph by convincing its opponents and making them see the light, but rather because its opponents eventually die, and a new generation grows up that is familiar with it." Last but not least, Paul Feyerabend wrote the following in Against Method: “… the most stupid procedures and the most laughable results in their domain are surrounded with an aura of excellence. It is time to cut them down to size and give them a more modest position in society.”

I think that all the major problems of the computer industry can be attributed to the elitism and intransigence that is rampant in the scientific community. The peer review system is partly to blame. It is a control mechanism that keeps outsiders at bay. As such, it limits the size of the meme pool in much the same way that incest limits the size of the gene pool in a closed community. Sooner or later, the system engenders monstrous absurdities but the community is blind to it. The Turing machine is a case in point. The point that I am getting at is that it is time to eradicate the Turing cult for the sake of progress in computer science. With the parallel programming crisis in full swing, the computer industry desperately needs a Kuhnian revolution. There is no stopping it. Many reactionaries will fight it teeth and nails but they will fall by the wayside. We are witnessing the beginning of the end of the Turing madness. I say, good riddance.

See Also:

Jeff Raskin - Computers Are Not Turing Machines (pdf)
Half a Century of Crappy Computing
How to Solve the Parallel Programming Crisis
Parallel Computing: Why the Future Is Non-Algorithmic
How to Construct 100% Bug-Free Software

Sunday, June 15, 2008

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

Part II

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 no 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:

Jeff Raskin - Computers Are Not Turing Machines (pdf)
Half a Century of Crappy Computing
How to Solve the Parallel Programming Crisis
Parallel Computing: Why the Future Is Non-Algorithmic