MOOONI's blog

A question about the "Post Correspondence problem"
By MOOONI, history, 18 months ago, In English

Hey everyone, hope you're having a great day. Here's a question about the famous post correspondence problem This problem is undecidable according to Wiki Pedia, which means there are no algorithms to solve the problem. but can't we simply try all possible permutations of the dominos? what am I misunderstanding?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by MOOONI (previous revision, new revision, compare).

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by MOOONI (previous revision, new revision, compare).

→ Reply
»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

If you try all possible permutations, you would still have no guarantee of finding a solution because it is possible for the PCP to have no solution

→ Reply
»
18 months ago, # |
  Vote: I like it +8 Vote: I do not like it

My understanding is that the main issue is that the length of the answer can be arbitrarily large. This is because you're not just permuting the two lists of dominos -- you are actually allowed to repeat dominos as much as you like.

As the other commenter said, there can be no solution. So the naive algorithm of iterating over the length of the answer and trying all solutions of that length might never halt, because you never know if the solution is just really long or if none exist.

→ Reply
»
18 months ago, # |
  Vote: I like it +12 Vote: I do not like it

What makes the PCP problem undecidable is precisely the unlimited number of times a given tile can be used. If the number of tiles that could be used was bounded, your solution would indeed decide the problem. However, since you have an unlimited supply of tiles, you would have to find and check “all permutations of an infinite set of tiles”, which doesn’t quite work.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If we could check whether or not a solution exists for a set of tiles, would the problem be decidable?

    → Reply