nach oben

2016 | Buch

Kapitel lesen Erstes Kapitel lesen

Turing Computability

Theory and Applications

verfasst von: Robert I. Soare

Verlag: Springer Berlin Heidelberg

Buchreihe : Theory and Applications of Computability

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Turing's famous 1936 paper introduced a formal definition of a computing machine, a Turing machine. This model led to both the development of actual computers and to computability theory, the study of what machines can and cannot compute. This book presents classical computability theory from Turing and Post to current results and methods, and their use in studying the information content of algebraic structures, models, and their relation to Peano arithmetic. The author presents the subject as an art to be practiced, and an art in the aesthetic sense of inherent beauty which all mathematicians recognize in their subject.

Part I gives a thorough development of the foundations of computability, from the definition of Turing machines up to finite injury priority arguments. Key topics include relative computability, and computably enumerable sets, those which can be effectively listed but not necessarily effectively decided, such as the theorems of Peano arithmetic. Part II includes the study of computably open and closed sets of reals and basis and nonbasis theorems for effectively closed sets. Part III covers minimal Turing degrees. Part IV is an introduction to games and their use in proving theorems. Finally, Part V offers a short history of computability theory.

The author has honed the content over decades according to feedback from students, lecturers, and researchers around the world. Most chapters include exercises, and the material is carefully structured according to importance and difficulty. The book is suitable for advanced undergraduate and graduate students in computer science and mathematics and researchers engaged with computability and mathematical logic.

Inhaltsverzeichnis

Frontmatter

Foundations of Computability

Frontmatter

1. Defining Computability

Abstract

In this chapter we define the notion of a computable function using Turing machines in §1.4. Then we develop its most important properties such as the Enumeration Theorem 1.5.3 and the s-m-n Theorem 1.5.5 (Parameter Theorem), which we shall use often. The historical development of other definitions of computable functions is discussed in the history chapter, Chapter 17.

Robert I. Soare

2. Computably Enumerable Sets

Abstract

This chapter is intended to give the reader a more intuitive feeling for c.e. sets, their alternative characterizations, and their most useful static and dynamic properties. We also prove the Recursion Theorem 2.2.1 (Fixed Point Theorem), which will be a very useful tool, and we apply it to prove Myhill's Theorem 2.4.6 that all creative sets are computably isomorphic.

Robert I. Soare

3. Turing Reducibility

Abstract

After his epochal paper in 1936 on Turing machines, Turing wrote a Ph.D. dissertation with Alonzo Church which was published in 1939. A tiny part of this paper in section 4 contained the germ of one of the most important ideas in all of modern computability theory. In half a page Turing suggested augmenting his formera-machines by adding some kind of “oracle” which could supply the answers to specific questions during the computation.

Robert I. Soare

4. The Arithmetical Hierarchy

Abstract

In addition to the notions of computability and relative computability, the Kleene arithmetical hierarchy is one of the fundamental concepts of computability theory.

Robert I. Soare

5. Classifying C.E. Sets

Abstract

In §1.6 we constructed a noncomputable c.e. set K. In §2.4 we studied creative sets and showed that all are computably isomorphic to K. So far the noncomputable c.e. sets we have exhibited are all computably isomorphic to K and therefore of Turing degree 0′. Post in [Post 1944] asked whether there is only one noncomputable c.e. set up to Turing equivalence.

Robert I. Soare

6. Oracle Constructions and Forcing

Abstract

We have seen in Chapter 5 how Post tried to solve Post's Problem 5.1.1 by defining c.e. sets A with ever thinner complements. Post himself did not live to see the refutation of this approach by [Friedberg 1958], who constructed a maximal set with the thinnest complement of all, and the construction of a complete maximal set by Yates, which refuted Post's approach. Post moved on to understand full Turing reducibility in [Post 1944]. He gave an excellent intuitive description of one set being Turing reducible to another.

Robert I. Soare

7. The Finite Injury Method

Abstract

A positive solution to Post’s problem was finally achieved by Friedberg in [Friedberg 1957] and independently by Muchnik in [Muchnik 1956], who built c.e. sets A and B of incomparable (Turing) degree. Friedberg then produced other results on c.e. sets in [Friedberg 1957b], [Friedberg 1957c] and [Friedberg 1958].

Robert I. Soare

Trees and Classes

8. Open and Closed Classes

Abstract

Using ordinal notation identify the ordinal 2 with the set of smaller ordinals {0, 1}.

Robert I. Soare

9. Basis Theorems

Abstract

The main theme of this chapter is this: Given a nonempty \(\Pi_{1}^0\) class \(\mathcal{C}\) What are the Turing degrees of members \(f\in \mathcal{C}\)?

Robert I. Soare

10. Peano Arithmetic and -Classes

Abstract

One of the earliest purposes of computability theory was the study of logical systems and theories. We consider theories in a computable language: one which is countable, and whose function, relation, and constant symbols and their arities are effectively given. We also assume that languages come equipped with an effective coding for formulas and sentences in the languages, i.e., a Gödel numbering, and identify sets of formulas with the corresponding set of Gödel numbers. We can then speak of the Turing degree of a theory in a computable language

Robert I. Soare

11. Randomness and -Classes

Abstract

In this chapter, we explore some of the relationships between \(\Pi_1^0\) classes, algorithmic randomness, and computably dominated degrees.

Robert I. Soare

Minimal Degrees

Frontmatter

12. Minimal Degrees Below

Abstract

This chapter presents the important method of forcing with trees to contruct minimal degrees. Variations on this method have produced many results on degrees and their initial segments as presented in Lerman [1983]. Theorems using the minimal degree construction can be found in the bibliographies of Epstein [1975] and [1979].

Robert I. Soare

13. Minimal Degrees Below

Abstract

The Spector proof of a minimal degree used a ø” oracle to prune one tree \(T^{e-1}\) to obtain the next tree \(T^{e}\). Sacks used a variation of the finite injury method. He saw that the Spector method could be approximated to find a minimal degree below a ø’ oracle

Robert I. Soare

Games in Computability Theory

Frontmatter

14. Banach-Mazur Games

Abstract

We use the definitions and notation on the topology of Cantor space and Baire space from §8.1 with basic open sets ⟦σ⟧ defined in (8.1). We extend Definition 8.6.1, which introduced dense sets and dense open sets.

Robert I. Soare

15. Gale-Stewart Games

Abstract

Gale-Stewart games illustrate the applications of \(\Pi_1^0\)-classes. In a Gale-Stewart game there are two players who alternately choose elements \(a_i \in \left\{0.1\right\}\).

Robert I. Soare

16. More Lachlan Games

Abstract

With the Kleene-Post [1954] paper on oracle constructions presented in Chapter 6, and the finite injury computable approximations to them in Friedberg [1957] and Muchnik [1956] presented in Chapter 7, constructions in computability entered a new and much more complicated phase in the 1960s. Shoenfield [1961] and independently Sacks [1963a, 1963c, and 1964a] invented the infinite injury method for constructing c.e. sets and degrees.

Robert I. Soare

History of Computability

Frontmatter

17. History of Computability

Abstract

Around 1880, Georg Cantor, a German mathematician, invented naive set theory. A small fraction of this is sometimes taught to elementary school children. It was soon discovered that this naive set theory was inconsistent because it allowed unbounded set formation, such as the set of all sets. David Hilbert, the world's foremost mathematician from 1900 to 1930, defended Cantor's set theory but suggested a formal axiomatic approach to eliminate the inconsistencies.

Robert I. Soare

Backmatter

Titel: Turing Computability
verfasst von: Robert I. Soare
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-31933-4
Print ISBN: 978-3-642-31932-7
DOI: https://doi.org/10.1007/978-3-642-31933-4