What is computation? (Final v5)
Loading...
Authors
Denning, Peter J.
Subjects
CACM IT Profession Columns
Advisors
Date of Issue
2010-08
Date
8/26/2010
Publisher
Language
Abstract
Most people understand a computation as a process evoked when a computational model (or computational agent) acts on its inputs under the
control of an algorithm to produce its results. 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 more closely
match the information processes involved and give better predictions of running
time and space.
Type
Description
The standard reference model for computation, the Turing machine, is a powerful model for digital computers and it can simulate every other computation model ever proposed. Yet the Turing machine information process -- execution sequences of machine configurations -- is not as well matched for the natural, interactive, and continuous information processes frequently encountered today. Other models more closely match the information processes involved and give better predictions of running time and space.
A Ubiquity Symposium Opening Statement FINAL v5– 8/26/10
A Ubiquity Symposium Opening Statement FINAL v5– 8/26/10
Series/Report No
Department
Computer Science (CS)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
What is computation? (Ubiquity September 2010) The standard reference model for computation, the Turing machine, is a powerful model for digital computers and it can simulate every other computation model ever proposed. Yet the Turing machine information process -- execution sequences of machine configurations -- is not as well matched for the natural, interactive, and continuous information processes frequently encountered today. Other models more closely match the information processes involved and give better predictions of running time and space.
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.