m29s11 Minitest 2: topics
This test covers topics from Chapters 5, 6, and 7, as well as the first page of Chapter 8.
Topics
- computably enumerable sets
- simple sets
- Turing reduction and degree
- Turing completeness (proof usually involves s-m-n)
- relativization and the Turing jump
- stagewise constructions
- requirements, priority, and injury
- arithmetic hierarchy: levels, completeness in this context, relationship to Turing degrees
- limit lemma and its application to low sets
Back to m29 syllabus
Back to main m29 page
Last modified May 16, 2011