Post Correspondence Problem And Decidability Philosophy Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

In the terms of logic, the term decidable refers to the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas (or theorems) can be effectively determined. A theory (set of formulas closed under logical consequence) in a fixed logical system is decidable if there is an effective method for determining whether arbitrary formulas are included in the theory.

A logical system is decidable if there is an effective method for determining whether arbitrary formulas are theorems of the logical system. For example, propositional logic is decidable, because the truth-table method can be used to determine whether an arbitrary propositional formula is logically valid.

A theory is a set of formulas, which here is assumed to be closed under logical consequence. The question of decidability for a theory is whether there is an effective procedure that, given an arbitrary formula in the signature of the theory, decides whether the formula is a member of the theory or not. This problem arises naturally when a theory is defined as the set of logical consequences of a fixed set of axioms. Examples of decidable first-order theories include the theory of real closed fields, and Presburger arithmetic, while the theory of groups and Robinson arithmetic are examples of undecidable theories.

A consistent theory which has the property that every consistent extension is undecidable is said to be essentially undecidable. In fact, every consistent extension will be essentially undecidable. The theory of fields is undecidable but not essentially undecidable. Robinson arithmetic is known to be essentially undecidable, and thus every consistent theory which includes or interprets Robinson arithmetic is also (essentially) undecidable.

Let a language be any set of strings (or words) over a given finite alphabet. The alphabet could consist of the symbols we normally use for communication, such as the ASCII characters on a keyboard, including spaces and punctuation marks. In this way any story can be regarded as a "word".

Definition: A language is called decidable if there exists a method - any method at all - to determine whether a given word belongs to that language or not.


The Post correspondence problem is an un decidable decision problem that was introduced by Emil Post in 1946.Because it is simpler than the halting problem and the Entscheidungs problem it is often used in proofs of un decidability. The Post correspondence problem (due to Emil Post) is another undecidable problem that turns out to be a very helpful tool for proving problems in logic or in formal language theory to be undecidable. In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem. The answer can be either 'yes' or 'no', and depends upon the values of x and y.

Decision problems are closely related to function problems, which can have answers that are more complex than a simple 'yes' or 'no'. A corresponding function problem is "given two numbers x and y, what is x divided by y?". They are also related to optimization problems, which are concerned with finding the best answer to a particular problem.

The most common proof for the undecidability of PCP describes an instance of PCP that can simulate the computation of a Turing machine on a particular input. A match will only occur if the input would be accepted by the Turing machine. Because deciding if a Turing machine will accept an input is a basic undecidable problem, PCP cannot be decidable either.

Many variants of PCP have been considered. One reason is that, when one tries to prove undecidability of some new problem by reducing from PCP, it often happens that the first reduction one finds is not from PCP itself but from an apparently weaker version.

A simple variant is to fix n, the number of tiles. This problem is decidable if n ≤ 2, but remains undecidable for n ≥ 7. It is unknown whether the problem is decidable for 3 ≤ n ≤ 6.

Another variant of PCP is called the marked Post Correspondence Problem, in which each ui must begin with a different symbol, and each vi must also begin with a different symbol. Halava, Hirvensalo, and de Wolf showed that this variation is decidable in exponential time. Moreover, they showed that if this requirement is slightly loosened so that only the two-character prefixes need to differ (the so-called 2-marked Post Correspondence Problem), the problem becomes undecidable again.

One of the most important variants of PCP is the bounded Post correspondence problem, which asks if we can find a match using no more than k tiles, including repeated tiles. A brute force search solves the problem in time O(2k), but this may be difficult to improve upon, since the problem is NP-complete[4]. Unlike some NP-complete problems like the boolean satisfiability problem, a small variation of the bounded problem was also shown to be complete for RNP, which means that it remains hard even if the inputs are chosen at random (it is hard on average over uniformly distributed inputs).

The circular Post correspondence problem asks whether indexes i1,i2,... can be found such that and are conjugate words, i.e., they are equal modulo rotation. This variant is undecidable[3].

Post's correspondence problem is very useful for showing the undecidability of many other problems by means of reducibility. Its undecidability follows from its capacity for simulating the computations of Turing machines, as exhibited indirectly in the following proof through derivations in Type 0 grammars.

The following corollary exhibits how Post's correspondence problem can be used to show the undecidability of some other problems by means of reducibility.

Corollary 4.7.1    The equivalence problem is undecidable for finite-state transducers.

Proof     Consider any instance <(x1, y1), . . . , (xk, yk)> of PCP. Let be the minimal alphabet such that x1, . . . , xk, y1, . . . , yk are all in *. With no loss of generality assume that = {1, . . . , k} is an alphabet.

Let M1 = <Q1, , , 1, q0, F1> be a finite-state transducer that computes the relation * Ã- *, that is, a finite-state transducer that accepts all inputs over , and on each such input can output any string over .

Let M2 = <Q2, , , 2, q0, F2> be a finite-state transducer that on input i1 in outputs some w such that either w xi1 xin or w yi1 yin. Thus, M2 on input i1 in can output any string in * if xi1 xin yi1 yin. On the other hand, if xi1 xin = yi1 yin, then M2 on such an input i1 in can output any string in *, except for xi1 xin.

It follows that M1 is equivalent to M2 if and only if the PCP has a negative answer at the given instance <(x1, y1), . . . , (xk, yk)>.