Computation
From Exampleproblems
Informally, a computation is what an algorithm performs when transforming inputs into outputs (if it halts). For instance, your computer is performing a computation whenever you run a program.
More formally, a computation is a sequence of intermediate steps in the evaluation of an algorithm in some model of computation, each step immediately following from the previous according to the rules provided for the model of computation. These formal definitions are used to give a rigorous basis to computability theory and computational complexity theory. In practice, the formal notion of a computation is rarely mentioned after the theory is introduced, and is instead replaced by less cumbersome informal arguments often involving appeals to the Church-Turing thesis. The choice of a formalization of computation is usually unimportant since most of the commonly used models of computation are equivalent.
In addition to giving a rigorous foundation for the notion of "computable" objects, formal notions of computation also allow one to show that it is possible to computably mimic the operation of an algorithm. Phrased in terms of Turing machines, this means it is possible to create a universal Turing machine; similar results can be established in any equivalent model of computation.
Contents |
Formal definitions of computation
For instance, if your model of computation is the lambda calculus, a computation would be an initial lambda expression (or two if you want to separate the function and its input) plus finite sequence of lambda terms, each deduced from the preceding term by one application of Beta reduction.
If your model of computation is represented by a Turing machine M, a computation would consist of an input value and a finite sequence of states of M, plus its accompanying "tape", i.e., triples of tape state, head position, and machine state. The initial state must have the Turing machine in the initial state and the input written on the tape. The computation has terminated only if the final triple in the sequence is in a final state; otherwise it is a partial computation. See the formal definition of a one tape Turing machine for an explanation of these concepts.
If your model of computation is based on recursive functions, a computation would be a recursive function, i.e. its defining sequence, an input value(s) and a sequence of recursive functions appearing in the defining sequence with inputs and outputs. Thus, if in the defining sequence of a recursive function f(x) the functions g(x) an h(x,y) appear, then terms of the form 'g(5)=7' or 'h(3,2)=10' might appear. Each entry in this sequence needs to be an application of a basic function or follow from the entries above by using composition, primitive recursion or mu recursion. For instance if f(x)=h(x,g(x)), then for 'f(5)=3' to appear, terms like 'g(5)=6' and 'h(3,6)=3' must occur above. The computation terminates only if the final term gives the value of the recursive function applied to the inputs.
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 tag 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 unbounded 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.
More recently, theories of concurrent computation have been developed, including Petri nets and the Actor model and process calculi that have raised additional issues about what is computable (see Actor model, mathematical logic, and physics).
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 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.
Further reading
- Sipser, Michael: "Introduction to the Theory of Computation." ISBN: 053494728X. A popular book on introduction to Computation written by the professor who teaches the graduate version of the course at MIT.
- 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.
- Hartley Rogers, Jr, Theory of Recursive Functions and Effective Computability, MIT Press, 1987, ISBN 0-262-68052-1 (paperback)
- Computability Logic: A theory of interactive computation. The main web source on this subject.
See also
- Computability logic
- Interactive computation
- Important publications in computability
- Open problems in computability
- Calculation
- Model-based computing
- Ptolemy Project
- This article contains some content from an article by Nancy Tinkham, originally posted on Nupedia.de:Theoretische Informatik
fr:Calculabilité he:חישוביות ja:計算理論 lb:Theoretesch Informatik pl:Teoria obliczeń pt:Teoria da computação su:Computation th:การคำนวณ zh:计算理论
