First Hard Problems
Who are These Guys?
Alonzo Church was an American mathematician, computer scientist, logician and philospher who had contributions to mathematical logic and the foundations of theoretical computer science.
Alan Mathison Turing was an English mathematician, logician, cryptoanalyst, philosopher, and theoretical biologist.
Initially working independently — and, sometimes, proving the same things in different ways — both made numerous contributions in computability. Both proposed universal models of contribution that continue to be studied, and used, today. Both contributed early results, concerning undecidability. In the 1930’s, Turing travelled to Princeton to work under Church’s supervision. At this time they (along with Stephen Cole Kleene) established the equivalence of their models of computation, leading to the development of the “Church-Turing thesis” as we understand it now.
Overview
The next lectures introduce concepts and techniques needed to identify functions that are provably not computable — as well as languages and problems that are provably undecidable.
We will begin with universality of computation, which concerns the ability to describe a program or machine that emulates the computation of others. Diagonalization will be reviewed after this, and reductions and reducibilities will be presented. A variety of extensions and applications of this theory will be introduced. This will be used to prove something that has been claimed but not yet shown — there exists a total function that is computable, but not primitive recursive.
Lecture #9: Emulation of Computations — and a “Universal”
S-Program
(Tuesday, October 1)
Why This is Included
Universality — the ability to use a model of computation to describe a machine or program that emulates computations of other (encoded) machines or programs of the same type — is one of the properties that generally useful (and “Turing machine equivalent”) models of computation have, which more limited models of computation lack. This (or, at least, the material needed to develop this) can be useful when one is establishing a first undecidable language or uncomputable function — when others are not already available, so that a reduction cannot be used for this.
This lecture describes the development of a “universal S-program”. It ends by using some of the material, used to obtain this, to complete a proof that every Turing-computable partial or total function is also μ-recursive.
Preparatory Reading
- Emulation of Computations — and a “Universal” S-Program: [ PDF ] [ Video ]
- Supplement: Proof of the Normal Form Theorem: [ PDF ]
- Supplement: Universal Turing Machines: [ PDF ]
Lecture Presentation
Finishing Up
Lecture #10: First Hard Problems
(Thursday, October 3)
Why This is Included
Diagonalization is a proof technique that has been used to prove a variety of significant results in mathematics and theoretical computer science. Students who have been introduced to this proof technique in a mathematics course have probably (but not definitely) seen this used to prove that the set of real numbers is an uncountable set. As shown in these lecture notes it can also be used to prove that a particular function\ is not S-computable.
Lecture material continues with two results — the Universality Theorem and the Parameter Theorem — that may seem unsurprising, but that are reasonably easy to establish, using the results from the previous lecture (and the work done to obtain them). These will be used to establish somewhat more interesting things, later on.
Two different classes of subsets of the natural numbers, computable sets and computably enumerable sets, can defined using the models of computation that have been introduced. These will both be important as the course material. The lecture material includes statements and proofs of several properties concerning how these set are related, and how they can be (differently) defined. This will help to relate these to other sets that you have probably seen already.
Two useful sets are identified:. Another diagonalization argument is used to identify that a set that is provably not computably enumerable — and this is used to identify another set that is provably computably enumerable, but not computable.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #11: Reducibilities — and Many-One Reductions
(Tuesday, October 8)
Why This is Included
As described in these notes, a reducibility is a binary relation, between subsets of the natural numbers, satisfying a pair of additional properties. Closure properties can sometimes be established for reducibilities and collections of subsets that are interest — including the collection of computable subsets of N and the collection of computably enumerable subsets of N. These can sometimes be used to prove results about the computability of sets.
One particular kind of reducibility — the collection of many-one reductions between sets — is defined and investigated in this lecture. Many-one reductions are then used to identify additional subsets of N that are provably not computable, and that are provably not computably enumerable.
Students may not be surprised to see a discussion of “reductions” in this course, since another kind of reduction was almost certainly used in another course introducing the theory of computation. It may be more surprising that a form of completeness is also given here, since it is likely that “completeness” has only been considered, before this, as part of a discussion of computational complexity theory. Indeed, “completeness” plays a significant role in computability theory — and, as this might suggest, many of the ideas used early on, in the study of computational complexity theory, had been introduced in computability theory, before that.
Preparatory Reading
Lecture Presentation
Finishing Up
Lecture #12: Rice’s Theorem and the Recursion Theorem
(Thursday, October 10)
Why This is Included
As the examples included in the notes should show, Rice’s Theorem and the Recursion Theorem are technical results that can be used to show that a variety of sets are not computable — providing another way to do this besides presenting many-one reductions.
Preparatory Reading
- Rice’s Theorem and the Recursion Theorem: [ PDF ] [ Video ]
- Supplement: Proof of the Recursion Theorem [ PDF ]
Lecture Presentation
Finishing Up
Lecture #13: A Computable Total Function That is Not Primitive
Recursive
(Tuesday, October 15)
Why This is Included
It was initially believed, by a significant number of researchers, that every computable total function is primitive recursive — so that this result was unexpected. While the proof is rather complicated, it serves as an example of a nontrivial use of diagonalization, as well as a nontrivial use of the Recursion Theorem.
Preparatory Reading
- A Computable Total Function That is Not Primitive Recursive: [ PDF ] [ Video ]
- Supplement: Proofs of Claims: [ PDF ]
