search
Log In
0 votes
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$.
in Theory of Computation
edited by
98 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
2
29 views
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$.
asked Jul 21, 2019 in Theory of Computation Lakshman Patel RJIT 29 views
0 votes
0 answers
3
0 votes
0 answers
4
...