ConceptTheory & Algos
Decidability
A language is decidable if there exists a Turing machine that accepts all strings in the language and rejects all strings not in the language.
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
1Lectures that assume it
11- Undecidability
- Recursion Theorem and Logic
- Time Complexity and Universal Turing Machines
- Reducibility
- Computation History Method
- Time Hierarchy Theorem
- Course Introduction and Overview
- Why is P vs. NP Difficult?
- Decision Problems for Automata and Grammars
- Time Complexity
- HSE Kolmogorov Complexity, Lecture 1: Computability and Solomonoff Induction
Connections
18The lectures that define it or assume it, and the concepts next to it.