ConceptTheory & Algos
Computability theory
Sort of like a precursor to complexity theory that asks what computational tasks can be solved at all.
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.
Opens up
Concepts that name this one as a prerequisite.
Lecturers
2Each in their own terms, from the easiest level.
Michael Sipser
The study of what can be computed with an algorithm in principle.
Lectures that assume it
10- Architectures: Memory
- Complexity and Computability with Closed Timelike Curves
- Computing, Life, and Intelligence
- Why is P vs. NP Difficult?
- An Observation on Generalization and Unsupervised Compression
- Some Set Theory of Kaufmann Models
- Time Complexity
- HSE Kolmogorov Complexity, Lecture 1: Computability and Solomonoff Induction
- The Decomposability Conjecture in Borel Functions
- Super Turing Computing: Foundations for Aware and Ever-Adapting Systems
Connections
20The lectures that define it or assume it, and the concepts next to it.
Concepts8
Show 2 moreShow fewer
Lectures12
- Introduction, Finite Automata, Regular Expressions
- Course Overview and Formal Definition of Computation
- Architectures: Memory
- Complexity and Computability with Closed Timelike Curves
- Computing, Life, and Intelligence
- Why is P vs. NP Difficult?
Show 6 moreShow fewer
- An Observation on Generalization and Unsupervised Compression
- Some Set Theory of Kaufmann Models
- Time Complexity
- HSE Kolmogorov Complexity, Lecture 1: Computability and Solomonoff Induction
- The Decomposability Conjecture in Borel Functions
- Super Turing Computing: Foundations for Aware and Ever-Adapting Systems