Tag
turing-machines
- Jan 21, 2026 Encoding Turing Machines and the Undecidability of Acceptance How a machine becomes a finite string, what a configuration record contains, and why diagonalization over that encoding rules out any decider for acceptance. computation theory
- Jan 22, 2025 Diagonalization and the Time Hierarchy Theorem How a machine that runs itself on its own description separates two time bounds, why the constructibility condition cannot be dropped, and what the theorem does not prove. computation theory
- Nov 20, 2024 Polynomial Time and the Machine-Independence of P How P is defined by counting steps on a Turing machine, why the class survives a change of machine model, and where the definition stops matching the idea of tractability. computation theory
- Feb 27, 2023 The Chomsky Hierarchy as a Ladder of Memory Each level of the hierarchy corresponds to a kind of store a machine may use: none, a stack, a bounded tape, an unbounded tape. What the grammar restrictions encode about that store. computation theory