Post correspondence problem

From Academic Kids

The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post. Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.

Informally the problem can be described as follows. Given a dictionary that contains pairs of phrases, i.e., a list of words, that mean the same, decide if there is a sentence that means the same in both languages.

Definition of the problem

The input of the problem consists of two finite lists.

<math>u_1, ..., u_n<math> and <math>v_1, ..., v_n<math>

of words over some alphabet Σ with at least two symbols. A solution to this problem is a sequence of indexes <math>i_1, ..., i_k, 1 \le i_j \le n<math>, such that

<math>u_{i_1}...u_{i_k} = v_{i_1}...v_{i_k}<math>.

The decision problem then is to decide whether such a solution exists or not.

Example of an instance of the problem

Consider the following two lists:

<math>u_1<math> <math>u_2<math> <math>u_3<math> <math>u_4<math> <math>v_1<math> <math>v_2<math> <math>v_3<math> <math>v_4<math>
<math>aba<math> <math>bbb<math> <math>aab<math> <math>bb<math> <math>a<math> <math>aaa<math> <math>abab<math> <math>babba<math>

A solution to this problem would be the sequence 1, 4, 3, 1 because

<math>u_1 u_4 u_3 u_1 = aba + bb + aab + aba = ababbaababa = a + babba + abab + a = v_1 v_4 v_3 v_1<math>

However, if the two lists had consisted of only <math>u_1, u_2, u_3<math> and <math>v_1, v_2, v_3<math>, then there would have been no solution.

A convenient way to view an instance of a Post correspondence problem is as a collection of blocks of the form

<math>u_i<math>
<math>v_i<math>

Thus the above example is viewed as

<math>aba<math>
<math>a<math>
,
<math>bbb<math>
<math>aaa<math>
,
<math>aab<math>
<math>abab<math>
,
<math>bb<math>
<math>babba<math>
<math>i=1<math>

<math>i=2<math>

<math>i=3<math>

<math>i=4<math>

A solution corresponds to some way of laying blocks next to each other so that the string in the top cells corresponds to the string in the bottom cells. Then the solution to the above example corresponds to:

<math>aba<math>
<math>a<math>
,
<math>bb<math>
<math>babba<math>
,
<math>aab<math>
<math>abab<math>
,
<math>aba<math>
<math>a<math>
<math>i_1=1<math>

<math>i_2=4<math>

<math>i_3=3<math>

<math>i_4=1<math>
de:Postsches Korrespondenzproblem
Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools