scientific article; zbMATH DE number 3887669
[For the entire collection see Zbl 0544.00005.] Definitions of Type 2 computability, i.e. computability on sets with cardinality not greater than that of the continuum, have been given in several ways. Most of these definitions are equivalent or at least dependent from each other but there is no generally accepted approach as in the case of computability on denumerable sets. This paper presents the concept of representations as a foundation for a unified Type 2 computability theory. Its basic idea is that real world computers cannot operate on abstract elements of a set M but only on names. The authors have chosen the set \({\mathbb{F}}\) of sequences of natural numbers as a standard set of names and have defined computability on \({\mathbb{F}}\) explicitly (see the second author's forthcoming paper Type 2 recursion theory). Computability on other sets M then can be derived from computability on \({\mathbb{F}}\) by means of representations i.e. (partial) mappings from \({\mathbb{F}}\) onto M. Computable Type 2 functions turn out to be continuous in general and in most cases functions which are not computable are not even continuous. Hence topological considerations are fundamental for Type 2 theory and continuity w.r.t. representations is also studied. Therefore two versions of Type 2 theory are developed simultaneously, a topological (t-) and a computable (c-) one. They turn out to be formally equivalent to ordinary Type 1 recursion theory. The theory of representations corresponds to the theory of numberings. For \(T_ 0\)-spaces with countable bases admissible representations which reflect the topological structure are introduced and discussed. The theory of representations supplies a broad basis for investigating computability and computational complexity in analysis.
- Type 2 recursion theory
- Theory of representations
- Representations of the real numbers and of the open subsets of the set of real numbers
- Topological properties of real number representations.
- Topological analysis of representations
- Quantitative coding and complexity theory of compact metric spaces
- Representations and the foundations of mathematics
- Self-representation in Girard's System U
- The representational foundations of computation
- scientific article; zbMATH DE number 5898637 (Why is no real title available?)
- Type‐2 computability on spaces of integrable functions
- Spaces allowing Type‐2 Complexity Theory revisited
- Honest computability and complexity
- scientific article; zbMATH DE number 3869319 (Why is no real title available?)
- Recursion theoretic operators and morphisms on numbered sets
- Exhaustible sets in higher-type computation
- scientific article; zbMATH DE number 3920459 (Why is no real title available?)
- scientific article; zbMATH DE number 4037847 (Why is no real title available?)
- scientific article; zbMATH DE number 551031 (Why is no real title available?)
- scientific article; zbMATH DE number 1969324 (Why is no real title available?)
- Closed sets and operators thereon: representations, computability and complexity
- scientific article; zbMATH DE number 2163039 (Why is no real title available?)
- scientific article; zbMATH DE number 3993572 (Why is no real title available?)
- Computability and representations of the zero set
- Revising type-2 computation and degrees of discontinuity
- Total representations
- FM-representability and beyond
- scientific article; zbMATH DE number 7644091 (Why is no real title available?)
- Logical Approaches to Computational Barriers
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3222178)