Wolfram Data Repository

Immediate Computable Access to Curated Contributed Data

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 default content:

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

Find the correspondences for the first example:

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

Find the solution for the first example:

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

Use the solution for the first problem:

In[4]:=
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[4]=

Confirm that the strings are the same:

In[5]:=
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[5]=
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]=

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

In[7]:=
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[7]=

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

In[8]:=
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[8]=
In[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

Data Resource History

  • Date Created:

Source Metadata

  • Creator: Stephen Wolfram
  • Source: https://www.wolframscience.com/nksonline/page-757
  • Citation: Stephen Wolfram, “A New Kind of Science” (2002)

Publisher Information

  • Publisher of Record: Wolfram Research