Contents

• Contents
• Background for Decidability
  • Turing Machines briefly defined
  • Procedures and Functions
    • Procedures equivalent to TM's
    • More functions than procedures
  • Problems
    • A problem is a yes-no question
    • Reducibility
      • A reducible to B means A at least as hard as B
    • Encoding and Algorithms
      • Problem instances as strings, problem as language
• Recursive and Recursively Enumerable Languages
  • Recursively Enumerable Languages
    • r.e. languages enumerable by TMs
    • Enumeration means listing only valid strings
    • Some r.e. languages have no always-halting TM
    • TMs always halt for w in L(M)
    • Recursive Languages
      • Recursive languages = TMs that always halt
  • Are All Languages Recursively Enumerable?
    • Some languages not r.e.
• Decidability
  • problems with recursive languages decidable
  • Trivial Decidability
    • one string = recursive language
  • Decidable Doesn't Mean Solved
    • e.g. Fermat's conjecture
    • decidable doesn't mean we know how to solve it
  • Decidability Theorems
    • Theorem 1
      • The complement of a recursive language is recursive
    • Theorem 2
      • The union of two recursive languages is recursive
    • Theorem 3
      • If a language and it's complement are r.e, they are both recursive
      • Implications of Theorem 3
  • Decidability analysis
    • Strategy for decidability
      • first principles or reduction
    • A non-r.e. language: L_d
      • definition of w_i and M_j
      • acceptance table
      • The language L_d is not r.e.
    • A r.e, non-recursive language: L_u
      • The Universal Language
    • Rice's Theorem
      • Rice's theorem applies to languages, not to TMs
    • Post's Correspondence Problem