Wolfram Research

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)

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

Data Resource History

  • Date Created: 10 May 2017

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