Completed
Church-Turing Thesis: "Any natural / reasonable notion of computation can be simulated by a TM."
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Great Ideas in Theoretical Computer Science: Computability
Automatically move to the next video in the Classroom when playback concludes
- 1 15-251: Great Theoretical ideas in Computer Science Lecture 22
- 2 What is a computation/algorithm?
- 3 Turing's inspiration: computers (usage 2)
- 4 The finite control (AKA transition rules)
- 5 Formal definition of Turing Machines
- 6 Decidable languages
- 7 TM programming exercises & tricks
- 8 Universal Turing Machine
- 9 TM's: good definition of computation?
- 10 Church-Turing Thesis: "Any natural / reasonable notion of computation can be simulated by a TM."
- 11 Describing Turing Machines
- 12 Some uncomputable functions
- 13 Does the following program (written in Maple) print out "HELLO WORLD" ?
- 14 The Halting Problem is Undecidable
