post_correspondence_problem (455B)
1 # Post correspondence problem 2 3 https://en.wikipedia.org/wiki/Post_correspondence_problem 4 5 The [computational_problem], given a set of [word] [pairs] (u_1, v_1), ..., (u_k, v_k), of deciding whether there is a sequence of indices i_1, ..., i_n in {1, ..., k} (potentially with repetitions) so that the concatenations 6 u_{i_1} ... u_{i_n} and v_{i_1} ... v_{i_n} are the same [word] 7 8 It is an [undecidable] problem 9 10 Up: [computational_problem] 11 12 Aliases: PCP