Computation Histories

We conclude the discussion of undecidability with a few more examples of languages that one might not expect to be undecidable.

Definition

The configuration of a Turing Machine at some point of time consists of the the content of the tape, the position of the head on that tape, and the state of the DFA.

We can represent any configuration of a TM using a string wqvwqv where

  • ww is the string of symbols on the tape to the left of the head;
  • qq is the DFA controller’s current state;
  • vv is the string of symbols at and to the right of the head.

The infinite blank part of the tape to the left of ww and the right of vv is left implicit.

Even though the tape is infinite, at any instant during a computation there are only finitely many non-blank symbols on the tape. The TM starts with a tape that is blank except for the finite input string, and after finitely many steps the TM can have written to only finitely many squares on the tape.

Definition

A Computation History is a step-by-step (finite) trace of a Turing Machine’s computation, represented as a string.

For example if a TM takes threes step through the successive configurations

q011 ⇒ 1q01⇒ 11q0 ⇒ 111qaq_011\ \Rightarrow\ 1q_01\Rightarrow\ 11q_0\ \Rightarrow\ 111q_a

then we can represent this history as a finite string:

#q011#1q01#11q0#111qa#\#q_011\#1q_01\#11q_0\#111q_a\#

Definition

A history checker for MM accepting ww is a Turing Machine that takes an input string hh checks whether hh is a valid computation history showing MM accepting w.w.

Such a machine always exists for any MM and any ww; it just needs to check whether

  • the input hh consists of configurations separated by #\#;
  • the first configuration has the TM’s head in its start state positioned at the beginning of the string ww;
  • successive configurations differ only around the head, in exactly the ways corresponding to the MM’s transitions; and
  • the last configuration has the TM in an accepting state.

Note that a history checker for MM accepting ww always exists whether or not MM accepts ww! If MM accepts ww then there is a history showing the trace of that computation, and this string will be accepted by the history checker. But if MM does not accept ww, there is no such finite trace. As a consequence, any purported trace we give to the history checker will be found to be flawed, and the history checker won’t accept any strings at all.

This observation immediately gives us a different way to prove a known fact:

Example

Here’s another proof that ETM={  ⟨M⟩ ∣ L(M)=∅ }E_\mathrm{TM} = \{\ \ \langle M\rangle\ |\ L(M)=\emptyset\ \} is not semidecidable.

Proof. We will show that ¬ATM≤mETM\lnot A_\mathrm{TM} \leq_m E_\mathrm{TM}.

Let ff be the function that turns ⟨M,w⟩\langle M,w\rangle into the code of a history checker for MM accepting ww.

  • If ⟨M,w⟩∈¬ATM\langle M,w\rangle \in \lnot A_\mathrm{TM} then MM does not accept ww, so there no computation history that shows how MM accepts ww, so there are no strings accepted by the corresponding history checker and its language is empty.
  • If ⟨M,w⟩∉¬ATM\langle M,w\rangle \not\in \lnot A_\mathrm{TM} then there is a computation history showing how MM accepts ww, so the corresponding history checker accepts that string and its language is not empty.

Undecidability and CFLs

The idea of computation histories lets us prove surprising facts about context-free languages.

Example

While it is easy to decide whether a context-free grammar generates any strings at all (whether its language is nonempty), it is undecidable whether a context-free grammar can generate all possible strings!

That is, the language

ALLCFG ={⟨G⟩ ∣ L(G)=Σ∗ }\mathit{ALL}_\mathrm{CFG}\ = \{ \langle G\rangle\ |\ L(G)=\Sigma^*\ \}

is not decidable.

Proof Sketch. One can show that ¬ATM≤mALLCFG\lnot A_\mathrm{TM} \leq_m \mathit{ALL}_\mathrm{CFG}.

The fundamental trick is that given ⟨M,w⟩\langle M,w\rangle, the strings that are not valid computation histories are (with one small hack) context-free.

So asking whether MM fails to accept ww is equivalent to asking whether all strings are not valid histories showing MM accept ww, which in turn is equivalent to asking whether the language of CFG generating strings that are not valid histories includes all possible strings.

To see why strings that are not valid computation histories are context-free, it is a little easier to think about PDAs rather than grammars. A trace is not a valid history of MM accepting ww if it has at least one error, such as:

  • The first configuration does not have the TM in its start state, or ww is not on the tape;
  • The final configuration does not have the TM in its accepting state; or
  • There are two consecutive configurations that don’t match up according to the transitions of the TM.

We can find each sort of error using a PDA, and then can create one “super” PDA that nondeterministically chooses which kind of error to look for (and in the case of consecutive configurations, nondeterministically choose where in the string to find those configurations). If an error exists, the nondeterministic PDA is guaranteed to find it. (And if a PDA exists, then there is a corresponding CFG.)

Example

It is not even semidecidable whether two CFGs parse the same strings (i.e., produce the same language). That is,

EQCFG={ ⟨G1,G2⟩ ∣ L(G1)=L(G2) }\mathit{EQ}_\mathrm{CFG} = \{\ \langle G_1,G_2\rangle\ |\ L(G_1)=L(G_2)\ \}

is not decidable and not semidecidable.

Proof. We can show that ALLCFG≤mEQCFG\mathit{ALL}_\mathrm{CFG} \leq_m \mathit{EQ}_\mathrm{CFG} using a mapping that sends ⟨G⟨\langle G\langle to the pair G,GallG, G_\mathit{all} where GallG_\mathit{all} is a context-free grammar specifically constructed to generate all strings in Σ∗)\Sigma^*).