“abstract computability theory”的概念、定义、翻译、参考文献-科学参考

abstract computability theory

Computer

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. Comparisons can be made between computations on different algebras, modelling data types and their implementations. The theory also provides a foundation for new theories of computation for special data types, such as algebras of real numbers, which can be used in applications.
The while programming language is a simple example of a method for computing functions on any many-sorted algebra A (that possesses the Booleans). On the natural numbers it can compute all partial recursive functions. Computation is based on the operations of the algebra—sequencing, branching, and iteration—and has available a limited means of searching A. However, a vital missing component is the capacity to compute with finite sequences of data from A. On the natural numbers finite sequences can be simulated using pairing functions, but it is not possible to simulate finite sequences on an algebra A. Finite sequences and operations for every data set in A are therefore added to A to make a new algebra A*. It turns out that while programs on A* (i.e. while programs equipped with finite sequences) have all the essential properties of the computable functions on A. This class of functions is the subject of the generalized Church-Turing thesis.
Most of the main results in the theory of computability on the natural numbers can also be proved for abstract computability theory on any finite generated minimal algebra.

单词	abstract computability theory
释义	abstract computability theory Computer 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. Comparisons can be made between computations on different algebras, modelling data types and their implementations. The theory also provides a foundation for new theories of computation for special data types, such as algebras of real numbers, which can be used in applications. The while programming language is a simple example of a method for computing functions on any many-sorted algebra A (that possesses the Booleans). On the natural numbers it can compute all partial recursive functions. Computation is based on the operations of the algebra—sequencing, branching, and iteration—and has available a limited means of searching A. However, a vital missing component is the capacity to compute with finite sequences of data from A. On the natural numbers finite sequences can be simulated using pairing functions, but it is not possible to simulate finite sequences on an algebra A. Finite sequences and operations for every data set in A are therefore added to A to make a new algebra A. It turns out that while* programs on A* (i.e. while programs equipped with finite sequences) have all the essential properties of the computable functions on A. This class of functions is the subject of the generalized Church-Turing thesis. Most of the main results in the theory of computability on the natural numbers can also be proved for abstract computability theory on any finite generated minimal algebra.
随便看	deceleration parameter Decembrists decentralization DECHEMA de Chéseaux, Comet deci- decibel decibel(symbol: dB) decidability decidable decidable problem decidable set deciduous deciduous forest deciduous teeth decile decimal expansion decimalize decimal places decimal point decimal reduction time decimal representation decimal system decimation decision analysis