Classifying Unsolvable Problems
Who Is This Guy?
Stephen Cole Kleene was an American mathematician — and a student of Alonzo Church. Along with Emil Leon Post, Kleene continued the work of Church and Turing. His contributions concerned the Normal Form Theorem, which established the equivalence of μ-computable functions and Turing-computable functions, as well as a considerable number of the results that will be discussed in the next lectures.
Overview
Is one problem more “unsolvable” than another? Can unsolvable problems be compared, and organized, in a useful way? The next lectures consider these questions and some of the research that they inspired. In particular, they include an introduction to the arithmetic hierarchy — which is sometimes called the “Kleene-Mostowski Hierarchy”, in recognition of Kleene&rsquo's (and Mostowski’s) work to define and study this.
Lecture #14: Oracle Computations (Thursday, October 17)
Why This is Included
Computations with oracles somewhat resemble the use of “library software” in software development: One uses, as a subroutine, software that is expected to solve a given problem without having any knowledge, or control, over what that software does — essentially treating that software as a “black box”.
In this lecture, this idea is developed by introducing and exploring the use of S-programs with oracles. These will be used, later on, to develop another reducibility that will be useful to classify uncomputable sets.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #15: More about Reductions and Reducibilities (Tuesday, October 22)
Why This is Included
This lecture introduces another two reducibilities — one-one reducibility and Turing reducibility (which might also be called “oracle reducibility”) — which will be useful later in this course.
Turing reductions are also used to define sets that are computable, relative to an oracle and sets that are computably enumerable, relative to an oracle. These will be useful shortly, as a classification of unsolvable problems using the “arithmetic hierarchy” is introduced.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #16: The Arithmetic Hierarchy (Thursday, October 24)
Why This is Included
This lecture introduces the arithmetic hierarchy, which is useful for classifying (at least some) unsolvable problems. Results that have been presented in recent weeks are applied, here, to identify complete sets for various classes in this hierarchy (and, in one case, to prove that a complete set cannot exist) and to establish containment and separation results that help to explain the structure of this hierarchy of classes of sets.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #17: Applying the Arithmetic Hierarchy (Tuesday, October 29)
Why This is Included
This lecture provides an alternative characterization of the arithmetic hierarchy, using arithmetic predicates, which makes it easier to place sets within this hierarchy. It is applied to identify 1-complete sets for a class in the Arithmetic Hierarchy that was not considered, in this course, before the Arithmetic Hierarchy was introduced — characterizing the “computability” of an interesting set in a way that was not possible before this.
