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?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3390 |
| 6 | Um_nik | 3387 |
| 7 | tourist | 3384 |
| 8 | heuristica | 3322 |
| 9 | turmax | 3319 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 4 | AmShZ | 143 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | maroonrk | 134 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
Auto comment: topic has been updated by mani100011 (previous revision, new revision, compare).
Auto comment: topic has been updated by mani100011 (previous revision, new revision, compare).
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
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.
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.
If we could check whether or not a solution exists for a set of tiles, would the problem be decidable?