Abiblo Computer Science - Abstract Computability Theory
It is a theory of function which could be computed on any algebra by algorithms. The aim of abstract computability theory is to explore the scope and limitation of computation of any data. It is a generalisation to arbitrary many sorted algebras of the theory of the calculable or recursive function on the natural numbers.
Abstract computability theory begins with classification and analysis of many models of computation and specification which apply to algebras. This lead to Church - Turing thesis which establishes , function on an abstract data type which are programmable by a deterministic programming language.
Comparison is possible between computations on modelling data types, algebras and implementations.
There will be a new theories of computation for special data types arrived from the theory such as algebras of real numbers.
The programming language is a form of simple example of a method for computing functions on many sorted algebra A.
It can compute all partial recursive function on natural numbers.
Computation focuses on the operation of algebras ( sequencing, iteration and branching which available as limited means of searching A ).
However, a vital missing component is the capacity to compute with finite sequence of data from A,
Pairing functions can stimulates the natural number of finite sequences but not possible to stimulate finite sequence on algebra A.
A new algebra A * is created by addition of finite sequence and operations for every data set in A.
Most of the results derived from the theory of computability on the natural number can also be proven for abstract computability theory on finite generated minimal algebra.
Leave a Reply.
Learn the facts about Computer Science.