The theory of functions that can be computed by algorithms on any algebra. Its aim is to explore the scope and limits of computation on any kind of data. It is a generalization to arbitrary many sorted algebras of the theory of the effectively calculable or recursive functions on the natural numbers.
Abstract computability theory starts with an analysis and classification of many models of computation and specification that apply to algebras. This reveals the essential features of methods, and results in a generalized Church–Turing thesis that establishes which functions on an abstract data type are programmable by a deterministic programming language. Comparisons can be made between computations on different algebras, modelling data types and their implementations. The theory also provides a foundation for new theories of computation for special data types, such as algebras of real numbers, which can be used in applications.
The while programming language is a simple example of a method for computing functions on any many-sorted algebra A (that possesses the Booleans). On the natural numbers it can compute all partial recursive functions. Computation is based on the operations of the algebra—sequencing, branching, and iteration—and has available a limited means of searching A. However, a vital missing component is the capacity to compute with finite sequences of data from A. On the natural numbers finite sequences can be simulated using pairing functions, but it is not possible to simulate finite sequences on an algebra A. Finite sequences and operations for every data set in A are therefore added to A to make a new algebra A*. It turns out that while programs on A* (i.e. while programs equipped with finite sequences) have all the essential properties of the computable functions on A. This class of functions is the subject of the generalized Church-Turing thesis.
Most of the main results in the theory of computability on the natural numbers can also be proved for abstract computability theory on any finite generated minimal algebra.