Jump to ContentJump to Main Navigation
Handbook of Logic in Computer Science: Volume 5. Algebraic and Logical Structures$
Users without a subscription are not able to see the full content.

S. Abramsky, Dov M. Gabbay, and T. S. E. Maibaum

Print publication date: 2001

Print ISBN-13: 9780198537816

Published to Oxford Scholarship Online: November 2020

DOI: 10.1093/oso/9780198537816.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2021. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 15 June 2021

Computable functions and semicomputable sets on many-sorted algebras

Computable functions and semicomputable sets on many-sorted algebras

(p.317) Computable functions and semicomputable sets on many-sorted algebras
Handbook of Logic in Computer Science: Volume 5. Algebraic and Logical Structures

J. V. Tucker

J. I. Zucker

Oxford University Press

The theory of the computable functions is a mathematical theory of total and partial functions of the form f : Nn →N, and sets of the form. . . SÍ Nn. . .that can be defined by means of algorithms on the set . . . N = {0,1,2, . . . } . . . of natural numbers. The theory establishes what can and cannot be computed in an explicit way using finitely many simple operations on numbers. The set of naturals and a selection of these simple operations together form an algebra. A mathematical objective of the theory is to develop, analyse and compare a variety of models of computation and formal systems for defining functions over a range of algebras of natural numbers. Computability theory on N is of importance in science because it establishes the scope and limits of digital computation. The numbers are realised as concrete symbolic objects and the operations on the numbers can be carried out explicitly, in finitely many concrete symbolic steps. More generally, the numbers can be used to represent or code any form of discrete data. However, the question arises: . . . Can we develop theories of functions that can be defined by means of algorithms on other sets of data?. . . The obvious examples of numerical data are the integer, rational, real and complex numbers; and associated with these numbers there are data such as matrices, polynomials, power series and various types of functions. In addition, there are geometric objects that are represented using the real and complex numbers, including algebraic curves and manifolds. Examples of syntactic data are finite and infinite strings, terms, formulae, trees and graphs. For each set of data there are many choices for a collection of operations from which to build algorithms. . .How specific to the set of data and chosen operations are these computability theories? What properties do the computability theories over different sets of data have in common? . . . The theory of the computable functions on N is stable, rich and useful; will the theory of computable functions on the sets of real and complex numbers, and the other data sets also be so? The theory of computable functions on arbitrary many-sorted algebras will answer these questions.

Keywords:   Baire space, abstract data type, computable analysis, continuous domain, dynamical systems, effective algebra, halting set, infinite streams, initialisations, iterated map, periodic points, procedures, program schematology, program scheme, random assignments, register machines, relations, remainder set, search, search procedure, signature, snapshot function

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .