Skip to main content

abstract computability theory

abstract computability theory 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, modeling 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 fininte 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.

Cite this article
Pick a style below, and copy the text for your bibliography.

  • MLA
  • Chicago
  • APA

"abstract computability theory." A Dictionary of Computing. . Encyclopedia.com. 21 Aug. 2018 <http://www.encyclopedia.com>.

"abstract computability theory." A Dictionary of Computing. . Encyclopedia.com. (August 21, 2018). http://www.encyclopedia.com/computing/dictionaries-thesauruses-pictures-and-press-releases/abstract-computability-theory

"abstract computability theory." A Dictionary of Computing. . Retrieved August 21, 2018 from Encyclopedia.com: http://www.encyclopedia.com/computing/dictionaries-thesauruses-pictures-and-press-releases/abstract-computability-theory

Learn more about citation styles

Citation styles

Encyclopedia.com gives you the ability to cite reference entries and articles according to common styles from the Modern Language Association (MLA), The Chicago Manual of Style, and the American Psychological Association (APA).

Within the “Cite this article” tool, pick a style to see how all available information looks when formatted according to that style. Then, copy and paste the text into your bibliography or works cited list.

Because each style has its own formatting nuances that evolve over time and not all information is available for every reference entry or article, Encyclopedia.com cannot guarantee each citation it generates. Therefore, it’s best to use Encyclopedia.com citations as a starting point before checking the style against your school or publication’s requirements and the most-recent information available at these sites:

Modern Language Association

http://www.mla.org/style

The Chicago Manual of Style

http://www.chicagomanualofstyle.org/tools_citationguide.html

American Psychological Association

http://apastyle.apa.org/

Notes:
  • Most online reference entries and articles do not have page numbers. Therefore, that information is unavailable for most Encyclopedia.com content. However, the date of retrieval is often important. Refer to each style’s convention regarding the best way to format page numbers and retrieval dates.
  • In addition to the MLA, Chicago, and APA styles, your school, university, publication, or institution may have its own requirements for citations. Therefore, be sure to refer to those guidelines when editing your bibliography or works cited list.