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 σ : A^k → A

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

such that σ(α(x₁), …, α(x_k)) = α(f(x₁, …, x_k))

for all x₁,…,x_k ∈ Ω. 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.