Skip to main content

computable algebra

computable algebra An algebra that can be faithfully implemented or represented on a computer, in principle. The notion is made mathematically precise using the theory of the effectively computable functions on the set of natural numbers (and the Church–Turing thesis).

An algebra is computable if (a) there is a mapping α : Ω → A, called a numbering, that uses a recursive set Ω of natural numbers to represent, or code, the set A of elements of the algebra;(b) there are recursive functions on numbers that track the operations of the algebra in the set Ω of natural number codes;(c) there is a recursive function that can decide whether or not two numbers in Ω code the same element of A.

The idea in (b) of tracking operations in the code set is formulated by a commutative diagram depicting an equation: for each operation σ : AkA

of the algebra there is a recursive function f : Ωk → Ω

such that σ(α(x1), …, α(xk)) = α(f(x1, …, xk))

for all x1,…,xk ∈ Ω. The idea of deciding equality in A is formulated by the relation nα m α(n) = α(m) for n,m ∈ Ω

A closely associated concept is that of a semicomputable algebra; this satisfies properties (a) and (b) above, and a third condition, weaker than (c), that whether or not two numbers in the set Ω code the same element of A is recursively enumerable, rather than recursively decidable.

The concepts of computable and semicomputable algebras are used to establish the scope and limits of digital computation. Some fundamental completeness theorems link these algebras with equational specifications and their properties: (1) an algebra is semicomputable if and only if it can be defined uniquely by a finite set of equations, possibly involving extra or hidden functions and sorts, and using initial-algebra semantics;(2) an algebra is computable if and only if it can be defined uniquely by a finite set of equations (possibly using hidden functions) whose associated term rewriting system has the Church–Rosser and strong termination properties.

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

  • MLA
  • Chicago
  • APA

"computable algebra." A Dictionary of Computing. . Encyclopedia.com. 20 Oct. 2018 <http://www.encyclopedia.com>.

"computable algebra." A Dictionary of Computing. . Encyclopedia.com. (October 20, 2018). http://www.encyclopedia.com/computing/dictionaries-thesauruses-pictures-and-press-releases/computable-algebra

"computable algebra." A Dictionary of Computing. . Retrieved October 20, 2018 from Encyclopedia.com: http://www.encyclopedia.com/computing/dictionaries-thesauruses-pictures-and-press-releases/computable-algebra

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.