Skip to main content
main-content

Über dieses Buch

Science involves descriptions of the world we live in. It also depends on nature exhibiting what we can best describe as a high aLgorithmic content. The theme running through this collection of papers is that of the interaction between descriptions, in the form of formal theories, and the algorithmic content of what is described, namely of the modeLs of those theories. This appears most explicitly here in a number of valuable, and substantial, contributions to what has until recently been known as 'recursive model theory' - an area in which researchers from the former Soviet Union (in particular Novosibirsk) have been pre-eminent. There are also articles concerned with the computability of aspects of familiar mathematical structures, and - a return to the sort of basic underlying questions considered by Alan Turing in the early days of the subject - an article giving a new perspective on computability in the real world. And, of course, there are also articles concerned with the classical theory of computability, including the first widely available survey of work on quasi-reducibility. The contributors, all internationally recognised experts in their fields, have been associated with the three-year INTAS-RFBR Research Project "Com­ putability and Models" (Project No. 972-139), and most have participated in one or more of the various international workshops (in Novosibirsk, Heidelberg and Almaty) and otherresearch activities of the network.

Inhaltsverzeichnis

Frontmatter

Truth-Table Complete Computably Enumerable Sets

Abstract
We prove a truth-table completeness criterion for computably enumerable sets.
Marat M. Arslanov

Completeness and Universality of Arithmetical Numberings

Abstract
We investigate completeness and universality notions, relative to different oracles, and the interconnection between these notions, with applications to arithmetical numberings. We prove that principal numberings are complete; completeness is independent of the oracle; the degree of any incomplete numbering is meet-reducible, uniformly complete numberings exist. We completely characterize which finite arithmetical families have a universal numbering.
Serikzhan Badaev, Sergey Goncharov, Andrea Sorbi

Algebraic Properties of Rogers Semilattices of Arithmetical Numberings

Abstract
We investigate initial segments and intervals of Rogers semilattices of arithmetical families. We prove that there exist intervals with different algebraic properties; the elementary theory of any Rogers semilattice at arithmetical level n ≥ 2 is hereditarily undecidable; the class of all Rogers semilattices of a fixed level n ≥ 2 has an incomplete theory.
Serikzhan Badaev, Sergey Goncharov, Sergey Podzorov, Andrea Sorbi

Isomorphism Types and Theories of Rogers Semilattices of Arithmetical Numberings

Abstract
We investigate differences in isomorphism types and elementary theories of Rogers semilattices of arithmetical numberings, depending on different levels of the arithmetical hierarchy. It is proved that new types of isomorphism appear as the arithmetical level increases. It is also proved the incompleteness of the theory of the class of all Rogers semilattices of any fixed level. Finally, no Rogers semilattice of any infinite family at arithmetical level n ≥ 2 is weakly distributive, whereas Rogers semilattices of finite families are always distributive.
Serikzhan Badaev, Sergey Goncharov, Andrea Sorbi

Computability over Topological Structures

Abstract
Computable analysis is the Turing machine based theory of computability on the real numbers and other topological spaces. Similarly as Eršov’s concept of numberings can be used to deal with discrete structures, Kreitz and Weihrauch’s concept of representations can be used to handle structures of continuum cardinality. In this context the choice of representations is very sensitively related to the underlying notion of approximation, hence to topology. In this paper we summarize some basic ideas of the representation based approach to computable analysis and we introduce an abstract and purely set theoretic characterization of this theory which can be considered as a generalization of the classical concept of µ-recursive functions. Together with this characterization we introduce the notion of a perfect topological structure. In particular, these structures are effectively categorical, i.e. they characterize their own computability theory. Important examples of perfect structures are provided by metric spaces and additional attention is paid to their effective subsets.
Vasco Brattka

Incomputability in Nature

Abstract
To what extent is incomputability relevant to the material Universe? We look at ways in which this question might be answered, and the extent to which the theory of computability, which grew out of the work of Gödel, Church, Kleene and Turing, can contribute to a clear resolution of the current confusion. It is hoped that the presentation will be accessible to the non-specialist reader.
S. Barry Cooper, Piergiorgio Odifreddi

Gems in the Field of Bounded Queries

Abstract
Let A be a set. Given {x 1,…,x n }, I may want to know (1) which elements of {x 1,…,x n }, are in A, (2) how many elements of {x 1,…,x n } are in A, or (3) is |{x 1,…,x n }∩A| even. All of these can be determined with n queries to A. For which A, n can we get by with fewer queries? Other questions involving ‘how many queries do you need to…’ have been posed and (some) answered. This article is a survey of the gems in the field—the results that both answer an interesting question and have a nice proof.
William Gasarch

Finite End Intervals in Definable Quotients of ε

Abstract
It will be shown that in a factor lattice of the lattice of c.e. sets under inclusion with respect to a special congruence relation, there exists a finite end interval which is not a Boolean algebra.
Eberhard Herrmann

A Tour of Robust Learning

Abstract
Bārzdiņš conjectured that only recursively enumerable classes of functions can be learned robustly. This conjecture, which was finally refuted by Fulk, initiated the study of notions of robust learning. The present work surveys research on robust learning and focuses on the recently introduced variants of uniformly robust and hyperrobust learning. Proofs are included for the (already known) results that uniformly robust Ex-learning is more restrictive than robust Ex-learning, that uniformly robustly Ex-learnable classes are consistently learnable, that hyperrobustly Ex-learnable classes are in Num and that some hyperrobustly BC-learnable class is not in Num.
Sanjay Jain, Frank Stephan

On Primitive Recursive Permutations

Abstract
We show that each computable permutation is generated by polynomial time computable permutations via a three-placed term.
Iskander Kalimullin

On Self-Embeddings of Computable Linear Orders

Abstract
We show the existence of a computable linear order without nontrivial 0′-computable self-embedding.
Steffen Lempp, Andrei S. Morozov, Charles F. D. McCoy, D. Reed Solomon

Definable Relations on the Computably Enumerable Degrees

Abstract
We review recent developments in the study of definable relations on the computably enumerable (c.e.) degrees, including the following aspects:
(1)
Structure and hierarchies
 
(2)
Definable relations
 
(3)
Continuity in the c.e. degrees
 
(4)
Automorphisms
 
(5)
Defining ε in εn
 
Angsheng Li

Quasi-Degrees of Recursively Enumerable Sets

Abstract
The basis of the modern theory of degrees of unsolvability is established in the article by Post [46] in which the notions of many-one (m-) reducibility, truth-table (tt-), bounded truth-table (btt-) and Turing (T-) reducibility are introduced.
Roland Sh. Omanadze

Positive Structures

Abstract
The paper reviews the current state of the theory of positive (or computably enumerable) structures. This theory is relevant to several branches of algebra, logic and computer science, e.g. to algorithmic problems in algebra, theory of quasivarieties, logic programming, algebraic specifications of data types. Along with the general theory of positive structures we consider also positive structures of special kind (the most interesting results are obtained for positive boolean algebras) and some appliations of positive structures to logic and computability theory.
Victor Selivanov

Local Properties of the Non-Total Enumeration Degrees

Abstract
The non-total e-degrees are examined as a special subclass of the enumeration degrees.
Boris Solon

Backmatter

Weitere Informationen