# Recursion on Abstract Structures

@inproceedings{Hinman1999RecursionOA, title={Recursion on Abstract Structures}, author={Peter G. Hinman}, booktitle={Handbook of Computability Theory}, year={1999} }

We develop and compare two models for computability over an abstract structure. The first, characterized in term of generalized register machines, provides a good theory for a large class of first-order structures. The second, defined in terms of minimal solutions for functional equations, is more versatile and handles many common second-order examples.

#### Topics from this paper

#### 7 Citations

First and Second Order Recursion on Abstract Data Types

- Mathematics, Computer Science
- Fundam. Informaticae
- 2005

This paper compares two scheme-based models of computation on abstract many-sorted algebras A: Feferman's system ACP(A) of "abstract computational procedures" based on a least fixed point operator,… Expand

Gandy's Theorem for Abstract Structures without the Equality Test

- Computer Science
- LPAR
- 2003

It is proved that Gandy’s theorem holds for abstract structures without the equality test, providing a useful tool for dealing with inductive definitions using Σ-formulas over continuous data types. Expand

Fixed points on abstract structures without the equality test

- Computer Science, Mathematics
- FICS
- 2002

It is proved that Gandy theorem holds for abstract structures and provides a useful tool for dealing with recursive definitions using Sigma-formulas. Expand

Theses for Computation and Recursion on Concrete and Abstract Structures

- Mathematics
- 2015

The main aim of this article is to examine proposed theses for computation and recursion on concrete and abstract structures. What is generally referred to as Church’s Thesis or the Church-Turing… Expand

Recent Advances in S-Definability over Continuous Data Types

- Computer Science
- Ershov Memorial Conference
- 2003

The purpose of this paper is to survey the recent research in computability and definability over continuous data types such as the real numbers, real-valued functions and functionals and illustrate how computability can be expressed in the language of Σ-formulas. Expand

Fixed Points on the Real Numbers without the Equality Test

- Computer Science, Mathematics
- Electron. Notes Theor. Comput. Sci.
- 2002

It is proved that Gandy theorem holds for the reals without the equality test, which provides a useful tool for dealing with recursive definitions using σ-formulas. Expand

On Gupta-Belnap Revision Theories of Truth, Kripkean fixed points, and the next stable set

- Mathematics, Computer Science
- Bull. Symb. Log.
- 2001

A simplified account of varied revision sequences is given —as a generalised algorithmic theory of truth —which enables something of a unification with the Kripkean theory oftruth using supervaluation schemes. Expand

#### References

SHOWING 1-10 OF 45 REFERENCES

Deterministic and Nondeterministic Computation and Horn Programs, on Abstract Data Types

- Computer Science, Mathematics
- J. Log. Program.
- 1992

The notion of “semicomputability” is investigated, intended to generalize the notion of recursive enumerability of relations to abstract structures and leads to the formulation of a “Generalized Church-Turing Thesis” for definability of Relations on abstract structures. Expand

Computable Functions on Stream Algebras

- Computer Science
- 1995

It is shown how models of deterministic parallel computation on A can be adapted to provide new models of computation on stream algebras over A, including simultaneous primitive recursion schemes with and without the least number operator. Expand

Computations in Higher Types

- Mathematics
- 1977

Abstract.- The computation domain.- Recursion on ?.- Connection with Kleene recursion in higher types.- Recursion in normal lists on ?.- Kleene recursion in normal objects of type n+2, n>0.-… Expand

Examples of Semicomputable Sets of Real and Complex Numbers

- Mathematics, Computer Science
- Constructivity in Computer Science
- 1991

We investigate the concept of semicomputability of relations on abstract structures. We consider three possible definitions of this concept, which all reduce to the classical notion of recursive… Expand

Computability over arbitrary fields

- Computer Science, Mathematics
- STOC
- 1969

The proposed definition of computability over arbitrary fields is based on the Shepherdson - Sturgis2 concept of an unlimited register machine. Expand

The Formal Language of Recursion

- Mathematics, Computer Science
- J. Symb. Log.
- 1989

This is the first of a sequence of papers in which this approach takes recursion to be a fundamental (primitive) process for constructing algorithms, not a derived notion which must be reduced to others—e.g. iteration or application and abstraction. Expand

Computability: An Introduction to Recursive Function Theory

- Mathematics
- 1980

Preface Prologue, prerequisites and notation 1. Computable functions 2. Generating computable functions 3. Other approaches to computability: Church's thesis 4. Numbering computable functions 5.… Expand

On the Solvability of Algorithmic Problems

- Computer Science
- 1975

This chapter discusses the basic concepts of a generalized Galois theory to make the paradigm of Galois available for the discussion of the solvability of algorithmic problems. Expand

On a theory of computation and complexity over the real numbers: $NP$- completeness, recursive functions and universal machines

- Mathematics
- 1989

We present a model for computation over the reals or an arbitrary (ordered) ring R. In this general setting, we obtain universal machines, partial recursive functions, as well as JVP-complete… Expand

Recursion in Higher Types

- Mathematics
- 1977

Publisher Summary Recursion in higher types is an extension of the theory of recursive functions on the integers. This chapter presents an exposition of the basic notions and facts of this theory. It… Expand