Why is the post correspondence problem undecidable?

Question

The post correspondence problem is, to my understanding, given two ordered collections of strings with the same cardinality, i.e., $\{t_1, t_2, \dots, t_n\}$ and $\{w_1, w_2, \dots, w_n\}$, does there exist a rearrangement of the terms such that $t_{i_1} t_{i_2} \dots t_{i_n} = w_{i_1} w_{i_2} \dots w_{i_n}$? Sipser's text has a proof that this problem is undecidable. This strikes me as counterintuitive: if our two sets are finite, there should only exist $n!$ different possible orderings of the strings. Why can a Turing machine not simply test all $n!$ cases and reject if none of these cases produce a match?

Answer 1

The issue is with your description of the post correspondence problem: it's not a rearrangement of the ordered collections of strings, just a selection of indices $i_1, \ldots, i_m$, not necessarily comprehensive and possibly with repeats, and $m$ does not have to be $n$, such that $t_{i_1} t_{i_2} \cdots t_{i_m} = w_{i_1} w_{i_2} \cdots w_{i_m}$. So the algorithm you suggest can't work because there's no bound on the allowable value of $m$, so the search space is no longer finite.