## Quick Reference

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*, called a **numbering**, that uses a recursive set Ω of natural numbers to represent, or code, the set *A* of elements of the algebra;*A*.The idea in (b) of tracking operations in the code set is formulated by a commutative diagram depicting an equation: for each operation

*A*, called a **numbering**, that uses a recursive set Ω of natural numbers to represent, or code, the set *A* of elements of the algebra;

*A*.

*σ* : *A** ^{k}* →

*A*

of the algebra there is a recursive function

*f* : Ω* ^{k}* → Ω

such that

σ(α(*x*_{1}), …, α(*x** _{k}*) = α(

*f*(

*x*

_{1}, …,

*x*

*)*

_{k}for all

*x*_{1},…,*x** _{k}* ∈ Ω

. The idea of deciding equality in *A* is formulated by the relation

*n* ≡_{α}*m* ∅pendarrow; α(*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:

*Subjects:*
Computing.

## Related content in Oxford Index

##### Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.