Tag
undecidability
- Oct 19, 2026 Ambiguity, Equivalence, and Other Undecidable Grammar Questions Membership in a context-free language is decidable, but asking whether two grammars denote the same language is not, and neither is asking whether one is ambiguous. computation theory
- Mar 12, 2026 Rice’s Theorem and the Collapse of Semantic Properties Why every nontrivial property of the language a program computes is undecidable, how the proof smuggles a halting question into an arbitrary property, and which program properties escape the theorem. computation theory
- 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
- Nov 10, 2025 The Post Correspondence Problem as a Reduction Source How a set of domino pairs encodes a computation through matched strings, why no algorithm can decide whether a match exists, and why this formulation is the convenient origin for other undecidability proofs. computation theory
- Dec 9, 2024 Mapping Reductions and the Halting Problem How a computable function that maps one language into another transfers undecidability, why the halting problem follows from acceptance by a reduction in the opposite direction, and where the construction breaks. computation theory