I am asked, "Show that these T-Grammars constitute a set of languages that are undecidable. Do this by building a T-Grammar for a Turing machine description. For a starting point you might think about machine configurations."

I am not sure how configurations is suppose to help, but the grammar that I built:

$$ abc \to def; d \to a; e \to b; f \to c $$

Is this undecidable?

  • 1
    $\begingroup$ What's a T-grammar, and what does it mean for it to be undecidable? $\endgroup$ – Yuval Filmus May 1 '16 at 16:40
  • $\begingroup$ Why do you think your particular grammar is undecidable? $\endgroup$ – Yuval Filmus May 1 '16 at 16:41

Presumably, a T-grammar is undecidable if you cannot decide its word problem: given a word $w$, to decide whether the grammar generates $w$.

(Another option is that we want to show that the following problem is undecidable: given a T-grammar $G$ and a word $w$, decide whether $G$ generates $w$. This slightly simplifies the plan of attack suggested below.)

There are basically two ways to show that a certain problem is undecidable:

  1. Diagonalization.

  2. Reduction to the undecidability of another problem.

Here it's not clear how to diagonalize, so we want to use the second method. We want to come up with some problem P which we already know is undecidable, and construct a grammar G, such that if you could solve the word problem for G, then you could solve problem P.

The hint suggests to use the following class of problems. For each Turing machine T, we can consider the problem to decide, given a word $w$, whether T halts on the input $w$. There exists a Turing machine T for which this problem is undecidable.

This suggests the following course of action: show a method to transform a Turing machine T into a T-grammar G such that T halts on $w$ iff $G$ generates $w$. If we could do that, then we will have proved that the word problem is generally unsolvable for T-grammars.

How do you convert a Turing machine T into a T-grammar G? It is here that machine configurations could become helpful. I'll leave the rest for you to ponder.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.