Computability is the ability to solve a problem in an effective manner.
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.
The description often takes the form of an abstract machine that is meant to perform the task at hand.
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.
Non-deterministic pushdown automata are another formalism equivalent to context-free grammars.
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.
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.
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.
The result is similar to that for regular expressions, and won't be detailed here.
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.
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.
The Turing machine, it turns out, is an exceedingly powerful model of automata.
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.
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.
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.
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.
A number of computational models based on concurrency have been developed, including the parallel random-access machine and the Petri net.
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...).
These machines are a central topic of study in recursion theory.