65 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 | 65 views