CIS 511, Spring 2021

Some Course Notes and Slides

Slides for Languages and Automata

Slides for Computability, Undecidability and Complexity

  • RAM Programs and Turing Machines (slides) (pdf)
  • The Primitive Recursive Functions and the Partial Computable Functions (slides)   (pdf)
  • The Puccini Theorem (slides)   (pdf)
  • Universal RAM Programs and the Undecidability of the Halting Problem
    Undecidability and Reducibility (slides)   (pdf)
  • Elementary Recursive Function Theory (slides)   (pdf)
  • The Lambda Calculus as a Computation Model (slides)   (pdf)
  • Recursion Theory: More Advanced Topics (slides)   (pdf)
  • Listable and Diopantine Sets; Hilbert's Tenth (slides)   (pdf)
  • The Post Correspondence Problem. Applications to Undecidability Results (slides)   (pdf)
  • Computational Complexity; P and NP (slides)   (pdf)
  • Some NP-Complete Problems (slides)   (pdf)
  • Polynomial-Space Complete Problems; PS and NPS (slides)   (pdf)

  • ** Prove that P = NP, and get a one million dollar reward! (Clay Institute)
  • ** Theory of Computation in German! (slides)


    Back to Gallier Homepage

    published by:

    Jean Gallier