MU puzzle(en.wikipedia.org)
en.wikipedia.org
MU puzzle
https://en.wikipedia.org/wiki/MU_puzzle
45 comments
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 . WARNING: PDF.
"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 . WARNING: PDF.
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)
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.
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.
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
For example, https://arxiv.org/abs/1104.2804
Thanks! I love learning little tips like that.
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.
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.
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.
The puzzle is called MU for a reason. 'Mu' is the valid solution. https://en.wikipedia.org/wiki/Mu_(negative)#The_Mu-koan
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.
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.
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.
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.
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.
Different contexts. In the real world it's understood that anything is possible (you can also clarify if unclear). But in a book like this, you put trust in the author to use precise language, and especially given the nature of this particular book. Maybe it was done purposefully for effect, but that's still jarring.
No. In the real would "anything" is not possible, and that it is an odd statement to make. It's not at all uncommon for me to see or be a part of a problem solving process that at some point includes a statement like "given the constraints we're under, there is no current solution." Now the next stage might be something like "We can eliminate one constraint by doing X, which will cost Y dollars" etc. So in the MU problem one might say "Given the string transformation rules, MI cannot become MU. However, if we added rule X, then such a transformation would become possible."
All of which is besides the point: "Puzzle" and "Riddle" are pretty much interchangeable. They appear as synonyms for each other in thesauri; "riddle" is given as one of multiple definitions for "puzzle" in wiktionary. Many sources treat "riddle" as a kind of "puzzle". The degree to which riddle might be more appropriate in a given context relies on a few factors, for example riddles often tend towards more verbal basis, spoken or written. A puzzle is the broader category and can include things like physical object such as a 500-piece jigsaw puzzle. But any difference is still only that of broader category and specific type. Either term is valid here.
So stating "It's not a puzzle, it's a riddle" is indeed splitting hairs, or simply not knowing the nuances of the actual definitions of those words. The OP of that comment appeared to be doing so with the implication that the whole problem was somehow unfair as a result. I cry foul on that assertion for the reasons stated.
All of which is besides the point: "Puzzle" and "Riddle" are pretty much interchangeable. They appear as synonyms for each other in thesauri; "riddle" is given as one of multiple definitions for "puzzle" in wiktionary. Many sources treat "riddle" as a kind of "puzzle". The degree to which riddle might be more appropriate in a given context relies on a few factors, for example riddles often tend towards more verbal basis, spoken or written. A puzzle is the broader category and can include things like physical object such as a 500-piece jigsaw puzzle. But any difference is still only that of broader category and specific type. Either term is valid here.
So stating "It's not a puzzle, it's a riddle" is indeed splitting hairs, or simply not knowing the nuances of the actual definitions of those words. The OP of that comment appeared to be doing so with the implication that the whole problem was somehow unfair as a result. I cry foul on that assertion for the reasons stated.
I have a similar memory! I read about the problem in the book and worked on it for days, trying to solve it. I was in junior high at the time, and my math teacher spotted what I was doing. The teacher figured out quite quickly that it was impossible to solve. And I felt sort of dumb for not figuring out it was impossible and having a teacher prooving it :)
There are a whole class of problems that revolve around the incompatibility of operations based on the primes (in this case 2 and 3). When you attempt to solve, and fail to solve, any of them you are likely to gain an instinctive appreciation for all of them - the kind of appreciation that would lead a maths teacher to a proof to the contrary very fast.
It should be noted that if the teacher had had the foresight (often a big ask) to simply tell you they suspected there was no solution, which is often the case with such problems presented as they are, and that you should attempt a proof alone, you would likely not feel so bad about not spotting it immediately.
It should be noted that if the teacher had had the foresight (often a big ask) to simply tell you they suspected there was no solution, which is often the case with such problems presented as they are, and that you should attempt a proof alone, you would likely not feel so bad about not spotting it immediately.
I wouldn't feel dumb about it. People often look at very difficult problems for a very long time before they conclude a solution is impossible and later to be disproven. I would expect this one to be any different. Yes, there are currently no known solutions, but that doesn't preclude a brilliant mind coming in down the road with a solution.
In this case, there is provably no solution. A brilliant mind can’t fight that, any more than it can prove that 2+2=5. :-)
(Yes, using the traditional definitions of all those symbols.)
(Yes, using the traditional definitions of all those symbols.)
I always saw it as his way of teaching of grammars. But I think it is kind of bad that the grammar isn't actually creating a solvable system.
it is kind of bad that the grammar isn't actually creating a solvable system
But that was precisely the point. That given a system with a set of rules, the space of all possible problems may be larger than the space of all solutions, i.e., not all problems have a solution.
To say it's useful to be able to determine if a problem is solvable is a vast understatement.
But that was precisely the point. That given a system with a set of rules, the space of all possible problems may be larger than the space of all solutions, i.e., not all problems have a solution.
To say it's useful to be able to determine if a problem is solvable is a vast understatement.
It's a book about incompleteness, undecidability and other nasty surprises in math. Nobody expected them. So an unexpected nasty surprise of an unsolvable problem is somehow relevant to the book.
See, that's on my reading list. (3rd or 4th I think, so coming up soon)
Now I've had some of the surprise ruined just by reading a HN thread that didn't even appear to be related to the book in the first place. If I had just clicked the Wikipedia link and read the first puzzle, I'd have clipped it to my notes and marked it as something to read afterward. But because this was pushed up to top comment, it caught my eye first.
Now I've had some of the surprise ruined just by reading a HN thread that didn't even appear to be related to the book in the first place. If I had just clicked the Wikipedia link and read the first puzzle, I'd have clipped it to my notes and marked it as something to read afterward. But because this was pushed up to top comment, it caught my eye first.
I think this points to the central idea Hofstadter was trying to communicate. In order to "solve" the puzzle, you have to exit what he calls the "mechanical (m) mode" and think about the puzzle on a different level, the "intelligent (i) mode." The goal was for the reader to try and solve it by realizing blindly applying axioms of the system got nowhere. Proving the puzzle is impossible requires a mode of thinking analogous to Gödel's incompleteness theorem.
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?
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.
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;
}
}One person's fluff may be another person's concrete. Only way to know is to try a bit.
I thoroughly enjoyed it, but I've always had diverse interests and the book sort of caters to that.
I thoroughly enjoyed it, but I've always had diverse interests and the book sort of caters to that.
It was published almost 40 years ago. I think to get the best experience of it, you have to have read it back then, or read it as a precocious 14 year old. If you read it with a graduate or even undergraduate understanding of computer science, you're probably not going to get much out of it on the technical side; and I think a lot of his conjectures about how the mind works didn't really pan out.
If you approach it as an object of art, the book is fun because it embeds into itself many of the techniques and principles it describes (but you'll only notice this if you're paying attention). This is kinda cool on a meta-meta level because the central concept of the book is self-referentiality.
If you approach it as an object of art, the book is fun because it embeds into itself many of the techniques and principles it describes (but you'll only notice this if you're paying attention). This is kinda cool on a meta-meta level because the central concept of the book is self-referentiality.
The explanation of how Godel's Theorem works that I got from reading GEB is still the best one I have encountered.
I always find the Gödel representations using powers of primes too strange. It's technically correct, I can follow the proof, but there is a small corner of my mind that can't believe it.
The GEB book doesn't have all the details, but it uses the ASCII representations (actually base 20 but whatever). With the ASCII representation the theorem feels obvious.
The GEB book doesn't have all the details, but it uses the ASCII representations (actually base 20 but whatever). With the ASCII representation the theorem feels obvious.
I would say the first half is great, second half is terrible.
It is a lot of fluff and meandering, but the dialogue are just too good, and I still enjoy them.
Some people have recommended reading "I am a strange loop" as a basically more mature and better written version of GEB.
It is a lot of fluff and meandering, but the dialogue are just too good, and I still enjoy them.
Some people have recommended reading "I am a strange loop" as a basically more mature and better written version of GEB.
There is a section in the book where he laments that certain mediums (like books, and movies) leak information about where the story ends (because in a book as you are reading it you will know you are coming towards the end). He explained one way to avoid this and retain some mystery in story-telling would be to finish the story some distance before the end and pad the remainder of the book with blank pages. However blank pages are too easy to spot if someone happens to flick through the book before hand, so instead it would be better to pad the book with text which appears to be related to the primary story and therefore is undetectable unless someone reads through the whole book in order.
And of course, this is explained in one of the dialogues, which is structured exactly like this - after it ends, there is some fake padding dialogue afterwards to hide where the actual ending is...
Opinions differ: https://blog.infinitenegativeutility.com/2018/7/why-i-dont-l... Fwiw, I liked it but some parts of the book which is from 1979 hasn't aged too well. For example, Hofstadter didn't realize how well computer programs could simulate what he thought was intelligent behavior such as chess playing.
No it’s fluff, good for curious people with no background.
C'mon, man. It's an analysis.
This was my first introduction to formal language theory. Beautiful intro.
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.
> 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"?
That's actually the Pythagorean theorem. How did you arrive at that by doing the "unsolvable"?
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
> 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.
This is basic knowledge (and as someone said, comes from the Pythagorean theorem) and taught on school in a lot of places.
Yes, thats exactly what im saying, everyone knows the pythagorean theorem by memory, but something even more basic, a simple constant, not a formula, in a simple square, if you ask around, at least in my experience, no one knows.
https://en.wikipedia.org/wiki/Collatz_conjecture