can you get to mu?

[amezri]

I had written this puzzle down when I was in junior high and had it tacted to my wall for ages. Then I cleaned my room and I don't know what I did with it. With cassiejamie and some others talking about sudoku, I remembered this thing and of course couldn't find the sheet anywhere. Anyway, spent the last few days trying to find some reference to it online and finally located it on this blog. Really long explanation for something that isn't exactly what I remembered, but might still be interesting enough to puzzle out.

Apparently, it's a formal system based on the ability to generate strings following a set of rules. If I'm understanding this right.

Douglas R. Hofstadter uses this example in Gödel, Escher, Bach:

Begin with the state MI.

Can you get the system to the state MU using only these four transformations (any combination, as many times as needed)?

• if the string ends with I you may add U; for example, MI becomes MIU


• if the string is Mx then you may create Mxx; for example, MI becomes MII; MIU becomes MIUIU


• if the string contains III you may replace those three characters with U


• if the string contains UU you may eliminate both characters

When my brain is more functional I might give it a try.

Comments

[tylergrrls.livejournal.com]

Sounds like a turing machine problem. Or a CFG.

That's the kind of stuff we do in my 350 class... "Automotan and Formal Language Theory"

-Bree

[amezri.livejournal.com]

Yeah. I did some more searching and a lot of the sites that mention formal systems also mention... typographical rewrite systems I think it was, in relation to AI or something.