Decidability Explorer
Explore the fundamental limits of computation through decidable, undecidable, and semi-decidable problems
Decidability Explorer
Explore decidable, undecidable, and semi-decidable problems
Decidability Explorer 🔍
Explore the fundamental limits of computation through decidable, undecidable, and semi-decidable problems
Decidable
Problems with algorithms that always terminate and give correct answers
Semi-decidable
Problems that can be recognized but not decided
Undecidable
Problems with no algorithmic solution
Problems
Click to explore each problem
Regular Language Membership
Given a regular language L and string w, determine if w ∈ L
Context-Free Language Emptiness
Given a CFG G, determine if L(G) = ∅
Halting Problem
Given a TM M and input w, determine if M halts on w
Turing Machine Acceptance
Given a TM M and input w, determine if M accepts w
Turing Machine Equivalence
Given two TMs M₁ and M₂, determine if L(M₁) = L(M₂)
Turing Machine Finiteness
Given a TM M, determine if L(M) is finite
Select a Problem
Choose a problem from the list to explore its decidability properties