Contents

• Contents
• Finite Automata and Regular Expressions -- Bern
  • Deterministic FAs
  • Non-deterministic FAs
  • FA with $\epsilon$ moves
  • Two-way FA
  • FAs with output
    • Moore machine
    • Mealy machine
    • HMM and NMM digression
• Properties of Regular Sets -- E'beth
  • digression on nature of class
  • Pumping Lemma
    • Regular Sets
      • Ben's prime number joke
    • Regular Sets Continued
      • Ben's synopsis
      • Han's elaboration
  • Neil Gershenfeld's digression
  • Han's explanation of FA limitations
  • E'beth's presentation continued
  • digression on class structure
• Presentation three -- Yael
• Ben's presentation
  • Properties of context-free languages
    • halting digression
  • Turing Machines
    • Black Box digression
  • TM's continued
    • instantaneous description of Turing machine
  • Two-way infinite tape
  • Multiple tape TM
  • Multidimensional TMs, Non-deterministic TMs, etc.
  • Church Turing hypothesis
    • Question about functions and computability (Yael)
• Discussion for next time
  • What do we all want to get out of this?
    • Yael
    • Han
    • Ben
      • Ben on complexity
    • Ed
    • E'beth
    • Rich
• Questions for next time
  • Ed
  • Yael
  • Ben
  • Rich
  • Han