Homepage

Read Fullscreen

RE: Did Anyone Solve the MU-Puzzle in Chapter 1?

EDIT 2: Alrighty, so it was quickly shown by both Joe in the comments and Alex over on his blog that my third hypothesis (“I’m missing something.”) was correct. No, I did not prove wikipedia wrong nor did I discover bugs in both Erlang and Ruby. The lesser Paul inside me is tempted to delete this post and my embarassing jumping to conclusions, but I think I’ll let it stand. Thanks guys :)

EDIT: The divisibility test for 3 (if a number is divisible by 3) is if the sum of it’s digits is divisible by 3. so 405 = 4 + 5 = 9, thus 405 is divisible by 3. The sum of the digits of 18014398509481984 is 82, and recursively 8 + 2 = 10 which clearly *isn’t* divisible by three. So there’s a disproof right there, but still I’m trying to figure out why the computer doesn’t agree…

godelescherbach:

SPOILER ALERT. Mouseover this link to see my response.

Yes I think I did, but wikipedia says it’s impossible. I want someone to show me why my proof is wrong.

Background:

For Christmas I got Godel Escher Bach and just started reading it. So far it’s really good and surprisingly readable. When godelescherbach came up on the staff tumblr picks, I decided to start following it.

The MU puzzle in question is very early in the book, here’s the rephrasing of the question from wikipedia:

(ref http://en.wikipedia.org/wiki/MU_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:

  1. Add a U to the end of any string ending in I. For example: MI to MIU.
  2. Double any string after the M (that is, change Mx, to Mxx). For example: MIUto MIUIU.
  3. Replace any III with a U For example: MUIIIU to MUUU.
  4. Remove any UU. For example: MUUU to MU.

Using these four rules is it possible to change MI into MU in a finite number of steps?

I think I found a solution. But there is a small issue: when I went to wikipedia to remind myself of the wording of the problem I saw wikipedia’s solution, which is the opposite of mine. Namely, according to wikipedia the answer is ‘no’ you can’t produce MU.

The proof of infeasbility (not a word but who cares) is this: By step 2, you can only grow Is by doubling the number of Is. Or the number of Is is always a power of 2. By step 3 you need to divide those Is into groups of 3 to get Us. But no power of 2 is divisible by 3, ergo impossible.

It’s that last part I take issue with. My approach is brute-force programmer not elegant mathemetician. But here’s the thing:

Both Ruby and Erlang are supposed to have arbitrary precision numbers, both are widely used very well tested and this is for all intents and purposes true. So they both should easily be able to handle any calculator-like task I throw at it.

First in Ruby:

irb(main):004:0> num = 2 ** 54

=> 18014398509481984

Great, so 2 ^ 54 =

And

irb(main):007:0> num / 3.0=> 6004799503160661.0

Oops, according to Ruby 2 ^54 *is divisible by 3! Into 6004799503160661 groups of 3 specfically.


Let’s verify in erlang, a totally different runtime, language, everything.

1> Num = math:pow(2,54).

18014398509481984.0

2> Divd = Num / 3.0 .

6004799503160661.0

Erlang ALSO thinks that 2^54 is divisible by 3, and with the same result.

So either I’ve found a very strange coinciding bug into two completely different, well tested programming languages, or Wikipedia’s wrong, or more probably, I’m missing something.

Assuming the computer is correct, here’s a straight forward proof/algorithm for producing MU from MI.

MI

number of Is can be any power of 2 (by step 2)

after 54 doublings

M is followed by 18014398509481984 Is. (2^ 54)  (by step 2)

Fortunately, 2^54 is divisible by 3.

So divide the 18014398509481984 Is into 6004799503160661 groups of 3,

and convert each group into a U.  (by step 3)

So M is now followed by 6004799503160661 Us.

Since there are an odd number of Us, clearly one less

Us is an even number, or (6004799503160661 - 1) =

6004799503160660 is even. So make 3002399751580330 groups of

2 Us and remove every group. That leaves the 1 U that was on the end.

Thus we have produced MU.