-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
74 lines (66 loc) · 3.57 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
<!doctype html>
<html>
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Gödel Escher Back - MUI</title>
<link rel="stylesheet" href="style.css">
</head>
<body>
<div id="app">
<div class="container">
<h1>Gödel Escher Bach - MIU System</h1>
<p>
I'm currently reading Gödel Escher Bach. His first formal system he introduces is the MIU system.
It follows four rules.
<ol>
<li>If you posses a string whose last letter is I, you can add on a U at the end.</li>
<li>Suppose you have Mx. Then you may add Mxx to your collection.
<li>If III occurs in one of the string in your collection, you may make a new string with U in place of III</li>
<li>If UU occurs inside one of your strings, you can drop it.</li>
</ol>
<strong>The Goal of the Book is to get from MI to MU.</strong>
You can use the applet below to apply the rules, for feedback, check the console.
</p>
<hr />
<h2>MIU System Applet</h2>
<div id="result" class="result">
</div>
<button id="ruleOne">
Rule One
</button>
<button id="ruleTwo">
Rule Two
</button>
<button id="ruleThree">
Rule Three
</button>
<button id="ruleFour">
Rule Four
</button>
<button id="reset">
RESET
</button>
<hr />
<h2>So how to get from the <code>I</code> to the <code>U</code>?</h2>
<p>The only rule that can reduce the number of <code>I</code> the the 3rd rule, so we should focus on that.
To remove all <code>I</code>, we need to fullfill <code>count(I) mod 3 = 0</code>, which means that the number of <code>I</code> must be divisible by 3.
<code>count</code> represents the number of <code>I</code>, <code>mod</code> is the mathematical operation modulo.</p>
<p>With the second rule, we can duplicate the starting <code>I</code>.
But doubling a number that is not divisible by 3 will never make it divisible by 3.</p>
<blockquote>
<strong>Proof sketch:</strong>
<p>Suppose you have a number <code>n</code> that is not divisible by 3, so <code>n mod 3 != 0</code>, which means that <code>n = x * 3 + y</code>, where <code>x</code> can be any number and <code>y</code> is 1 or 2.
When doubling the number we get <code>n * 2 = x * 6 + y * 2</code>.
<code>y * 2</code> is now 2 or 4, both numbers are still not divisible by 2. <code>x * 6</code> is divisible by 3, so adding 2 or 4 will make it not divisible by 3.</p>
</blockquote>
<p>Reducing the number of <code>I</code> by 3 obviously won't help, we can only use this rule in a useful way when we already have a number that is divisible by 3.
All other rules don't affect the number of <code>I</code>.</p>
<p>So the first exercise given by Douglas Hofstadter in <em>Gödel Escher Bach</em> is <strong>impossible</strong> to solve.</p>
<p>When you don't believe this proof, simply try it out and check if you're able to find a solution. <em>You won't.</em></p>
<p>The code for this page can be found at <a href="https://github.com/TN1ck/MIU">https://github.com/TN1ck/MIU</a>.</p>
<strong itemprop="author">- Tom Nick</strong>
</div>
<script type="text/javascript" src="script.js"></script>
</body>
</html>