Decidability

Mathematical Logic · Axiom Academy

Understanding when problems can be solved algorithmically Mathematical Logic • Unit 6 - Computability Theory A fundamental question in computability theory: Can we write an algorithm that always terminates and correctly answers whether an input belongs to a language? Formal Definition: Decidable Language A language is decidable if there exists a Turing machine such that: The key property: always halts and gives the correct yes/no answer. Decidable vs Semi-decidable (Recognizable) There's a crucial distinction between languages we can decide and those we can only recognize: A language is semi-decidable (or recognizable ) if there exists a Turing machine such that: Decidable Languages are Closed Under Complement A powerful property that distinguishes decidable from semi-decidable languages: Theorem: Closure Under Complement If is decidable, then is also decidable. Proof idea: Run the decider for , then flip the answer. Since the original TM always halts, so does the complement TM. Semi-decidable languages are NOT closed under complement. There exist languages where: is semi-decidable (recognizable) Example: The halting problem and its complement. Languages That Are Recognizable but Not Decidable Some problems can be partially solved but never fully decided: The canonical example of a recognizable but undecidable language: is semi-decidable : We can recognize when a TM halts is NOT decidable : We cannot always determine if a TM will halt

This is the written version of the interactive lesson above. See the full Mathematical Logic course.