<p>Given a set of pairs of words $P = \{(\alpha_1, \beta_1), \dots, (\alpha_n, \beta_n)\} \subseteq \Sigma^*\times\Sigma^*$, the <em>Post Correspondence Problem</em> (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}$.</p>

<p>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$.</p>

<p>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.</p>

<p>It seems only fair to ask: </p>

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

<p>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 <em>need</em> the kind of self-applicability we employ when proving HP not to be computable?</p>

<p><em><strong>PS:</strong> 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.</em></p>

CC BY-SA 3.0
2011-07-18T18:51:56.040Z
[related question](http://cstheory.stackexchange.com/questions/2853/are-there-any-proofs-the-undecidability-of-the-halting-problem-that-does-not-depe)
Kaveh
CC BY-SA 3.0
2011-07-18T19:06:06.123Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-18T19:22:21.700Z
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).
Raphael
CC BY-SA 3.0
2011-07-18T19:33:22.870Z
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).
Kaveh
CC BY-SA 3.0
2011-07-19T12:48:09.130Z
@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](http://en.wikipedia.org/wiki/Halting_problem)) 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)
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-19T12:51:07.350Z
(cont’d)  So it seems unlikely to me that you can get a more accessible proof by considering the Post correspondence problem directly.  I am happy if I am proven wrong.
Tsuyoshi Ito
CC BY-SA 3.0
2011-07-19T13:35:18.983Z
Tsuyoshi: precisely the fact that you can explain that HP can not be decidable without a formal definition got me asking (as you _need_ the precise definition for the reduction, afaik).
Raphael
<reference-request><computability><post-correspondence>
Prove Post Correspondence Problem Non-Recursive Without Reduction
Raphael
# Prove Post Correspondence Problem Non-Recursive Without Reduction

(Asked by: username_0 on 2011-07-18)

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.*

**Tags:** reference-request, computability, post-correspondence
> **Comments:**
> **username_1**: [related question](http://cstheory.stackexchange.com/questions/2853/are-there-any-proofs-the-undecidability-of-the-halting-problem-that-does-not-depe)  
> **username_2**: 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.  
> **username_0**: 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).  
> **username_1**: 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).  
> **username_2**: @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](http://en.wikipedia.org/wiki/Halting_problem)) 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)  
> **username_2**: (cont’d)  So it seems unlikely to me that you can get a more accessible proof by considering the Post correspondence problem directly.  I am happy if I am proven wrong.  
> **username_0**: Tsuyoshi: precisely the fact that you can explain that HP can not be decidable without a formal definition got me asking (as you _need_ the precise definition for the reduction, afaik).  

---

## 0 answers

