Interactive Turing Machine Simulator

Visualize Turing machines and understand undecidability through interactive simulations

Controls

Recognizes palindromes over the alphabet {a, b}

SlowFast

Current Status

Ready
Current State:
Steps: 0

Turing Machine Visualization

Understanding Undecidability

The Halting Problem asks whether there exists an algorithm that can determine, for any arbitrary program and input, whether the program will eventually halt or run forever.

The Paradox:

Assume we have a halting detector H that can determine if any program P halts on input I. We can create a new program D that:

  1. Takes a program P as input
  2. Uses H to determine if P halts when given P as input
  3. If H says "P halts on P", then D enters an infinite loop
  4. If H says "P doesn't halt on P", then D immediately halts

Now, what happens if we run D with itself as input? If D halts, then by its definition, it should run forever. If D runs forever, then by its definition, it should halt. This contradiction proves that our halting detector H cannot exist!