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