# Ullman (TOC) Edition 3 Exercise 9.4 Question 4 (Page No. 412)

98 views
A Post tag system consists of a set of pairs of strings chosen from some finite alphabet $\Sigma$ and a start string. If $(w,x)$ is a pair, and $y$ is any string over $\Sigma$, we say that $wy\vdash yx$. That is, on one move, we can remove some prefix $w$ of the "current" string $wy$ and instead add at the end the second component of a string $x$ with which $w$ is paired. Define $\vdash^{*}$ to mean zero or more steps of $\vdash$, just as for derivations in a context-free grammar. Show that it is undecidable.given a set of pairs $P$ and a start string $z$, whether $z\vdash^{*}\epsilon$.
Hint: For each $TM \ M$ and input $w$, let $z$ be the initial $ID$ of $M$ with input $w$, followed by a separator symbol $\#$. Select the pairs $P$ such that any $ID$ of $M$ must eventually become the $ID$ that follows by one move of $M$. If $M$ enters an accepting state, arrange that the current strings can eventually be erased, i.e., reduced to $\epsilon$.

edited

## Related questions

1
29 views
Suppose we limited $PCP$ to a one-symbol alphabet, say $\Sigma = \left\{0\right\}$. Would this restricted case of $PCP$ still be undecidable?
We showed that $PCP$ was undecidable, but we assumed that the alphabet $\Sigma$ could be arbitrary. Show that $PCP$ is undecidable even if we limit the alphabet to $\Sigma = \left\{0,1\right\}$ by reducing $PCP$ to this special case of $PCP$.
Show that the language of codes for $TM's\ M$ that, when started with blank tape, eventually write a $1$ somewhere on the tape is undecidable.