• Church-Turing thesis
• decidable predicate and predicate recognizability
• universal turing machine
• there are non-recognizable languages
• L is decidable IFF L and not L are both recognizable
• Mapping Reduction
  • halting problem
• computable function