this post was submitted on
25 points (90% like it)
28 up votes 3 down votes
shortlink:
to anything interesting: news article, blog entry, video, picture...

24
25

[Discussion] Chapter 1: The MU-puzzle (self.GEB)

submitted ago by rspeer5[M]

This is a short chapter, but that's fine because it gives you something to do. Seriously, try the puzzle! It doesn't matter whether it's on paper, in your favorite programming language, or just juggling symbols in your head.

If you've read the book already, don't spoil anything. If you think you have an answer (that is, a derivation of MU or an explanation of why it can't be derived), use spoiler tags. The right sidebar shows you how.

Spoilers need a statute of limitations, of course. (Snape kills Rosebud!) Hofstadter waits several chapters, but I'm going to say that you can spoil the MU-puzzle starting next Friday, when discussion of Chapter 2 begins.

all 48 comments
sorted by:
best
hot
new
controversial
top
old

[–]Routerbox 24 points25 points ago*

Here, I made this for you.

MIU-System

Flex 3 Code:

[–]unnamed_player 3 points4 points ago

This is wonderful!

[–]Routerbox 0 points1 point ago

:-)

[–]rspeer5[S] 9 points10 points ago

A few things to try in this system:

  1. There are MIU-theorems that are not just derivable from MI but equivalent -- that is, you can derive them from MI and you can also derive MI from them. If you started with such a theorem instead of MI, you would have exactly the same system.
    • You should be able to find some equivalent theorems with a bit of experimentation -- what are they?
    • You can also find theorems that are definitely not equivalent. How can you tell?
  2. When you explore the system on paper or on a computer, you will probably end up coming up with ways to avoid getting "stuck". Can you write these down as rules?
  3. Make a computer program that lists all the unique theorems you can get to in up to n steps. Then sort them (perhaps by length and then by alphabetical order).
    • Can you recognize patterns in the theorems you derive this way and the theorems you don't derive?
    • If you hypothesize such a pattern and it holds up as you increase n, you may have found a decision procedure, which would tell you a lot about the system! A decision procedure means you can look at a string and decide whether it is or is not a theorem, without trying to derive it.
    • For example, one very simple, incomplete decision procedure is that any string that doesn't start with M is not a theorem.

[–]elexhobbyV 2 points3 points ago

Inside the system stuff (after generating 1e7 theorems)

Theorems: ['MI', 'MII', 'MIU', 'MUI', 'MIIU', 'MIUI', 'MIUU', 'MUII', 'MUIU', 'MIIII', 'MIIUU', 'MIUIU', 'MIUUI', 'MIUUU', 'MUIIU', 'MUIUI', 'MUIUU', 'MUUII', 'MUUIU', 'MUUUI']

Non-theorems (claim): ['M', 'MU', 'MUU', 'MIII', 'MUUI', 'MUUU', 'MIIIU', 'MIIUI', 'MIUII', 'MUIII', 'MUUUU']

[–]Routerbox 0 points1 point ago

Theorems : Non-theorems :: Figure : Ground

?

[–]Kogos 0 points1 point ago

For your second question, I can think of a rule right off the bat: You must always start with the second rule (Double everything after 'M'). If you start with the first rule (add a 'U'), your only next move is rule 2, which you soon learn leads to a dead end.

[–]jfpowell2 5 points6 points ago

I really like this puzzle. It's a nice introduction to the power of proof and meta-reasoning, especially for those who have no formal training in mathematics.

The first time I read the book I skipped the puzzle, but the second time (many years later) I got a pen and paper out and gave it a go. Really quite satisfying to get an aha! moment.

If you can't solve it, don't worry, it's not as important as actually getting a feel for what it means to derive theorems and apply axioms.

[–]aflampV 0 points1 point ago

I don't know, I think that if you haven't solved it you really won't understand the rest of the book. Keep trying.

[–]NoodlesLongacre1 2 points3 points ago

I guess nobody got the joke.

[–]aflampV 2 points3 points ago

I guess not. Oh well. I spent quite a bit of time trying to figure that puzzle out. I guess I am more of a computer than a human.

[–]frezik1 1 point2 points ago

You can definitively understand the rest of the book without solving it. The important part is to Jump Out of the System and start seeing patterns that a brute force algorithm can't.

[–]rspeer5[S,M] 5 points6 points ago

Quick question about pacing. I feel like there isn't enough to talk about at this point. Does anyone else think we should open the second Dialogue for discussion on Monday instead of Wednesday?

[–]jzapate1 3 points4 points ago

That sounds pretty good to me.

[–]skullgridV 4 points5 points ago

Honestly, I'd prefer to be doing 1.5-2 chapters a week, rather than the 1 chapter a week we're doing now. I know people are busy, I'm busy too, but ~30 pages a week translates to ~1 hour of reading, 2 hours tops, and I have a hard time believing that people dont have 15 minutes a day to read. On top of that, when you're reading something so slowly, it's hard to keep it all fresh in your mind (at least for me).

[–]georgelulu 1 point2 points ago

I wonder how many people who are already reading the second Dialogue or are even further along yet are still looking at the discussion for the first chapter to answer your question about pacing. Perhaps setting up the next topic and asking if your going too fast would assist in gauging the pace?

[–]mathmatt1 1 point2 points ago

Yes, I think since the discussion threads become permanent fixtures of the subreddit, it shouldn't be a big deal if you go a little too fast at times.

[–]ilovecomputersV 5 points6 points ago

Can someone elaborate by what Hofstadter means by decision procedure?

[–]MaximKat 5 points6 points ago

It's an algorithm that can tell whether a certain statement is a theorem or not.

[–]waingroSS0 2 points3 points ago

So it wouldn't be possible to create a decision procedure without knowing all the rules of inference for a given formal system?

[–]MaximKat 4 points5 points ago

This depends on what exactly you mean by "without knowing".

You don't have to encode the inference rules explicitly in the decision procedure. For example, if you have a system with an axiom "0" and an inference rule "n |- n+1", then its theorems are natural numbers. You don't need to know these actual rules in order to write a program that would return "yes" if its input is a natural number and "no" otherwise.

On the other hand, you obviously need to have some knowledge of the rules to come up with a decision procedure.

[–]jzapate1 1 point2 points ago

I think that you could. I don't have my book in front of me but I remember Hofstadter covering this in the latter half of Ch. 1.

I don't think decision procedures are all encompassing, they just have to be definite. Like if you have any given string, you could decide if it is a theorem of the MIU system by looking at the first letter of the string. This decision procedure wouldn't tell you whether something is definitely a theorem of MIU, but it would tell you that a given string like 'XIU' is definitely not a theorem.

This makes me wonder though, is there a difference between an algorithm that will tell you that something is not a theorem and an algorithm that will tell you yes or no. The first algorithm could only tell you no or maybe whereas the second could tell you yes or no. Are these all decision procedures or fundamentally different procedures?

[–]waingroSS0 0 points1 point ago

This makes me wonder though, is there a difference between an algorithm that will tell you that something is not a theorem and an algorithm that will tell you yes or no. The first algorithm could only tell you no or maybe whereas the second could tell you yes or no. Are these all decision procedures or fundamentally different procedures?

I think that all hinges around one of the big themes in the book, the difference between something that is predictably terminating, and something that isn't.

[–]MaximKat 0 points1 point ago

Nope, that's not what a DP is. It has to tell you yes/no every time.

[–]rspeer5[S] 1 point2 points ago

Something that can decide in certain circumstances is still useful. I called it an "incomplete decision procedure" in my post, but maybe there's another term for it.

[–]MaximKat 2 points3 points ago

Sure. I'm just saying that a DP is a well-defined term with a specific meaning. Definitions are important when talking about formal logic.

[–]jzapate1 1 point2 points ago

Sorry for not having my book with me, maybe someone with it could jump in. What was Hofstadter describing when he was talking about how you could say if something was a theorem of the MIU system by checking for the presence of the letter M, if not a decision procedure?

Simply an intuitive way for humans to make generalizations which a machine could not make? Which would mean Hofstadter was maybe implying that these procedures that people come up with, which are quite effective though not strict decision procedures, are one aspect as to what makes us conscious or helps us think quickly.

[–]MaximKat 0 points1 point ago

He called it a "test". Informally, a decision procedure is a test that always works perfectly.

[–]dopplerdog5 1 point2 points ago

This makes me wonder though, is there a difference between an algorithm that will tell you that something is not a theorem and an algorithm that will tell you yes or no.

Yes. The difference is this: the first algorithm will tell you something is not a theorem, but it need not tell you something is a theorem, i.e. if you feed it a theorem it need never terminate. "Waiting forever" to see if it's a theorem is obviously not an option.

This is in stark contrast to the second algorithm, which is guaranteed to terminate and tell you something is a theorem or is not a theorem.

The first algorithm could only tell you no or maybe whereas the second could tell you yes or no. Are these all decision procedures or fundamentally different procedures?

The first algo is not a decision procedure as it can't always tell you something is a theorem. The second one is a decision procedure.

IMO, this distinction is important to understand now, as later chapters on recursive sets and recursive enumerable sets relies on it.

[–]MaximKat 0 points1 point ago

To be fair, I'm not sure how useful an algorithm that tells you "not a theorem" or runs forever would be (as opposed to "yes"/runs forever). You certainly can't enumerate theorems with it.

[–]dopplerdog5 0 points1 point ago

No, but you can enumerate non-theorems with it, which you wouldn't be able to do with a "yes"/runs forever algorithm.

Of course, if you had both algorithms available, then it's trivial to construct a decision procedure from them.

[–]Quantum_Rage 0 points1 point ago

In a finite time.

[–]Deltaway 2 points3 points ago*

Hint: Consider prime factors

[–]ja524309 -1 points0 points ago

Yeah this doesn't have anything to do with the puzzle.

[–]Deltaway 8 points9 points ago*

Solution using prime factors:

Call the number of I's i.

* Rule 1 is i invariant.

* Rule 2 doubles i, adding a prime factor of 2.

* Rule 3 removes 3 from i.

* Rule 4 is i invariant.

The start string MI has i = 1. Rule 1 and 4 cannot change i, and Rule 2 can only multiply i by a prime factor of 2. Rule 3 can only reduce i to 0 if a prime factor of 3 can be produced, and no combination of Rules 2 and 3 can do this. Therefore MU can never be produced.

[–]bjnord 1 point2 points ago

Elegant, Deltaway. Thanks for sharing.

[–]ja524309 1 point2 points ago

You still don't really need the concept of a prime factor to solve this. The same rationale would work with two rules using just relatively prime amounts. You're not employing anything important about prime numbers (their unique factorization).

[–]Deltaway 1 point2 points ago

Granted. I don't know what the book's solution is yet. This was one I found myself when I thought about factorizing the number of I's.. I'm sure prime factors aren't necessary to solve the problem, I just thought mentioning them might be an interesting mental prod for someone who hasn't solved the problem yet.

[–][deleted] 0 points1 point ago

I couldn't help but almost automatically jump right to going out of the system (I may have read a bit further) and try to reason about the system itself. I did probably 13 lines on paper and a fair bit more in my head. Also, using the Wolfram applet that was linked to earlier, it is easy to see how many paths lead to impossible situations.

[–]gbsalleryonce 0 points1 point ago

I'd just like to agree with the sentiment of "try the puzzle". I didn't bother getting out pencil and paper the first time I read this chapter (I was on holiday, by a swimming pool in the south of France - that increases inertia dramatically!), but I've just had a play around with it and it is indeed great fun.

It turns out that length matters, after all

[–]waingroSS0 1 point2 points ago

p.41 "one requirement on formal systems is that the set of axioms must be characterized by a decision procedure.."

How is MI characterized by a decision procedure?

[–]MaximKat 5 points6 points ago

It's a very simple decision procedure that returns True for MI and False for everything else.

[–]monxcracy~V~ 0 points1 point ago

It is possible for a machine to act unobservant; it is impossible for a human to act unobservant.

I think we should keep in mind some possible definitions of Action, in order to observe whether Hofstadter falls into anthropomorphism here and later.

http://mises.org/Books/humanaction.pdf

I. Acting Man 1. Purposeful Action and Animal Reaction

"HUMAN action is purposeful behavior. Or we may say: Action is will put into operation and transformed into an agency, is aiming at ends and goals, is the ego’s meaningful response to stimuli and to the conditions of its environment, is a person’s conscious adjustment to the state of the universe that determines his life."

[–]ja524309 0 points1 point ago

That definition didn't clear anything up. Also, Mises, ew.

[–]rkaufman3ish -2 points-1 points ago

In Chapter 1, non MU-puzzle related discussion, I found the "inside and outside the system" section to be an example of Hofstadter's rare lack of prescience.

This book has always impressed me by how it manages to present issues that are still relevant in AI research today, despite having been first published in 1979.

But come on. A car will "never" learn to avoid obstacles or stay on the road? Never, DH? I was surprised to see that pronouncement, even if it was "only" an illustrative example of the differences between humans and computers.

[–]MaximKat 15 points16 points ago

It's pretty obvious that he means regular cars here, not "smart car of the future" ones.

[–]4x4lo8ov 7 points8 points ago

I thought it was pretty clear he wasn't talking about the future or technological progression. He's talking about the car in your driveway right now

[–]rocketvat -1 points0 points ago

For certain instances of "car in your driveway right now", that is false.

Use of this site constitutes acceptance of our User Agreement and Privacy Policy. © 2012 reddit inc. All rights reserved.

REDDIT and the ALIEN Logo are registered trademarks of reddit inc.

π Rendered by PID 20044 on app-10 running 34b59fd.