J.V. Tucker

Title: J.V. Tucker

Research Question: Can abstract computability be defined and characterized using algebraic specifications?

Methodology: The researchers used abstract computability theory, which is a generalization of classical recursion theory on the natural numbers. They focused on many-sorted algebras and developed a model of computation called µPR∗. This model involves simultaneous primitive recursion and least number search, and is equivalent to 'while'-array programs over these algebras.

Results: The researchers proved that there exist finite universal algebraic specifications that uniquely specify abstract computable functions on any many-sorted algebra and functions that are effectively approximable by abstract computable functions on any metric algebra. They also showed that there exist universal algebraic specifications for all classically computable functions on the set R of real numbers.

Implications: These results have significant implications for the field of computability theory. The ability to define and characterize abstract computability using algebraic specifications provides a new way to understand and analyze models of computation and specification over abstract data types and their implementations. Additionally, the results have practical applications in the development of algorithms and programs for computing real numbers and solving differential or integral equations.

Link to Article: https://arxiv.org/abs/0109001v1 Authors: arXiv ID: 0109001v1