ConceptTheory & Algos
Turing machine
A mathematical model of computation that manipulates symbols on a strip of tape according to a table of rules.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Algorithm4Computability3Finite automata3Finite automaton2Pushdown automata2Alphabets and strings1Arrays/memory1Automata1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
9Each in their own terms, from the easiest level.
Michael Sipser
A theoretical model of computation that manipulates symbols on a tape according to a table of rules.Ryan O'Donnell
A theoretical model of computation consisting of a tape, a finite control with states, and a read-write head that moves left or right.Bernhard Boser & Gireeja Ranade
A very abstract, very simple kind of thing that captures all the essence of a computer.Yu Zhao
A mathematical model of computation that manipulates symbols on a tape according to a table of rules.Alan Kay
A mathematical model of computation that manipulates symbols on a strip of tape.Demis Hassabis
A theoretical model of computation that is able to compute anything that is computable.Juliet Floyd
A set of equations and a formal system that serves as a simplified snapshot of human linguistic behavior designed for a very specific purpose.John Carlos Baez
An idealized gadget for doing calculations in a completely systematic way with a potentially infinite memory.
Lectures that assume it
68The first 12 are shown.
- The Word RAM Model
- The Complexity Class coNP
- Randomized Complexity: RP, coRP, and ZPP
- Undecidability
- Games, Generalized Geography
- Hardness within P
- The Immerman-Szelepcsényi Theorem
- P and NP, SAT, Poly-Time Reducibility
- Course Overview and Formal Definition of Computation
- How Hard is too Hard? An Introduction to Complexity
- Complexity and Computability with Closed Timelike Curves
- PSPACE-Completeness
Connections
90The lectures that define it or assume it, and the concepts next to it.
Concepts10
Show 4 moreShow fewer
Lectures80
- CF Pumping Lemma, Turing Machines
- Turing Machines
- Introduction to Information Devices and Linear Modeling
- TM Variants, Church-Turing Thesis
- NP-Completeness and the Cook-Levin Theorem
- Computational Models: Turing Machines
Show 74 moreShow fewer
- Dynabook: The Complete Story
- Accelerating Scientific Discovery with Artificial Intelligence
- Time Complexity
- Algorithmic Thermodynamics
- HSE Kolmogorov Complexity, Lecture 1: Computability and Solomonoff Induction
- Aesthetics, Mathematics, and Philosophy: Is There an Intersection?
- The Word RAM Model
- The Complexity Class coNP
- Randomized Complexity: RP, coRP, and ZPP
- Undecidability
- Games, Generalized Geography
- Hardness within P
- The Immerman-Szelepcsényi Theorem
- P and NP, SAT, Poly-Time Reducibility
- Course Overview and Formal Definition of Computation
- How Hard is too Hard? An Introduction to Complexity
- Complexity and Computability with Closed Timelike Curves
- PSPACE-Completeness
- Simulations and Turing Machine Variants
- The Complexity Class NP
- Reductions
- Time/Space Tradeoffs for SAT
- Space Complexity
- BPP (Bounded-Error Probabilistic Polynomial Time) Complexity Class
- Interactive Proofs: IP=PSPACE
- Computing, Life, and Intelligence
- Recursion Theorem and Logic
- Time Complexity and Universal Turing Machines
- Hierarchy Theorems (Time, Space, and Nondeterministic)
- Hopcroft–Paul–Valiant Theorem
- Search-to-Decision, Padding, Dichotomy Theorems
- Toda's 1st Theorem and the Permanent
- Instance Checking and the Permanent
- The Conscious Turing Machine (CTM), a formally defined Theoretical model of Consciousness
- Reducibility
- Computation History Method
- NP-Completeness
- Cook-Levin Theorem
- Hierarchy Theorems
- Strange Gaps in the Local Time Hierarchy
- Time Hierarchy Theorem
- Course Introduction and Overview
- Circuits
- Probabilistic Complexity Classes
- Ladner's Theorem and Mahaney's Theorem
- Savitch's Theorem and NL
- NL-Completeness and Logspace Reductions
- From P-Completeness to PSPACE-Completeness
- IP = PSPACE
- Interactive Proof Systems, IP
- Oracle Turing Machines and P^NP
- Why is P vs. NP Difficult?
- Toda's Second Theorem and Lower Bounds for Uniform ACC
- Hardness vs. Randomness I
- Quantum "Supremacy"
- Mathematics and Computation: The Landscape of P vs. NP
- Decision Problems for Automata and Grammars
- Space Complexity, PSPACE, Savitch's Theorem
- L and NL, NL = coNL
- Provably Intractable Problems, Oracles
- Problems in P
- Nondeterminism
- Valiant–Vazirani Theorem, and Exact Counting (#P)
- Probabilistic Computation, BPP
- AI's Impact on Programming: An Epistemological Perspective
- Oracles, and the Polynomial Time Hierarchy vs. circuits
- Architecture & Systems in Quantum Computing: Opportunities and Challenges
- Exploring Chemical Space with Chemputation and Assembly Theory
- The Polynomial Time Hierarchy
- Super Turing Computing: Foundations for Aware and Ever-Adapting Systems
- More on constant-round interactive proof systems
- Quasilinear Cook–Levin Theorem
- Mathematics and Metamathematics of Our Physics Project
- The Role of TCS in Understanding (AI) Consciousness