The Post's Correspondence Problem (PCP) gives you a list of pairs of strings, P_1 ... P_n. Your task is to find a k, and some sequence of k indices such that fst(P_i1) ... fst(P_ik) = snd(P_i1) ... snd(P_ik)
We're trying to find some sequence of the pairs where the word we build from the first part is equal to the word on the second part. A solution can use any of the pairs any number of times, and in any order.
For example, if our pairs are
(001,100) , then one solution is the world
11001110, with the solution sequence of
11 001 11 0 1 100 1 110
Some will have no solution, such as
An arbitrary number of words, separated by spaces.
Each word is of the format
seq1,seq2 where each
seq2 are strings consisting only of 0 or 1, of arbitrary length.
Example: the above examples would have the following formats:
0,110 11,1 001,110 001,01 0001,01
If there is some sequence of the pairs which solves the PCP, output the word of the solution, followed by a space, followed by the sequence. The pairs are numbered starting at 1.
If there is no such sequence, run forever. (The problem is undecidable, so this will have to do).
11001110 2321 # second example never halts
This is Turing Complete, so you're going to have to use some sort of infinite search.