CS 456/656 A Proof that Every Language is Decidable
Theorem: Every language L is decidable.
Proof: For each integer n, let Ln be the language consisting
of all strings of L of length n.
Since Ln is finite, it is regular, hence decidable. Let
Mn be a machine that decides Ln.
We can now decide L by the following algorithm:
Let w be any input string. Let n = |w|. Run Mn with w as
input. Whatever answer it gives is our answer.
What is wrong with this proof?
Back to
Course Page