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 σ : Ak → A
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.
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 σ : Ak → A
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.
More From encyclopedia.com
Computer Science , The term Computer Science encompasses three different types of research areas: computability, efficiency, and methodology.
General Introduction
Compu… Computation , Computation
Older methods
General-purpose digital computer
Error analysis
BIBLIOGRAPHY
In recent years there has occurred enormous technological deve… Primitive Recursion , primitive recursive function A function that can be obtained from certain initial functions by a finite number of applications of composition and pri… Grace Murray Hopper , Hopper, Grace Murray
HOPPER, GRACE MURRAY
computer sciences, programming languages, COBOL.
An admiral who never went to sea, Hopper owed her success… Julia Bowman Robinson , Robinson, Julia Bowman
ROBINSON, JULIA BOWMAN
(b. St. Louis, Missouri, 8 December 1919; d. Berkeley, California, 30 July 1985), mathematics, mathemat… Computer Software Security , Computers are an important facet of forensic science . Individual computers as well as computers that are electronically connected via the Internet h…
You Might Also Like
NEARBY TERMS
computable algebra