Post’s Problem
Who Is This Guy?
Emil Post was an American mathematician who made numerous contributions to computability. Among other things, Post was the first research to make use of many-one reductions to prove that functions are not computable. Post introduced the model of computation, called a “Post-Turing machine”, which was discussed earlier in this course. Post also asked the question (discussed below) which inspired the work that will next be discussed.
Overview
In 1944, Emil Post asked a question that can be phrased as follows: “Does there exist a set that is computably enumerable that is not computable, but that is also not Turing-complete for the set of all computably enumerable sets?”
This question was not answered until 1956, when two other researchers — working independently — proved that the answer is “Yes”, at almost the same time.
Post’s problem motivated investigations of a variety of related problems and resulted in a variety of other interesting results about computability being established. Some of these will be discussed in the lectures that follow.
Lecture #18: Introduction to Post’s Problem (Thursday, October 31)
Why This is Included
This lecture introduces the technical definitions needed to ask Post’s question in a somewhat different way, that also allow a variety of related ideas to be expressed, and that allow a variety of related problems to be considered. This includes an introduction to Q-degrees for any reducibility Q.
Among other things, it leads to a consideration of additional properties of 1-reducibility — and 1-degrees. Initial results, concerning this, are presented in these notes.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #19: Creative Sets, Simple Sets, and Limits (Tuesday, November 5)
Why This is Included
This lecture introduces various kinds of sets that are useful in solving Post’s problem. While this will not be discussed in this course, productive sets and creative sets have important application and mathematical logic. Simple sets are of interest, because they are computably enumerable, but neither computable nor m-complete for the class, Σ1, of computably enumerable sets.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #20: Priority Methods and a Solution for Post’s Problem (Thursday, November 7)
Why This is Included
A priority method is a method used for the construction of a set that satisfies an infinite number of conditions. While these methods were developed for the solution of Post’s problem they have subsequently been applied to solve other problems in computability theory, as well.
This lecture presents one of two solutions to Post’s problem, that were obtained using priority methods, at almost exactly the same time.
