[dblotsky]

This looks like the Post Correspondence Problem at first glance: https://en.m.wikipedia.org/wiki/Post_correspondence_problem.

[saagarjha]

It’s similar, but in this case the decision is removed as it is given that a solution exists.