Overview
Syllabus
15-251: Great Theoretical ideas in Computer Science Lecture 22
What is a computation/algorithm?
Turing's inspiration: computers (usage 2)
The finite control (AKA transition rules)
Formal definition of Turing Machines
Decidable languages
TM programming exercises & tricks
Universal Turing Machine
TM's: good definition of computation?
Church-Turing Thesis: "Any natural / reasonable notion of computation can be simulated by a TM."
Describing Turing Machines
Some uncomputable functions
Does the following program (written in Maple) print out "HELLO WORLD" ?
The Halting Problem is Undecidable
Taught by
Ryan O'Donnell