Halting Problem, Rice's Theorem

Interactive Decidability & Computability Explorer

Explore the fundamental limits of computation through interactive simulations and proofs

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
  • kyU emptiness
  • Regular language equality
  • Arithmetic expressions
Undecidable Problems:
  • Halting Problem
  • Post Correspondence Problem
  • kyU equivalence
  • Diophantine equations
semi-decidable:
  • 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 Explorer
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
semi-decidable (R.E.)
Problems with algorithms that halt on "yes" instances
Undecidable
Problems with no algorithmic solution
Problem Reductions