 |
Reading
Read what we covered in today's class: 6.6
Read what we will cover in the next class: 7.1, 7.2
When reading 6.6 pay special attention to the following concepts:
- the definition of partially decidable, the examples in 6.2,
the characterization of partially decidable predicates in Theorems 6.3 & 6.4,
the closure of partially decidable predicates under existential quantification given by
Theorem 6.5, diophantine predicates,
the equivalence of diophantine and partially decidable predicates given by
Theorems 6.9 & 6.10
When reading 7.1 pay special attention to the following concepts:
- characteristic function, recursive/computable sets, the examples of computable sets, and
Theorem 1.3 which lists some nice properties of computable sets
When reading 7.2 pay special attention to the following concepts:
- The definition and basic examples of c.e. sets, Theorems 2.3,4,5,6 which utilize
what we already know about partially decidable predicates to provide information about c.e. sets,
the characterization of c.e. sets given by Theorem 2.7, the characterization of the set
of indices of total computable functions given by Theorem 2.9 (you should find this particularly
interesting), the connection between c.e. sets and diophantine predicates,
and the algebraic facts about c.e. sets given by Theorem 2.13.
|
|
