m29s11 Minitest 1: topics

This test covers topics from 3.1-3.5, 4.1-4.4, and 5.1-5.2.

Definitions and examples

• Ackermann function (not calculating it, but as an example of non-primitive-recursive total computable function)
• Church-Turing thesis
• Universal machine
• Halting problem/halting set (K)
• Unsolvable problem
• Dovetailing

More than definitions

• Turing machine: step through a computation; determine function given quadruples
• Relationship between classes of functions: primitive recursive, total computable, partial recursive, Turing computable (but not the recursive definitions of the primitive and partial recursive functions)
• Effectively countable sets, codes/indices; basic codes (but not the equation for the pairing function) and putting together effectively countable sets
• S-m-n theorem and basic uses; Recursion Theorem and basic uses; both as in homework
• The "three contradictions": using the "diagonal plus one" function to show (a) there is a total computable but not primitive recursive function; (b) the total computable functions are not effectively countable; (c) the halting problem is not computable
• Computable and computably enumerable sets: basic results (5.2.2, 5.2.4), putting them together, considering subsets (as in homework)

Back to m29 syllabus

Back to main m29 page

Last modified April 13, 2011