The Puzzle
Suppose there are the symbols M
, I
, and U
which can be combined to produce strings of symbols called "words". The MU puzzle asks one to start with the "axiomatic" word MI
and transform it into the word MU
using in each step one of the following transformation rules:
- Add a
U
to the end of any string ending inI
. For example:MI
toMIU
. - Double any string after the
M
(that is, changeMx
, toMxx
). For example:MIU
toMIUIU
. - Replace any
III
with aU
. For example:MUIIIU
toMUUU
. - Remove any
UU
. For example:MUUU
toMU
.
Using these four rules is it possible to change MI
into MU
in a finite number of steps?
The production rules can be written in a more schematic way. Suppose x
and y
behave as variables (standing for strings of symbols). Then the production rules can be written as:
xI → xIU
Mx → Mxx
xIIIy → xUy
xUUy → xy
Is it possible to obtain the word MU
using these rules?
Read more about this topic: MU Puzzle
Famous quotes containing the word puzzle:
“The at present unutterable things we may find somewhere uttered. These same questions that disturb and puzzle and confound us have in their turn occurred to all the wise men; not one has been omitted; and each has answered them, according to his ability, by his words and his life.”
—Henry David Thoreau (18171862)
“Waiting for the race to become official, he began to feel as if he had as much effect on the final outcome of the operation as a single piece of a jumbo jigsaw puzzle has to its predetermined final design. Only the addition of the missing fragments of the puzzle would reveal if the picture was as he guessed it would be.”
—Stanley Kubrick (b. 1928)