Computability is the ability to solve a problem by an effective procedure. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem.
The most widely studied models of computability are the Turing-computable and μ-recursive functions, and the lambda calculus, all of which have computationally equivalent power. Other forms of computability are studied as well: computability notions weaker than Turing machines are studied in automata theory, while computability notions stronger than Turing machines are studied in the field of hypercomputation.
Problems
A central idea in computability is that of a (computational) problem, which is a task whose computability can be explored.
There are two key types of problems: A decision problem fixes a set S, which may be a set of strings, natural numbers, or other objects taken from some larger set U. A particular instance of the problem is to decide, given an element u of U, whether u is in S. For example, let U be the set of natural numbers and S the set of prime numbers. The corresponding decision problem corresponds to primality testing. A function problem consists of a function f from a set U to a set V. An instance of the problem is to compute, given an element u in U, the corresponding element f(u) in V. For example, U and V may be the set of all finite binary strings, and f may take a string and return the string obtained by reversing the digits of the input (so f(0101) = 1010). Other types of problems include search problems and optimization problems.
One goal of computability theory is to determine which problems, or classes of problems, can be solved in each model of computation.
Formal models of computation
A model of computation is a formal description of a particular type of computational process. The description often takes the form of an abstract machine that is meant to perform the task at hand. General models of computation equivalent to a Turing machine (see Church–Turing thesis) include:
Lambda calculus A computation consists of an initial lambda expression (or two if you want to separate the function and its input) plus a finite sequence of lambda terms, each deduced from the preceding term by one application of beta reduction. Combinatory logic A concept which has many similarities to -calculus, but also important differences exist (e.g. fixed point combinator Y has normal form in combinatory logic but not in -calculus). Combinatory logic was developed with great ambitions: understanding the nature of paradoxes, making foundations of mathematics more economic (conceptually), eliminating the notion of variables (thus clarifying their role in mathematics). μ-recursive functions A computation consists of a μ-recursive function, i.e. its defining sequence, any 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 the functions and appear, then terms of the form or 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 μ-recursion. For instance if , then for to appear, terms like and must occur above. The computation terminates only if the final term gives the value of the recursive function applied to the inputs. String rewriting systems Includes Markov algorithms, that use grammar-like rules to operate on strings of symbols; also Post canonical system. Register machine A theoretical idealization of a computer. There are several variants. In most of them, each register can hold a natural number (of unlimited size), and the instructions are simple (and few in number), e.g. only decrementation (combined with conditional jump) and incrementation exist (and halting). The lack of the infinite (or dynamically growing) external store (seen at Turing machines) can be understood by replacing its role with Gödel numbering techniques: the fact that each register holds a natural number allows the possibility of representing a complicated thing (e.g. a sequence, or a matrix etc.) by an appropriate huge natural number — unambiguity of both representation and interpretation can be established by number theoretical foundations of these techniques. Turing machine Also similar to the finite state machine, except that the input is provided on an execution "tape", which the Turing machine can read from, write to, or move back and forth past its read/write "head". The tape is allowed to grow to arbitrary size. The Turing machine is capable of performing complex calculations which can have arbitrary duration. This model is perhaps the most important model of computation in computer science, as it simulates computation in the absence of predefined resource limits. Multitape Turing machine Here, there may be more than one tape; moreover there may be multiple heads per tape. Surprisingly, any computation that can be performed by this sort of machine can also be performed by an ordinary Turing machine, although the latter may be slower or require a larger total region of its tape. P′′ Like Turing machines, P′′ uses an infinite tape of symbols (without random access), and a rather minimalistic set of instructions. But these instructions are very different, thus, unlike Turing machines, P′′ does not need to maintain a distinct state, because all “memory-like” functionality can be provided only by the tape. Instead of rewriting the current symbol, it can perform a modular arithmetic incrementation on it. P′′ has also a pair of instructions for a cycle, inspecting the blank symbol. Despite its minimalistic nature, it has become the parental formal language of an implemented and (for entertainment) used programming language called Brainfuck.
In addition to the general computational models, some simpler computational models are useful for special, restricted applications. Regular expressions, for example, specify string patterns in many contexts, from office productivity software to programming languages. Another formalism mathematically equivalent to regular expressions, Finite automata are used in circuit design and in some kinds of problem-solving. Context-free grammars specify programming language syntax. Non-deterministic pushdown automata are another formalism equivalent to context-free grammars.
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; in such a way the Chomsky hierarchy of languages is obtained.
Other restricted models of computation include: Deterministic finite automaton (DFA) Also called a finite-state machine. All real computing devices in existence today can be modeled as a finite-state machine, as all real computers operate on finite resources. Such a machine has a set of states, and a set of state transitions which are affected by the input stream. Certain states are defined to be accepting states. An input stream is fed into the machine one character at a time, and the state transitions for the current state are compared to the input stream, and if there is a matching transition the machine may enter a new state. If at the end of the input stream the machine is in an accepting state, then the whole input stream is accepted. Nondeterministic finite automaton (NFA) Another simple model of computation, although its processing sequence is not uniquely determined. It can be interpreted as taking multiple paths of computation simultaneously through a finite number of states. However, it is possible to prove that any NFA is reducible to an equivalent DFA. Pushdown automaton Similar to the finite state machine, except that it has available an execution stack, which is allowed to grow to arbitrary size. The state transitions additionally specify whether to add a symbol to the stack, or to remove a symbol from the stack. It is more powerful than a DFA due to its infinite-memory stack, although only the top element of the stack is accessible at any time.
Power of automata With these computational models in hand, we can determine what their limits are. That is, what classes of languages can they accept?
Power of finite-state machines
Computer scientists call any language that can be accepted by a finite-state machine a regular language. Because of the restriction that the number of possible states in a finite state machine is finite, we can see that to find a language that is not regular, we must construct a language that would require an infinite number of states.
An example of such a language is the set of all strings consisting of the letters 'a' and 'b' which contain an equal number of the letter 'a' and 'b'. To see why this language cannot be correctly recognized by a finite state machine, assume first that such a machine M exists. M must have some number of states n. Now consider the string x consisting of 'a's followed by 'b's.
As M reads in x, there must be some state in the machine that is repeated as it reads in the first series of 'a's, since there are 'a's and only n states by the pigeonhole principle. Call this state S, and further let d be the number of 'a's that our machine read in order to get from the first occurrence of S to some subsequent occurrence during the 'a' sequence. We know, then, that at that second occurrence of S, we can add in an additional d (where ) 'a's and we will be again at state S. This means that we know that a string of 'a's must end up in the same state as the string of 'a's. This implies that if our machine accepts x, it must also accept the string of 'a's followed by 'b's, which is not in the language of strings containing an equal number of 'a's and 'b's. In other words, M cannot correctly distinguish between a string of equal number of 'a's and 'b's and a string with 'a's and 'b's.
We know, therefore, that this language cannot be accepted correctly by any finite-state machine, and is thus not a regular language. A more general form of this result is called the Pumping lemma for regular languages, which can be used to show that broad classes of languages cannot be recognized by a finite state machine.
Power of pushdown automata Computer scientists define a language that can be accepted by a pushdown automaton as a Context-free language, which can be specified as a Context-free grammar. The language consisting of strings with equal numbers of 'a's and 'b's, which we showed was not a regular language, can be decided by a push-down automaton. Also, in general, a push-down automaton can behave just like a finite-state machine, so it can decide any language which is regular. This model of computation is thus strictly more powerful than finite state machines.
However, it turns out there are languages that cannot be decided by push-down automaton either. The result is similar to that for regular expressions, and won't be detailed here. There exists a Pumping lemma for context-free languages. An example of such a language is the set of prime numbers.
Power of Turing machines Turing machines can decide any context-free language(language accepted by Push Down Automata and Context Free Grammer), in addition to languages not decidable by a push-down automaton, such as the language consisting of prime numbers. It is therefore a strictly more powerful model of computation.