Computability is the ability to solve a problem in an effective manner. 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.
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:
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.
Main article: Model 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:
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 is the Chomsky hierarchy of languages is obtained.
Other restricted models of computation include:
With these computational models in hand, we can determine what their limits are. That is, what classes of languages can they accept?
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.
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.
Turing machines can decide any context-free language, 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.
Because Turing machines have the ability to "back up" in their input tape, it is possible for a Turing machine to run for a long time in a way that is not possible with the other computation models previously described. It is possible to construct a Turing machine that will never finish running (halt) on some inputs. We say that a Turing machine can decide a language if it eventually will halt on all inputs and give an answer. A language that can be so decided is called a recursive language. We can further describe Turing machines that will eventually halt and give an answer for any input in a language, but which may run forever for input strings which are not in the language. Such Turing machines could tell us that a given string is in the language, but we may never be sure based on its behavior that a given string is not in a language, since it may run forever in such a case. A language which is accepted by such a Turing machine is called a recursively enumerable language.
The Turing machine, it turns out, is an exceedingly powerful model of automata. Attempts to amend the definition of a Turing machine to produce a more powerful machine have surprisingly met with failure. For example, adding an extra tape to the Turing machine, giving it a two-dimensional (or three- or any-dimensional) infinite surface to work with can all be simulated by a Turing machine with the basic one-dimensional tape. These models are thus not more powerful. In fact, a consequence of the Church–Turing thesis is that there is no reasonable model of computation which can decide languages that cannot be decided by a Turing machine.
The question to ask then is: do there exist languages which are recursively enumerable, but not recursive? And, furthermore, are there languages which are not even recursively enumerable?
Main article: Halting problem
The halting problem is one of the most famous problems in computer science, because it has profound implications on the theory of computability and on how we use computers in everyday practice. The problem can be phrased:
Here we are asking not a simple question about a prime number or a palindrome, but we are instead turning the tables and asking a Turing machine to answer a question about another Turing machine. It can be shown (See main article: Halting problem) that it is not possible to construct a Turing machine that can answer this question in all cases.
That is, the only general way to know for sure if a given program will halt on a particular input in all cases is simply to run it and see if it halts. If it does halt, then you know it halts. If it doesn't halt, however, you may never know if it will eventually halt. The language consisting of all Turing machine descriptions paired with all possible input streams on which those Turing machines will eventually halt, is not recursive. The halting problem is therefore called non-computable or undecidable.
An extension of the halting problem is called Rice's theorem, which states that it is undecidable (in general) whether a given language possesses any specific nontrivial property.
The halting problem is easy to solve, however, if we allow that the Turing machine that decides it may run forever when given input which is a representation of a Turing machine that does not itself halt. The halting language is therefore recursively enumerable. It is possible to construct languages which are not even recursively enumerable, however.
A simple example of such a language is the complement of the halting language; that is the language consisting of all Turing machines paired with input strings where the Turing machines do not halt on their input. To see that this language is not recursively enumerable, imagine that we construct a Turing machine M which is able to give a definite answer for all such Turing machines, but that it may run forever on any Turing machine that does eventually halt. We can then construct another Turing machine that simulates the operation of this machine, along with simulating directly the execution of the machine given in the input as well, by interleaving the execution of the two programs. Since the direct simulation will eventually halt if the program it is simulating halts, and since by assumption the simulation of M will eventually halt if the input program would never halt, we know that will eventually have one of its parallel versions halt. is thus a decider for the halting problem. We have previously shown, however, that the halting problem is undecidable. We have a contradiction, and we have thus shown that our assumption that M exists is incorrect. The complement of the halting language is therefore not recursively enumerable.
A number of computational models based on concurrency have been developed, including the parallel random-access machine and the Petri net. These models of concurrent computation still do not implement any mathematical functions that cannot be implemented by Turing machines.
The Church–Turing thesis conjectures that there is no effective model of computing that can compute more mathematical functions than a Turing machine. Computer scientists have imagined many varieties of hypercomputers, models of computation that go beyond Turing computability.
Main article: Zeno machine
Imagine a machine where each step of the computation requires half the time of the previous step (and hopefully half the energy of the previous step...). If we normalize to 1/2 time unit the amount of time required for the first step (and to 1/2 energy unit the amount of energy required for the first step...), the execution would require
time unit (and 1 energy unit...) to run. This infinite series converges to 1, which means that this Zeno machine can execute a countably infinite number of steps in 1 time unit (using 1 energy unit...). This machine is capable of deciding the halting problem by directly simulating the execution of the machine in question. By extension, any convergent infinite [must be provably infinite] series would work. Assuming that the infinite series converges to a value n, the Zeno machine would complete a countably infinite execution in n time units.
Main article: Oracle machine
So-called Oracle machines have access to various "oracles" which provide the solution to specific undecidable problems. For example, the Turing machine may have a "halting oracle" which answers immediately whether a given Turing machine will ever halt on a given input. These machines are a central topic of study in recursion theory.
Even these machines, which seemingly represent the limit of automata that we could imagine, run into their own limitations. While each of them can solve the halting problem for a Turing machine, they cannot solve their own version of the halting problem. For example, an Oracle machine cannot answer the question of whether a given Oracle machine will ever halt.