Computability

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.

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.

...
Wikipedia