Module
Basic Computability Landscape and Rice’s Theorem
Sign in to add this module to your path and practice.
About
The arithmetic hierarchy light touch: RE, co-RE, and beyond. Rice’s theorem: every nontrivial semantic property of RE languages is undecidable. Examples (does TM accept a regular language? infinite language? etc.). Optional: recursion theorem / fixed points at high level. Synthesis of the Chomsky hierarchy and computability map.
Goal
Apply Rice’s theorem correctly to semantic properties; place languages in the decidable/RE/co-RE/non-RE map; relate the automata hierarchy (regular ⊂ CFL ⊂ decidable ⊂ RE) and explain intrinsic limits of computation.
Unlocks
Tutor
Ask questions about this module.
Hi — I'm your tutor for Basic Computability Landscape and Rice’s Theorem. Ask about the concepts, goal, or where you're stuck.