  Let PCP(k) denote the Post Correspondence Problem for k input pairs of
strings. Let ACCESSIBILITY(k) denote the the word problem for k-rule semi-Thue
systems. In 1980, Claus showed that if ACCESSIBILITY(k) is undecidable then
PCP(k + 4) is also undecidable. The aim of the paper is to present a clean,
detailed proof of the statement.
  We proceed in two steps, using the Generalized Post Correspondence Problem as
an auxiliary. First, we prove that if ACCESSIBILITY(k) is undecidable then
GPCP(k + 2) is also undecidable. Then, we prove that if GPCP(k) is undecidable
then PCP(k + 2) is also undecidable. (The latter result has also been shown by
Harju and Karhumaki.) To date, the sharpest undecidability bounds for both PCP
and GPCP have been deduced from Claus's result: since Matiyasevich and
Senizergues showed that ACCESSIBILITY(3) is undecidable, GPCP(5) and PCP(7) are
undecidable.
