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