Decidability & Computability

Decidability & Computability Visually

Explore decidability, undecidability, and computability theory with interactive simulations of the Halting Problem, Rice Theorem, and reduction techniques.

Halting Problem Reductions Rice's Theorem Complexity Hierarchy

Decidability & Computability Theory

Decidability and Computability theory studies the fundamental limits of what can be computed algorithmically. It explores which problems can be solved by algorithms and which are inherently unsolvable, providing crucial insights into the nature of computation itself.

Decidable Problems:
  • DFA acceptance
  • CFG emptiness
  • Regular language equality
  • Arithmetic expressions
Undecidable Problems:
  • Halting Problem
  • Post Correspondence Problem
  • CFG equivalence
  • Diophantine equations
xi0:
  • TM acceptance
  • Program termination
  • Theorem proving
  • Context-sensitive membership

Choose Problem to Explore

Select from various decidability and computability problems

Halting Problem
Rice's Theorem
Post Correspondence
Turing Reductions
Complexity Hierarchy

Interactive Halting Problem Simulator

Enter a Simple Program:
Example Programs:
Terminating Program: Simple countdown loop
Infinite Loop: Never-ending while loop
Complex Program: Collatz conjecture
Conditional Halting: Input-dependent termination
Interactive Proof xXj
Theorem: The Halting Problem is Undecidable

There is no algorithm that can determine, for arbitrary program P and input I, whether P halts on input I.

Step 1: Assume for contradiction that such an algorithm H exists
Step 2: Construct a new program D using H
Step 3: Analyze what happens when D is given itself as input
Step 4: Derive a contradiction
Analysis Statistics
Programs Analyzed: 0
Terminating: 0
Non-terminating: 0
Undetermined: 0
Average Analysis Time: 0ms
Decidability Hierarchy
Decidable (Recursive)
Problems with algorithms that always halt
xi0 (R.E.)
Problems with algorithms that halt on "yes" instances
Undecidable
Problems with no algorithmic solution
Problem Reductions