|
|
Dictionary definition: abstract computability theory
- Article from:
- A Dictionary of Computing
- Author:
Copyright© A Dictionary of Computing 2004, originally published by Oxford University Press 2004. (Hide copyright information)
|
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
. ...