Given a set of pairs of words $P = \{(\alpha_1, \beta_1), \dots, (\alpha_n, \beta_n)\} \subseteq \Sigma^*\times\Sigma^*$, the Post Correspondence Problem (PCP) is to decide wether or not there are indices $i_1, \dots, i_k \in \{1\dots n\}$ such that $\alpha_{i_1}\cdot \dots \cdot \alpha_{i_k} = \beta_{i_1}\cdot \dots \cdot \beta_{i_k}$.

It is well known that PCP is not computable in any Turing-equivalent machine model. Usually, this fact is proven by reducing the Halting Problem (HP) to PCP, i.e. describing how to create a PCP instance $\Pi$ for an arbitrary Turing machine $M$ and an input $x$ such that $\Pi$ has a solution if and only if $M$ terminates on $x$.

Arguably, undecidability of PCP is more useful than of HP because it is removed from the notion of computation itself and therefore might be understood without having to read up on Turing machines (or equivalent models) first. Also, it is a more natural choice for many reduction proofs for not computation-related problems, e.g. in formal language theory.

It seems only fair to ask:

Is there a proof for undecidability of PCP that does not employ reduction to HP (or similar problems)?

Note that I want to exclude chains of reductions that end up at HP in the end. Having such an independent proof might open up new ways for students and laymen to understand the underlying issues. Failing that, are there reasons for that lack? Do we need the kind of self-applicability we employ when proving HP not to be computable?

PS: I was unsure wether or not this question should go here or rather onto math.SE. As the proper place might depend on the level of answers, I went with the specialist community.

  • 1
    $\begingroup$ related question $\endgroup$
    – Kaveh
    Jul 18, 2011 at 18:51
  • 2
    $\begingroup$ You need the notion of Turing machines or some equivalent model first to define what “undecidable” means. Therefore, while I will not rule out the possibility of a proof completely different from the usual proof via the halting problem, I doubt that your approach can give a proof which does not require the knowledge on Turing machines or any of the equivalent models. $\endgroup$ Jul 18, 2011 at 19:06
  • $\begingroup$ You are certainly right. But then, you need a very formal introduction to a machine model and its enumeration in order to perform the usual diagonalisation rigorously. My hope is that a self-contained proof for PCP might work with rather shallow prior knowledge (on computability). $\endgroup$
    – Raphael
    Jul 18, 2011 at 19:22
  • $\begingroup$ Tsuyoshi is right, you need some definition of what is a computable set. One possibility is using "machine independent" logical definitions for computable sets and functions ($\Delta_1$ and $\Sigma_1$). But the diagonalization argument needs encoding at least basic computation about encoding/decoding sequences and manipulating them (like substituting the Godel code of a formula for a free variable of another formula) (AFAIK). $\endgroup$
    – Kaveh
    Jul 18, 2011 at 19:33
  • $\begingroup$ @Raphael: I see your motivation, but note that casual reading of the usual proof of undecidability of the halting problem (such as the one in Wikipedia) does not necessarily require the precise definition of decidability. On the other hand, if someone wants to understand a proof of undecidability of any problem rigorously, it is crucial to understand a rather precise definition of decidability, no matter which problem and which proof you use. (more) $\endgroup$ Jul 19, 2011 at 12:48


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.