28 views
Show that for $|\Sigma| = 1$, the Post correspondence problem is decidable, that is, there is an algorithm that can decide whether or not $(A, B)$ has a $\text{PC}$ solution for any given $(A, B)$ on a single-letter alphabet.
| 28 views