admin, 03:51 UTC, Mon 07 of Nov, 2011: Does this site need a redesign yet?
admin, 10:38 UTC, Sat 05 of Sep, 2009: Good things coming soon!
admin, 03:42 UTC, Fri 03 of Aug, 2007: Don't give up the ship!
admin, 02:51 UTC, Tue 03 of Jul, 2007: Test.
TypewriterKing > Nupedia - The Theory of Computation
The theory of computation is the study of mathematical models of computing, independent of any particular computer hardware. It has its origins early in the twentieth century, before modern electronic computers had been invented. At that time, mathematicians were trying to design a computing machine that would automate the process of computing, in much the same way that the machines of the Industrial Revolution had automated many agricultural and manufacturing processes. An essential step in automating computing is deciding what steps are involved in computing: that is, what kind of memory is available (e.g., a single string, a fixed number of registers storing numbers, or an infinitely long tape storing characters), and what kinds of computational steps can be performed on the data in memory.
Several different computational models were devised by these early researchers. One model, the Turing machine, stores characters on an infinitely long tape, with one square at any given time being scanned by a read/write head. Another model, partial recursive functions, uses functions and function composition to operate on numbers. Still others, including Markov algorithms and Post systems, use grammar-like rules to operate on strings. All of these formalisms were shown to be equivalent in computational power — that is, any computation that can be performed with one can be performed with any of the others. They are also equivalent in power to the familiar electronic computer, if one pretends that electronic computers have infinite memory.
The theory of computation studies these models of general computation, along with the limits of computing: Which problems are (provably) unsolvable by a computer? Which problems are solvable by a computer, but require such an enormously long time to compute that the solution is impractical?
In addition to the general computational models, some simpler computational models are useful for special, restricted applications. Regular expressions, for example, are used to specify string patterns in UNIX and in some programming languages such as Perl. Finite automata are used in circuit design and in some kinds of problem-solving. Context-free grammars are used to specify programming language syntax. The theory of computation includes the study of these simpler models as well as the more general models.
For Further Reading
Garey, Michael R., and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. The standard reference on NP-Complete problems - an important category of problems whose solutions appear to require an impractically long time to compute.
Hein, James L. Theory of Computation. Sudbury, MA: Jones & Bartlett, 1996. A gentle introduction to the field, appropriate for second-year undergraduate computer science students.
Hopcroft, John E., and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Reading, MA: Addison-Wesley?, 1979. One of the standard references in the field.
Taylor, R. Gregory. Models of Computation. New York: Oxford University Press, 1998. An unusually readable textbook, appropriate for upper-level undergraduates or beginning graduate students.
The content on this page is licensed under the terms of the LicensePage.