Solutions to Examples of Post’s Correspondence Problem

A dataset of instances and solutions (if they exist) for Post’s correspondence problem

These were given on page 757 of A New Kind of Science (Wolfram, 2002)

(2 columns, 19 rows)

Examples

Basic Examples

Retrieve the resource:

In[1]:=
ResourceObject["Solutions to Examples of Post\[CloseCurlyQuote]s \
Correspondence Problem"]
Out[1]=

Retrieve the default content:

In[2]:=
ResourceData["Solutions to Examples of Post\[CloseCurlyQuote]s \
Correspondence Problem"]
Out[2]=

Find the correspondences for the first example:

In[3]:=
Normal[ResourceData[
   "Solutions to Examples of Post\[CloseCurlyQuote]s Correspondence \
Problem"][[1, "Correspondences"]]]
Out[3]=

Find the solution for the first example:

In[4]:=
Normal@ResourceData[
   "Solutions to Examples of Post\[CloseCurlyQuote]s Correspondence \
Problem"][[1, "Solution"]]
Out[4]=

Use the solution for the first problem:

In[5]:=
Transpose[
  Normal@ResourceData[
     "Solutions to Examples of Post\[CloseCurlyQuote]s Correspondence \
Problem"][[1, "Correspondences"]]][[All, 
 Normal@ResourceData[
    "Solutions to Examples of Post\[CloseCurlyQuote]s Correspondence \
Problem"][[1, "Solution"]]]]
Out[5]=

Confirm that the strings are the same:

In[6]:=
StringJoin /@ 
 Transpose[
   Normal@ResourceData[
      "Solutions to Examples of Post\[CloseCurlyQuote]s \
Correspondence Problem"][[1, "Correspondences"]]][[All, 
  Normal@ResourceData[
     "Solutions to Examples of Post\[CloseCurlyQuote]s Correspondence \
Problem"][[1, "Solution"]]]]
Out[6]=
In[7]:=
StringJoin /@ 
 Transpose[
   Normal@ResourceData[
      "Solutions to Examples of Post\[CloseCurlyQuote]s \
Correspondence Problem"][[1, "Correspondences"]]][[All, 
  Normal@ResourceData[
     "Solutions to Examples of Post\[CloseCurlyQuote]s Correspondence \
Problem"][[1, "Solution"]]]]
Out[7]=

Make a graphical version of the solution for the 10th problem:

In[8]:=
ArrayPlot[
    {Flatten@Map[StringPartition[#, 1] &, #]},
    ColorRules -> {
      "a" -> Black,
      "b" -> White
      },
    ImageSize -> Large
    ] & /@ 
  Transpose[
    Normal@ResourceData[
       "Solutions to Examples of Post\[CloseCurlyQuote]s \
Correspondence Problem"][[10, "Correspondences"]]][[All, 
   Normal@ResourceData[
      "Solutions to Examples of Post\[CloseCurlyQuote]s \
Correspondence Problem"][[10, "Solution"]]]] // Column
Out[8]=

Show each step of the solution for the 5th problem:

In[9]:=
Row@*
   Map[
    ArrayPlot[
      List@StringPartition[#, 1],
      ColorRules -> {
        "a" -> Black,
        "b" -> White
        },
      ImageSize -> {Automatic, 15}
      ] &
    ] /@ Transpose[
    Normal@ResourceData[
       "Solutions to Examples of Post\[CloseCurlyQuote]s \
Correspondence Problem"][[5, "Correspondences"]]][[All, 
   Normal@ResourceData[
      "Solutions to Examples of Post\[CloseCurlyQuote]s \
Correspondence Problem"][[5, "Solution"]]]] // Column
Out[9]=

Wolfram Research, "Solutions to Examples of Post’s Correspondence Problem" from the Wolfram Data Repository. (2017) https://doi.org/10.24097/wolfram.68271.data

Source Metadata