and indeed any computable function or computable set at all.

Correspondence systems were introduced by Post in 1946 to give simple examples of undecidability. He showed that the Post correspondence problem (PCP) of satisfying their constraints is, in general, undecidable. The undecidability of the correspondence problem turned out to be exactly what was needed