Computation
From Academic Kids

Computation can be defined as finding a solution to a problem from given inputs by means of an algorithm. In turn, the theory of computation, a subfield of computer science and mathematics, provides analysis of problems, inputs, and algorithms.
Contents 
History of computation and computational models
For thousands of years, computing was done with pen and paper, chalk and slate, or even mentally, sometimes with the aid of tables. The theory of computation began early in the twentieth century, before modern electronic computers had been invented. At that time, mathematicians were trying to find which math problems could be solved by simple methods and which could not. The first step was to define what was meant by a "simple method" for solving a problem, implying a need for 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 grammarlike 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 ChurchTuring thesis. In general, questions of what can be computed by various machines are investigated in computability theory.
Theory of computation
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 problemsolving. Contextfree grammars are used to specify programming language syntax. Nondeterministic pushdown automata are another formalism equivalent to contextfree 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.
Further reading
 Michael Garey, and David S. Johnson: Computers and Intractability: A Guide to the Theory of NPCompleteness. New York: W. H. Freeman & Co., 1979. The standard reference on NPComplete 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 secondyear undergraduate computer science students.
 Hopcroft, John E., and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Reading, MA: AddisonWesley, 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 upperlevel undergraduates or beginning graduate students.
 Hartley Rogers, Jr, Theory of Recursive Functions and Effective Computability, MIT Press, 1987, ISBN 0262680521 (paperback)
 The Complexity Zoo (http://www.complexityzoo.com/): A huge list of complexity classes, as reference for experts.
 Computability Logic (http://www.cis.upenn.edu/~giorgi/cl.html): A theory of interactive computation. The main web source on this new subject.
See also
 Computability logic
 Interactive computation
 Important publications in computability
 Open problems in computability
 Calculation
 This article contains some content from an article by Nancy Tinkham (http://www.nupedia.com/article/567/), originally posted on Nupedia.de:Theoretische Informatik
fr:Calculabilité he:חישוביות ja:計算理論 pl:Teoria obliczeń pt:Teoria da computação su:Computation th:การคำนวณ zh:计算理论