A translation puzzle

Your task is to write down a sequence of English words that, after possibly moving around the spaces between the words, become their German translations.

As stated, this is pretty easy: for instance, I could write down the single English word SAND which translates to the single German word SAND. Or I could be a tiny bit more ambitious and write down a sequence of words like SAND PARK RADIO, which is similarly unchanged after translating into German.

But suppose we generalised away from just “English and German” and used a pair of languages that share an alphabet but don’t have any words that self-translate like that. Then the problem becomes rather harder because you might have to actually shuffle the spaces around in order to find a solution.

For instance, perhaps the dictionary looks like this:

Language 1Language 2

Can you come up with a sequence of words in Language 1 that, after possibly moving around the spaces, become their Language 2 translations? Here’s one:


is a sequence of words in Language 1, and if I move the spaces around I can get


which is exactly the same sequence translated into Language 2.

Although that particular example wasn’t too hard in the end, it turns out that this is a rather hard problem to solve in general. In fact, it’s an instance of the Post Correspondence Problem, which is famously undecidable. That means that it’s impossible to write a program that is capable of taking any translation dictionary you can think of and telling you whether or not a solution exists.

Might still be fun to try, though.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s