No label defined (Q3222178)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3887669
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3887669 |
Statements
1984
0 references
Type 2 computability
0 references
0.8708199
0 references
0 references
0.8691505
0 references
0 references
0.8588474
0 references
[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.
0 references