acm - an acm publication

Articles

Ubiquity symposium 'What is computation?'
Opening statement

Ubiquity, Volume 2010 Issue November, November 2010 | BY Peter J. Denning 

|

Full citation in the ACM Digital Library  | PDF

Most people understand a computation as a process evoked when a computational agent acts on its inputs under the control of an algorithm. The classical Turing machine model has long served as the fundamental reference model because an appropriate Turing machine can simulate every other computational model known. The Turing model is a good abstraction for most digital computers because the number of steps to execute a Turing machine algorithm is predictive of the running time of the computation on a digital computer. However, the Turing model is not as well matched for the natural, interactive, and continuous information processes frequently encountered today. Other models whose structures more closely match the information processes involved give better predictions of running time and space. Models based on transforming representations may be useful.




Connection Failure

COMMENTS

"So, what is the problem with the Turing model? To many, the Turing machine model is a poor representation of the systems they are interested in. For example, a DNA molecule being transcribed does not resemble a moveable control unit on an infinite tape. The theorems about running times of algorithms on Turing machines do not help mathematicians solving continuous models predict the running times of their models". You have my permission to abandon the Turing Machine model and replace it by anything else which works for you. But I am guessing that "a DNA molecule being transcribed" is modelled quite well by "a moveable control unit on an infinite tape". ---------------------------------------------------------------- "The theorems about running times of algorithms on Turing machines do not help mathematicians solving continuous models predict the running times of their models". I agree that it may turn out to be impractical to use a Turing machine for serious work. But isn't it a simple model of a CPU with an absurdly inefficient storage device (similar to magnetic tape, which was in fact used widely in the 1970's). There is nothing to stop a new Ken Thompson from inventing a new machine. It will be describable as interacting finite state machines, and therefore it will be describable as interacting Turing machines. Maybe you could leave out the infinite tape, and replace it by ports which can store input and output from other devices.

— richard mullins, Fri, 05 Feb 2016 22:33:26 UTC

Thanks for the great Post  very COOL!!!

— computer sales, Tue, 30 Nov 2010 20:30:50 UTC

POST A COMMENT
Leave this field empty