1. Computability
2. Logic

Computability

• Language Classes
  Definition of Recursive (R) Turing Machines
  Definition of Recursively Enumerable (R.E.) Turing Machines
  Definition of the languages NSA and SA
• Proof: NSA is not R.E., SA is R.E.
• Rice's Theorem

Logic

• PLNS Incompleteness
• ⊦ <φ>C<ψ> is R.E. (some content on previous page)
• ⊧ <φ>C<ψ> is not R.E. (some content on next page)
• Relate from PLNS to Gödels