Peter J. Denning
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.
- Atchison, William, Samuel Conte, John Hamblen, Thomas Hull, Thomas Keenan, William Kehl, Edward McCluskey, Silvio Navarro, Werner Rheinboldt, Earl Schweppe, William Viavant, and David Young. "Curriculum 68: Recommends for academic programs in computer science". Communications of ACM 11, 3 (March 1968), 151-197. Google Scholar
Digital Library
- Arden, B. W. What Can Be Automated: Computer Science and Engineering Research Study (COSERS). MIT Press (1983). Google ScholarDigital Library
- Bacon, Dave, and Wim van Dam. "Recent progress in quantum algorithms". Communications of ACM 53, 2 (February 2010), 84-93. Google ScholarDigital Library
- Baltimore, D. "How Biology Became an Information Science." In The Invisible Future (P. Denning, Ed.). McGraw-Hill (2001), 43-56. Google ScholarDigital Library
- Carse, James. Finite and Infinite Games. Random House (1986).Google Scholar
- Chaitin, G. Meta Math!: The Quest for Omega. Vintage (2006). Google ScholarDigital Library
- Church, A. "A Note on the Entscheidungsproblem." Am. J. of Mathematics 58 (1936), 345-363.Google ScholarCross Ref
- Coffman, E. G., Jr., and Peter Denning. Operating Systems Theory. Prentice-Hall (1973). Google ScholarDigital Library
- Denning, P. Computing is a natural science. Communications of the ACM 50, 7 (July 2007), 15-18. Google ScholarDigital Library
- Denning, P. "Computing Field: Structure". In Wiley Encyclopedia of Computer Science and Engineering (B. Wah, Ed.). Wiley Interscience (2008).Google Scholar
- Denning, P. "Beyond Computational Thinking". Communications of the ACM 52, 6 (June 2009), 28- 30. Google ScholarDigital Library
- Denning, P., and P. Freeman. "Computing's Paradigm". Communications of the ACM 52, 12 (December 2009), 28-30. Google ScholarDigital Library
- Denning, P., and P. Rosenbloom. Computing: The fourth great domain of science. Communications of the ACM 52, 9 (September 2009). Google ScholarDigital Library
- Dennis, Jack, and Earl Van Horn. "Programming Semantics for Multiprogrammed Computations." Communications of the ACM 9, 3 (March 1966), 143-155. Google ScholarDigital Library
- Dijkstra, Edsger. "The Structure of THE Multiprogramming System." Communications of the ACM 11, 5 (May 1968), 341-346. Google ScholarDigital Library
- Gödel, Kurt. "On undecidable propositions of formal mathematics". Lectures at the Institute for Advanced Study, Princeton, NJ (1934). Documented in http://en.wikipedia.org/wiki/Kurt_GodelGoogle Scholar
- Goldin, D., S. Smolka, and P. Wegner (Eds.). Interactive Computation: The New Paradigm. Springer (2006). Google ScholarDigital Library
- Hazen, R. Genesis: The Scientific Quest for Life's Origins. Joseph Henry Press (2007).Google Scholar
- Hofstadter, Douglas. Metamagical Themas: Questing for the Essence of Mind and Pattern. Basic Books (1985). See his essay on "The Genetic Code: Arbitrary?"Google Scholar
- Newell, A., A. J. Perlis, and Herbert A. Simon, "Computer Science," letter in Science 157(3795):1373- 1374, September 1967.Google ScholarCross Ref
- Organick, Elliot I. Computer Systems Organization: The B5700/B6700. ACM Monograph Series, 1973. LCN: 72-88334. Google ScholarDigital Library
- Perlis, A. J. "The Computer in the University". In Computers and the World of the Future (M. Greenberger, ed.). MIT Press (1962), 180-219.Google Scholar
- Polya, G. How To Solve It. Princeton University Press (1957).Google Scholar
- Post, E. Finite Combinatory Processes - Formulation 1. J. Symbolic Logic 1 (1936), 103-105.Google ScholarCross Ref
- Rocchi, P. Logic of Analog and Digital Machines. Nova Publishers (2010). Google ScholarDigital Library
- Rosenbloom, P. S. A new framework for computer science and engineering. IEEE Computer (November 2004), 31-36. Google ScholarDigital Library
- Shannon, C., and W. Weaver. The Mathematical Theory of Communication. University of Illinois Press (1998). First edition 1949. Shannon's original paper is available on the Web: http://cm.belllabs.com/cm/ms/what/shannonday/paper.html Google ScholarDigital Library
- Simon, H. The Sciences of the Artificial. MIT Press (1st ed. 1969, 3rd ed. 1996). Google ScholarDigital Library
- Turing, A. "On Computable Numbers, With an Application to the Entscheidungsproblem." Proc. of the London Mathematical Society, series 2, 42 (1937), 230-265.Google Scholar
- Traub, J. F., and H. Wozniakowski. A General Theory of Optimal Algorithms. Academic Press (1980).Google Scholar
- Wing, J. Computational thinking. Communications of the ACM 49, 3 (March 2006), 33-35. Google ScholarDigital Library
- Wolfram, S. A New Kind of Science. Wolfram Media (2002). Google ScholarDigital Library
Recommendations
Ubiquity symposium 'What is computation?': Computation is process
Various authors define forms of computation as specialized types of processes. As the scope of computation widens, the range of such specialties increases. Dennis J. Frailey posits that the essence of computation can be found in any form of process, ...
Ubiquity symposium 'What is computation?': Computation is symbol manipulation
In the second in the series of articles in the Ubiquity Symposium What is Computation?, Prof. John S. Conery of the University of Oregon explains why he believes computation can be seen as symbol manipulation. For more articles in this series, see table ...
Ubiquity symposium: Natural Computation
In this twelfth piece to the Ubiquity symposium discussing What is computation? Erol Gelenbe reviews computation in natural systems, focusing mainly on biology and citing examples of the computation that is inherent in chemistry, natural selection, gene ...
Comments