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)

Examples

Download Example Notebook

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

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]=

Bibliographic Citation

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: 10 May 2017

Source Metadata

Creator: Stephen Wolfram
Source: https://www.wolframscience.com/nksonline/page-757
Citation: Stephen Wolfram, \[OpenCurlyDoubleQuote]A New Kind of Science\[CloseCurlyDoubleQuote] (2002)

Publisher Information

Publisher of Record: Wolfram Research