7 ms·

MU puzzle

83 points by bladecatcher 8y ago

arkadiyt 8y ago
People who like this might also enjoy the similarly simple (yet unsolved) Collatz Conjecture: https://en.wikipedia.org/wiki/Collatz_conjecture https://en.wikipedia.org/wiki/Collatz_conjecture
- Intermernet 8y ago
  On a slight tangent, I recently read a paper on an interesting relationship between Collatz path length and Mersenne primes. "Our main finding to report is the fact that a path length of a Mersenne prime is approximately proportional to its index for large n, namely, D(Mn) ≈ 13.45n." Paper is at https://arxiv.org/pdf/1104.2804.pdf https://arxiv.org/pdf/1104.2804.pdf . WARNING: PDF.
  - jamescostian 8y ago
    I'm curious, why do people on HN warn about PDFs? The worst things I can imagine happening with PDFs are (1) you don't have any software that can read it (probably like .2% of HNers?) and (2) it could potentially have some malware (but the same could be said of a website)
    - hermitdev 8y ago
      Adobe is not known for their security. PDF is also known to allow remote execution via PDF. Default reader on most systems being Adobe's reader, yeah, I'd avoid it. I know this is shifting as browsers incorporate readers, but the format is tarnished.
    - geofft 8y ago
      Before the advent of built-in PDF readers in browsers, it would often either trigger a download or launch an external program, which are kind of rude behaviors to spring on someone without notice. I still have this habit (though I'll just mention "(PDF)" in a parenthetical), and I'll certainly warn about autoplaying audio or an excessive amount of ads even if I expect a good fraction of readers to have browser configs/extensions to deal with those.
    - pronoiac 8y ago
      The mobile experience for PDFs is awful.
      - anoncake 8y ago
        The mobile experience for HTML/JS/CSS is awful too.
  - evanb 8y ago
    You can de-PDF anything on the arXiv by chopping off the .pdf suffix and changing the /pdf/ to /abs/. For example, https://arxiv.org/abs/1104.2804 https://arxiv.org/abs/1104.2804
    - Intermernet 8y ago
      Thanks! I love learning little tips like that.
jeromebaek 8y ago
This was my first introduction to formal language theory. Beautiful intro.
lixtra 8y ago
When I read about it in Gödel Escher Bach I wasn’t aware yet that unsolvable is a valid answer to a problem. I felt cheated(1) and the whole book lost a lot of its appeal. In retrospect it may have actually undone some damage done by the school system where the solution space is usually very restricted. Edit: (1) From what I remember it’s stated as find the sequence and not does such a sequence exist.
- chongli 8y ago
  I would continue arguing that "unsolvable" is not a valid solution to this puzzle. If the description asks you to "find the solution" and the solution does not exist, then it is a riddle, not a puzzle.
  - ineedasername 8y ago
    You're simply playing semantics and defining "puzzle" as "something that has a solution". But if you're at work and your boss says "I have a puzzle I need you to solve: Given these constraints, find an answer" You need to be able to say "Here is my solution" or "No solution is possible, and here is why." Or take something simpler: a 500 piece "Puzzle" only there's a manufacturing defect in all copies: one piece is miss shaped. The puzzle can't be completed; there is no "solution". It's still a puzzle. So no, you don't get to "unfair!" your way out of the MU Puzzle through narrow semantic definitions, especially given the, well, grammatical nature of language, because then you have gone and missed the entire point.
    - paradoxparalax 8y ago
      I think his point: "If it asks you for a solution that doesn't exist, It's a Riddle" is a perfectly valid point and your comment was a bit "overreactive", in my opinion.
      - ineedasername 8y ago
        What makes it a valid point? I see nothing in the definition of either word that would definitively preclude "puzzle" as an appropriate label. Riddle is fine too, but no mutually exclusive. You and the parent comment claim it's not a puzzle, it's a riddle, with the implication that's somehow unfair or deceptive in how the problem was framed. That is a semantic hair splitting that dodges the problem & its answer. In real life problems you don't get to define away responsibility for problems put in front of you. And if thoroughly stating my case is "overractive", then I'm guilty, but I find it's generally better to over-support my argument than state claims without justification.
amatic 8y ago
Is the Gödel Escher Bach worth the reading? I started, but I feel it's fluff. People say he is good, though. Are there some practical insights?
- haskellandchill 8y ago
  No it’s fluff, good for curious people with no background.
  - muthdra 8y ago
    C'mon, man. It's an analysis.
- edflsafoiewq 8y ago
  I think most of us who really like it read it as kids which colors it too much. I distinctly remember this proof that you can't solve the MU-puzzle as the first piece of mathematics I ever saw. In one swoop I discovered impossibility proofs, invariants, and the use of divisibility which suffused the whole book with an aura of initiation into great mysteries that it will never attain for the already-initiated.
  - justinator 8y ago
    I read it in art school (swiped from my then-girlfriend's bookshelf), and it was nice to have a connection between my school of art weirdos and putting myself through the same school by teaching myself software engineering. I distinctly remembering writing a Perl script to highlight that the Mu puzzle is unsolvable. #!/usr/bin/perl -w use strict; my %tried = (); main(); sub main { my @rules = ( \&rule_one, \&rule_two, \&rule_three, \&rule_four, ); my $axiom = 'MI'; my @path; my @tries; solve($axiom, \@rules); } sub solve { my @app; my ($axiom, $rules) = @_; my $i = 0; foreach(@$rules){ my $tmp = $_->($axiom); push(@app, $tmp) if $tmp; } foreach(@app){ next if $tried{$_}; next unless (length($_) < 1000); print $_ . "\n"; $tried{$_} = 1; if($_ eq 'MU'){ print "YES!\n\n\n"; exit; } solve($_, $rules); } } sub rule_one { # If any string ends in I, you can append U my $str = shift; if ($str =~ m/I$/){ return $str . 'U'; }else{ return undef; } } sub rule_two { # If any string begins with M, # you can duplicate the string after M, my $str = shift; if($str =~ /^M/){ return 'M' . substr($str, 1) . substr($str, 1); }else{ return undef; } } sub rule_three { # If any string contains III, # you can replace the III with U my $str = shift; if($str =~ /III/){ $str =~ s/III/U/g; return $str; }else{ return undef; } } sub rule_four { #If any string contains UU, # you can delete the UU my $str = shift; if($str =~ /UU/){ $str =~ s/UU//g; return $str; }else{ return undef; } }
paradoxparalax 8y ago
I have learn more geometry from trying to solve the unsolvable "squaring the circle" problem than all the Geom. classes I had in my life. For example: No one ever has told me in school that for all squares, the length of the diagonal equals The Square Root Of Two times the side of the square's, so for a square where the side is 1 meter, the diagonal will be Sq.Rt.o'2 meters (around 1,4 m), And I came to find that by myself doing the exercise of the unsolvable. Also, more recently early this year, I found that the diagonal/diameter of a Pentagon was the Cubic Root of 3, or this was the hexagon, and the heptagon was the S.q.rt.o'2 multiplied by C.rt.o'3 or something like this, the thing is that they follow a sequence, Its always something with the square and cubic roots of 2 and 3 and I guess 5 or 7 will appear later in the sequence for polygons with more sides, noting that for a "infinite sides 'polygon' " , which would be a circle, the number that relates the diagonal with the "'sides'", or in this analogy, the Perimeter , is Pi...Anyway, good exercises. p.s: I have remembered that back then I thought maybe Pi was Square Root of Infinity, and now just came to my mind that maybe would be the Infinite Root of something...But off course just joking thinking, but nice exercise.
- mrleiter 8y ago
  > For example: No one ever has told me in school that for all squares, the length of the diagonal equals The Square Root Of Two times the side of the square's, so for a square where the side is 1 meter, the diagonal will be Sq.Rt.o'2 meters (around 1,4 m), And I came to find that by myself doing the exercise of the unsolvable. That's actually the Pythagorean theorem. How did you arrive at that by doing the "unsolvable"?
  - avian 8y ago
    The “unsolvable problem” the parent refers to is the problem of geometrically constructing a square with the same area as a circle. It has been proven to be impossible. https://en.m.wikipedia.org/wiki/Squaring_the_circle https://en.m.wikipedia.org/wiki/Squaring_the_circle
- raverbashing 8y ago
  > No one ever has told me in school that for all squares, the length of the diagonal equals The Square Root Of Two times the side of the square's This is basic knowledge (and as someone said, comes from the Pythagorean theorem) and taught on school in a lot of places.

83 points by bladecatcher 8y ago

People who like this might also enjoy the similarly simple (yet unsolved) Collatz Conjecture: https://en.wikipedia.org/wiki/Collatz_conjecture https://en.wikipedia.org/wiki/Collatz_conjecture

Intermernet 8y ago
On a slight tangent, I recently read a paper on an interesting relationship between Collatz path length and Mersenne primes. "Our main finding to report is the fact that a path length of a Mersenne prime is approximately proportional to its index for large n, namely, D(Mn) ≈ 13.45n." Paper is at https://arxiv.org/pdf/1104.2804.pdf https://arxiv.org/pdf/1104.2804.pdf . WARNING: PDF.
- jamescostian 8y ago
  I'm curious, why do people on HN warn about PDFs? The worst things I can imagine happening with PDFs are (1) you don't have any software that can read it (probably like .2% of HNers?) and (2) it could potentially have some malware (but the same could be said of a website)
  - hermitdev 8y ago
    Adobe is not known for their security. PDF is also known to allow remote execution via PDF. Default reader on most systems being Adobe's reader, yeah, I'd avoid it. I know this is shifting as browsers incorporate readers, but the format is tarnished.
  - geofft 8y ago
    Before the advent of built-in PDF readers in browsers, it would often either trigger a download or launch an external program, which are kind of rude behaviors to spring on someone without notice. I still have this habit (though I'll just mention "(PDF)" in a parenthetical), and I'll certainly warn about autoplaying audio or an excessive amount of ads even if I expect a good fraction of readers to have browser configs/extensions to deal with those.
  - pronoiac 8y ago
    The mobile experience for PDFs is awful.
    - anoncake 8y ago
      The mobile experience for HTML/JS/CSS is awful too.
- evanb 8y ago
  You can de-PDF anything on the arXiv by chopping off the .pdf suffix and changing the /pdf/ to /abs/. For example, https://arxiv.org/abs/1104.2804 https://arxiv.org/abs/1104.2804
  - Intermernet 8y ago
    Thanks! I love learning little tips like that.

jeromebaek 8y ago

This was my first introduction to formal language theory. Beautiful intro.

lixtra 8y ago

When I read about it in Gödel Escher Bach I wasn’t aware yet that unsolvable is a valid answer to a problem. I felt cheated(1) and the whole book lost a lot of its appeal. In retrospect it may have actually undone some damage done by the school system where the solution space is usually very restricted. Edit: (1) From what I remember it’s stated as find the sequence and not does such a sequence exist.

chongli 8y ago
I would continue arguing that "unsolvable" is not a valid solution to this puzzle. If the description asks you to "find the solution" and the solution does not exist, then it is a riddle, not a puzzle.
- ineedasername 8y ago
  You're simply playing semantics and defining "puzzle" as "something that has a solution". But if you're at work and your boss says "I have a puzzle I need you to solve: Given these constraints, find an answer" You need to be able to say "Here is my solution" or "No solution is possible, and here is why." Or take something simpler: a 500 piece "Puzzle" only there's a manufacturing defect in all copies: one piece is miss shaped. The puzzle can't be completed; there is no "solution". It's still a puzzle. So no, you don't get to "unfair!" your way out of the MU Puzzle through narrow semantic definitions, especially given the, well, grammatical nature of language, because then you have gone and missed the entire point.
  - paradoxparalax 8y ago
    I think his point: "If it asks you for a solution that doesn't exist, It's a Riddle" is a perfectly valid point and your comment was a bit "overreactive", in my opinion.
    - ineedasername 8y ago
      What makes it a valid point? I see nothing in the definition of either word that would definitively preclude "puzzle" as an appropriate label. Riddle is fine too, but no mutually exclusive. You and the parent comment claim it's not a puzzle, it's a riddle, with the implication that's somehow unfair or deceptive in how the problem was framed. That is a semantic hair splitting that dodges the problem & its answer. In real life problems you don't get to define away responsibility for problems put in front of you. And if thoroughly stating my case is "overractive", then I'm guilty, but I find it's generally better to over-support my argument than state claims without justification.

amatic 8y ago

Is the Gödel Escher Bach worth the reading? I started, but I feel it's fluff. People say he is good, though. Are there some practical insights?

haskellandchill 8y ago
No it’s fluff, good for curious people with no background.
- muthdra 8y ago
  C'mon, man. It's an analysis.
edflsafoiewq 8y ago
I think most of us who really like it read it as kids which colors it too much. I distinctly remember this proof that you can't solve the MU-puzzle as the first piece of mathematics I ever saw. In one swoop I discovered impossibility proofs, invariants, and the use of divisibility which suffused the whole book with an aura of initiation into great mysteries that it will never attain for the already-initiated.
- justinator 8y ago
  I read it in art school (swiped from my then-girlfriend's bookshelf), and it was nice to have a connection between my school of art weirdos and putting myself through the same school by teaching myself software engineering. I distinctly remembering writing a Perl script to highlight that the Mu puzzle is unsolvable. #!/usr/bin/perl -w use strict; my %tried = (); main(); sub main { my @rules = ( \&rule_one, \&rule_two, \&rule_three, \&rule_four, ); my $axiom = 'MI'; my @path; my @tries; solve($axiom, \@rules); } sub solve { my @app; my ($axiom, $rules) = @_; my $i = 0; foreach(@$rules){ my $tmp = $_->($axiom); push(@app, $tmp) if $tmp; } foreach(@app){ next if $tried{$_}; next unless (length($_) < 1000); print $_ . "\n"; $tried{$_} = 1; if($_ eq 'MU'){ print "YES!\n\n\n"; exit; } solve($_, $rules); } } sub rule_one { # If any string ends in I, you can append U my $str = shift; if ($str =~ m/I$/){ return $str . 'U'; }else{ return undef; } } sub rule_two { # If any string begins with M, # you can duplicate the string after M, my $str = shift; if($str =~ /^M/){ return 'M' . substr($str, 1) . substr($str, 1); }else{ return undef; } } sub rule_three { # If any string contains III, # you can replace the III with U my $str = shift; if($str =~ /III/){ $str =~ s/III/U/g; return $str; }else{ return undef; } } sub rule_four { #If any string contains UU, # you can delete the UU my $str = shift; if($str =~ /UU/){ $str =~ s/UU//g; return $str; }else{ return undef; } }

paradoxparalax 8y ago

I have learn more geometry from trying to solve the unsolvable "squaring the circle" problem than all the Geom. classes I had in my life. For example: No one ever has told me in school that for all squares, the length of the diagonal equals The Square Root Of Two times the side of the square's, so for a square where the side is 1 meter, the diagonal will be Sq.Rt.o'2 meters (around 1,4 m), And I came to find that by myself doing the exercise of the unsolvable. Also, more recently early this year, I found that the diagonal/diameter of a Pentagon was the Cubic Root of 3, or this was the hexagon, and the heptagon was the S.q.rt.o'2 multiplied by C.rt.o'3 or something like this, the thing is that they follow a sequence, Its always something with the square and cubic roots of 2 and 3 and I guess 5 or 7 will appear later in the sequence for polygons with more sides, noting that for a "infinite sides 'polygon' " , which would be a circle, the number that relates the diagonal with the "'sides'", or in this analogy, the Perimeter , is Pi...Anyway, good exercises. p.s: I have remembered that back then I thought maybe Pi was Square Root of Infinity, and now just came to my mind that maybe would be the Infinite Root of something...But off course just joking thinking, but nice exercise.

mrleiter 8y ago
> For example: No one ever has told me in school that for all squares, the length of the diagonal equals The Square Root Of Two times the side of the square's, so for a square where the side is 1 meter, the diagonal will be Sq.Rt.o'2 meters (around 1,4 m), And I came to find that by myself doing the exercise of the unsolvable. That's actually the Pythagorean theorem. How did you arrive at that by doing the "unsolvable"?
- avian 8y ago
  The “unsolvable problem” the parent refers to is the problem of geometrically constructing a square with the same area as a circle. It has been proven to be impossible. https://en.m.wikipedia.org/wiki/Squaring_the_circle https://en.m.wikipedia.org/wiki/Squaring_the_circle
raverbashing 8y ago
> No one ever has told me in school that for all squares, the length of the diagonal equals The Square Root Of Two times the side of the square's This is basic knowledge (and as someone said, comes from the Pythagorean theorem) and taught on school in a lot of places.