Ubiquity symposium 'What is computation?'
Open Access
- 1 November 2010
- journal article
- forum
- Published by Association for Computing Machinery (ACM) in Ubiquity
- Vol. 2010 (November)
Abstract
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.Keywords
This publication has 17 references indexed in Scilit:
- Recent progress in quantum algorithmsCommunications of the ACM, 2010
- The profession of ITBeyond computational thinkingCommunications of the ACM, 2009
- The Computing Field: Structure2009
- Computing is a natural scienceCommunications of the ACM, 2007
- Computational thinkingCommunications of the ACM, 2006
- The structure of the “THE”-multiprogramming systemCommunications of the ACM, 1968
- Curriculum 68: Recommendations for academic programs in computer scienceCommunications of the ACM, 1968
- Computer ScienceScience, 1967
- Programming semantics for multiprogrammed computationsCommunications of the ACM, 1966
- Finite combinatory processes—formulationThe Journal of Symbolic Logic, 1936