The Gateway to Computer Science Excellence
0 votes
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 by Veteran (58.8k points)
edited by | 65 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
104,903 users