Computational Complexity

Tuesday, April 08, 2003

 
Computation Beyond Turing Machines?

Posted by Lance

In the April issue of the Communications of the ACM, Peter Wegner and Dina Goldin have a technical opinion entitled Computation Beyond Turing Machines. From the article: "Turing machines are inappropriate as a universal foundation for computational problem solving and computer science is a fundamentally non-mathematical discipline". Those are fighting words and luckily I have this weblog to fight back.

Wegner and Goldin's main argument is summed up towards the end of the article. "In the last two decades, computing technology has shifted from mainframes and microstations to networks and wireless devices, with the corresponding shift in applications from number crunching and data processing to embedded systems and graphical user interfaces. We believe it is no longer premature to encompass interaction as part of computation. A paradigm shift is necessary in our notion of computational problem solving, so it can provide a complete model for the services of today's computing systems and software agents."

In here they have a good point. The area of human-computer interaction is sometimes more art than science. But while the basic model of the Turing machine is a sequential device, theoretical computer scientists have come up with variations that capture networks and other aspects of interaction, some of which are described in the Wegner-Goldin article. And all of these new models can be simulated by Turing machines. The Turing machine remains supreme as the model that captures all computation.

Far more troubling is the following: "Gödel had shown in 1931 that logic cannot model mathematics and Turing showed that neither logic nor algorithms can completely model computing and human thought." This is a complete misreading of Gödel and Turing. Not every mathematical statement has a logical proof, but logic does capture everything we can prove in mathematics, which is really what matters. Likewise, Turing machines captures everything we can compute. And what we can compute is what computer science is all about.

10:02 AM #

1.  Joe says:  
   
   I just ran across the cited article and my reaction was quite similar. I'll have to see a much better grounded argument before I'll be ready to accept that modern computers can compute problems a turing machine cannot.
   

   9:55 PM, April 22, 2007