17.7. Finding Counterexamples

Counterexamples

---

Most of what we did this term has been concerned with demonstrating that a problem is not in a particular class of problems.

To show that problem X is not solvable by an algorithm of type T, we can design an algorithm that solves the following problem.

Input. A program or machine M of type T.

Output. A string y on which M gets the wrong answer. That is, if y ∈ X then M says that y ∉ X, and if y ∉ X then M says that y ∈ X.

String y is a counterexample for M.

Since our algorithm finds a counterexample for every program or machine of type T, no such program or machine can solve X.

Finite-state

---

To show that a given set X of strings cannot be solved by a finite-state machine, the counterexample-finding algorithm relies on a selected infinite list of strings y₁, y₂, … The choice of this list is part of algorithm discovery.

Then the algorithm works as follows on input M.

1. Run M on y₁, y₂, … until two of them, y_i and y_j are found so that M ends on the same state, q, on both.

   Such strings must exist because M has finitely many states. If M has k states, then it cannot end of a different state on all of y₁, y₂, … y_k+1.

2. Find a third string s so that y_i s ∈ X but y_j s ∉ X. List y₁, y₂, … should be very simple so that finding s is easy.

3. Conclude that, because M ends on the same state on y_i and y_j, M must also end on the same state on y_i s and y_j s.

   Since M 's answer depends only on the state where it ends, M must give the same answer on y_i s and y_j s.

   But the correct answers to y_i s and y_js are different. So one of y_i s and y_j s is a counterexample. Choose the one that M gets wrong.

See this example.

You should be prepared to demonstrate that a given language (set of strings) cannot be solved by any finite-state machine.

Diagonalization

---

To show that a given problem is not computable by a (deterministic) Turing machine, we need a more powerful way to find a counterexample. We did that for the acceptance problem for Turing machines, using a method called diagonalization.

The idea of diagonalization is at its simplest for showing that K = {x | φ_x(x)↓} is not computable.

On input M (a program that is purported to solve K ), find a counterexample as follows.

1. Construct program F so that, for every x,

   φ_F (x)↑ ⇔ φ_M (x) = yes.

2. Since that equivalence is true for every x, it must be true for x = F. That is,

   φ_F (F)↑ ⇔ φ_M (F) = yes.

   But, by the definition of K,

   φ_F (F)↑ ⇔ F ∉ K.

   Putting those two equivalences together:

   F ∉ K ⇔ φ_M (F) = yes.

3. The counterexample is F; clearly, M gives the wrong answer about membership in K on input F.

I will not ask you to do a proof by diagonalization.