The theory of computation, a subfield of computer science and mathematics, 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 find which math problems can be solved by simple methods and which can't. The first step was to define what they meant by a "simple method" for solving a problem. In other words, they needed a formal model of computation.
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,
recursive functions, uses functions and function composition to operate
on numbers. The lambda calculus uses a similar approach. 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. Indeed, it is widely
believed that all "proper" formalizations of the concept of algorithm will be equivalent in power
to Turing machines; this is known as the Church-Turing thesis. In general, questions of what
can be computed by various machines are investigated in computability theory.
The theory of computation studies these models of general computation, along with the limits
of computing: Which problems are (provably) unsolvable by a computer? (See the
halting problem and the Post correspondence problem.) Which problems are solvable by a computer, but require
such an enormously long time to compute that the solution is impractical? (See
Presburger arithmetic.) Can it be harder to solve a problem than to check a given solution?
(See complexity classes P and NP). In general, questions concerning the time or space
requirements of given problems are investigated in complexity theory.
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.
Another formalism mathematically equivalent to regular expressions,
Finite automata are used in circuit design and in some kinds of
problem-solving. Context-free grammars are used to specify
programming language syntax. Non-deterministic pushdown automata are another
formalism equivalent to context-free grammars.
Primitive recursive functions are a defined
subclass of the recursive functions.
Different models of computation have the ability to do different tasks. One way to
measure the power of a computational model is to study the class of
formal languages that the model can generate; this leads to the
Chomsky hierarchy of languages.
The following table shows some of the classes of problems (or languages, or
grammars) that are considered in computability theory (blue) and complexity theory
(green). If class X is a strict subset of Y, then X is shown below Y, with a dark
line connecting them. If X is a subset, but it is unknown whether they are equal sets,
then the line is lighter and is dotted.
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 Complexity Zoo (http://www.cs.berkeley.edu/~aaronson/zoo): A huger list of complexity classes, as reference for experts.
This article contains some content from an article by Nancy Tinkham
), originally posted on Nupedia
. This article is open content
All Wikipedia text
is available under the
terms of the GNU Free Documentation License