Podcaster
Episoden
Über diesen Podcast
This is a rigorous undergraduate course on the Theory of
Computation, using the classic text "Introduction to the Theory of
Computation" by Michael Sipser. The course covers machine models
and languages defined by Finite State Machines, Context-Free
Languages, and Turing Machines. There are four major theorems (and
their uses) that we will study during this course, providing
complete proofs: the pumping Lemma for regular languages, used to
show that there are languages that are not regular; the existence
of a Universal Turing Machine; undecidability of the Halting
problem; and Cook's theorem that NP-complete problems exist. In
addition to these major results, and other results, a central goal
of the course is to increase student's skill level in understanding
and writing rigorous mathematical proofs.
Kommentare (0)