Here's a funny problem that you may probably know if you read Douglas Hofstadter's wonderful book, Gödel, Escher, Bach. You are given a small alphabet, which consists in the letters M, U and I, and a set of four rules, where x and y denote any string:
Let's start with the string MI. The goal is to convert this string to MU using those rules, that you can reuse at will. I can't remember where I saw this problem mentioned on the internet. There is no solution to this problem, but I keep thinking of this gorgeous book each time I see some mention of Hofstadter's puzzles.