Computation

From Freepedia

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 immediatly 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 instead replaced by less cumbersome informal arguments often involving appeals to the Church-Turing thesis. Since most commonly used models of computation are equivalent the choice of formalization of computation is usually unimportant.

In addition to giving a rigorous foundation of the notion of computable the formal notion of a computation also allows one to show that it is possible computably mimic the operation of an algorithm. Phrased in terms of turing machines this means it is possible to create a universal turing machine but similar results can be established in any equivalent model of computation.

Contents 1 Formal Definitions of Computation 2 History of computation and computational models 3 Theory of Computation 4 Further reading 5 See also

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 seperate the function and its input) plus finite sequence of lambda terms each preceding from the former by one application of Beta reduction

If your model of computation is calculation by turing machines a computatation would be a particular turing machine M and input value and a finite sequence of states of M plus its accompanying tape, i.e., triples of tape, 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 recursive functions a computation would be a recursive function, e.g., 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 of follow from the entries above 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 then the Actor model and process calculi that have raised additional issues about what is computable (see Actor model, mathematical logic, and quantum 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 new 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.