Notes - Models of Computation MT23, Post correspondence problem
Flashcards
Given the dominoes
\[P = \left[ \frac{b}{ca}, \frac{a}{ab}, \frac{ca}{a}, \frac{abc}{c} \right]\]
What is the Post correspondence problem?
Does there exist a selection of dominoes (including repetitions) so that reading the top and bottom seperately gives the same string?
What’s the basic idea behind the proof of the undecideability of the Post correspondence problem?
Show that if we could solve the Post correspondence problem, we could solve $A _ {\text{TM}\,}$, by designing a set of dominoes such that a solution shows how to find an accepting state in the Turing machine.
The Post correspondence problem is that given a collection $P$ of dominoes
\[P = \\{\left[\frac{t_1}{b_1}\right], \cdots, \left[\frac{t_k}{b_k}\right]\\}\]
where $k \ge 1$ and $t _ i$ and $b _ j$ are strings over $\Sigma$, does there exist a match for $P$, i.e. a non-empty sequence $i _ 1, \cdots, i _ l$ where each $1 \le i _ j \le k$ and
\[t_{i_1} t_{i_2} \cdots t_{i_\ell} = b_{i_1} b_{i_2} \cdots b_{i_l}\]
In this context, what is the MPCP problem used in the proof of the undecidability of PCP?
The Post correspondence problem is that given a collection $P$ of dominoes
\[P = \\{\left[\frac{t_1}{b_1}\right], \cdots, \left[\frac{t_k}{b_k}\right]\\}\]
where $k \ge 1$ and $t _ i$ and $b _ j$ are strings over $\Sigma$, does there exist a match for $P$, i.e. a non-empty sequence $i _ 1, \cdots, i _ l$ where each $1 \le i _ j \le k$ and
\[t_{i_1} t_{i_2} \cdots t_{i_\ell} = b_{i_1} b_{i_2} \cdots b_{i_l}\]
Can you give a brief outline of the proof that PCP is undecideable?
- Modify to
- Show that MPCP is undecidable by a reduction from $A _ \text{TM}$, i.e. given a TM $M$ with input $w$, construct dominoes $P’$ such that
- Convert $P’$ to $P$, an instance of PCP, such that