Great Ideas in Theoretical Computer Science - Turing's Legacy

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!

Grab it

Explore the foundational concepts of theoretical computer science in this lecture from CMU's "Great Ideas in Theoretical Computer Science" course. Delve into Turing's legacy, examining the concept of problems as mappings of instances to solutions and the limitations of this approach. Investigate interpreters and the invention of Turing Machine programming languages. Learn the official definition and visual representation of Turing Machines, and discover essential TM subroutines and tricks. Gain insights from Professor Ryan O'Donnell's expertise in this comprehensive exploration of computational theory.

Syllabus

Intro
Problem: A mapping of instances to solutions.
Downsides as a formal definition
Interpreters
Inventing TM programming language
Defining Turing Machines
OFFICIAL PICTURE of a Turing Machine
OFFICIAL DEFINITION of Turing Machines
Some TM subroutines and tricks