Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100755 207 lines (140 sloc) 6.585 kb
6245884 Peteris Krumins The initial import of Python and C++ busy beaver programs, the Perl visu...
authored
1 This is an implementation of The Busy Beaver Problem in Python and C++.
2
3 It was written by Peteris Krumins (peter@catonmat.net).
4 His blog is at http://www.catonmat.net -- good coders code, great reuse.
5
6 The code is licensed under the MIT license.
7
8 The code was written as a part of article "The Busy Beaver Problem" on my
9 website. The whole article can be read at:
10
11 http://www.catonmat.net/blog/busy-beaver/
12
13 ------------------------------------------------------------------------------
14
15 Table of contents:
16 [1] Introduction to The Busy Beaver Problem.
17 [2] Example Busy Beaver Turing Machine with 2 states.
18 [3] Busy Beaver Turing Machines for 1, 2, 3, 4, 5, and 6 states.
19 [4] busy-beaver.cpp and busy-beaver.py C++ and Python programs.
20 [5] draw_turing_machine.pl Perl program.
21
22
23 [1]-Introduction-to-The-Busy-Beaver-Problem-----------------------------------
24
25 The busy beaver problem is a fun theoretical computer science problem to know.
26 Intuitively, the problem is to find the smallest program that outputs as many
27 data as possible and eventually *halts*.
28
29 More formally it goes like this - given an n-state Turing Machine with a two
30 symbol alphabet {0, 1}, what is the maximum number of 1s that the machine may
31 print on an initially blank tape (0-filled) before halting?
32
33 It turns out that this problem can't be solved. For a small number of states
34 it can be reasoned about, but it can't be solved in general. Theorists call
35 such problems non-computable.
36
37 Currently people have managed to solve it for n=1,2,3,4 (for Turing Machines
38 with 1, 2, 3 and 4 states) by reasoning about and running all the possible
39 Turing Machines, but for n = 5 this task has currently been impossible.
40 While most likely it will be solved for n=5, theorists doubt that it shall
41 ever be computed for n=6.
42
02310a1 Peteris Krumins Improved readme.txt a little.
authored
43 ...
44
45 Continue reading on http://www.catonmat.net/blog/busy-beaver/
6245884 Peteris Krumins The initial import of Python and C++ busy beaver programs, the Perl visu...
authored
46
47
48 [2]-Example-Busy-Beaver-Turing-Machine-with-2-states--------------------------
49
50 Here is an example of a 2-state busy beaver. It's a Turing machine.
51
52 a0 -> b1r a1 -> b1l
53 b0 -> a1l b1 -> h1r
54
55 The initial tape is filled with 0's. The starting state is 'a' and the halting
56 state is 'h'. The notation 'a0 -> b1r' means "if we are in the state 'a' and
57 the current symbol on the tape is '0', then put a '1' in the current cell,
58 switch to state 'b' and move to the right 'r'. This process repeats until the
59 machine ends up in the halting state 'h'.
60
61 When run, it produces 4 ones on the tape and halts.
62
63 Here are all the tape changes. The tape is infinite and initially blank
64 (filled with 0's).
65
66 . starting state
67 |
68 v state change
69 ------------
70 ...|0|0|0|0|0|0|0|0|0|0|... a0 -> b1r
71 ...|0|0|0|0|1|0|0|0|0|0|... b0 -> a1l
72 ...|0|0|0|0|1|1|0|0|0|0|... a1 -> b1l
73 ...|0|0|0|0|1|1|0|0|0|0|... b0 -> a1l
74 ...|0|0|0|1|1|1|0|0|0|0|... a0 -> b1r
75 ...|0|0|1|1|1|1|0|0|0|0|... b1 -> h1r HALT
76 ...|0|0|1|1|1|1|0|0|0|0|...
77
78 The busy beaver stopped after 6 steps and the tape got filled with 4 ones.
79
80
81 [3]-Busy-Beaver-Turing-Machines-for-1-2-3-4-5-and-6-states--------------------
82
83 Turing Machine for 1-state Busy Beaver:
84
85 a0 -> h1r
86
87 The tape gets filled with 1 one and it terminates after 1 step.
88
89 Turing Machine for 2-state Busy Beaver:
90
91 a0 -> b1r a1 -> b1l
92 b0 -> a1l b1 -> h1r
93
94 The tape gets filled with 4 ones and it terminates after 6 steps.
95
96 Turing Machine for 3-state Busy Beaver:
97
98 a0 -> b1r a1 -> h1r
99 b0 -> c0r b1 -> b1r
100 c0 -> c1l c1 -> a1l
101
102 The tape gets filled with 6 ones and it terminates after 14 steps.
103
104 Turing Machine for 4-state Busy Beaver:
105
106 a0 -> b1r a1 -> b1l
107 b0 -> a1l b1 -> c0l
108 c0 -> h1r c1 -> d1l
109 d0 -> d1r d1 -> a0r
110
111 The tape gets filled with 13 ones and it terminates after 107 steps.
112
113 Turing Machine for 5-state Busy Beaver:
114
115 a0 -> b1l a1 -> a1l
116 b0 -> c1r b1 -> b1r
117 c0 -> a1l c1 -> d1r
118 d0 -> a1l d1 -> e1r
119 e0 -> h1r e1 -> c0r
120
121 The tape gets filled with 4098 ones and it terminates after
122 47176870 steps.
123
124 Turing Machine for 6 state Busy Beaver:
125
126 a0 -> b1r a1 -> e0l
127 b0 -> c1l b1 -> a0r
128 c0 -> d1l c1 -> c0r
129 d0 -> e1l d1 -> f0l
130 e0 -> a1l e1 -> c1l
131 f0 -> e1l f1 -> h1r
132
133 Currently best 6 state Busy Beaver outputs 4.6e1439 ones and
134 terminates after 2.8e2879 steps.
135
136 This result is a theoretical approximation. There are aproximately
137 0.3% of unchecked Turing Machines left.
138
139
140 [4]-busy-beaver.cpp-and-busy-beaver.py-programs-------------------------------
141
142 I decided to play with the busy beaver myself to verify the known results for
143 n <= 5. I implemented a Turing Machine in Python, which turned out to be too
144 slow, so I reimplemented it in C++.
145
146 I also wrote a visualization tool in Perl that shows how the Turing Machine's
147 tape changes from the start to the finish (see [5]).
148
149 The Python program is called busy-beaver.py and it takes one argument -
150 which n-state busy beaver to run.
151
152 The C++ program is called busy-beaver.cpp and takes the same argument.
153
154 Here is how to invoke the Python program:
155
156 $ ./busy-beaver.py 2
157 Running Busy Beaver with 2 states.
158 0
159 10
160 11
161 011
162 0111
163 1111
164 1111
165 Busy beaver finished in 6 steps.
166
167 The output is the tape changes and the final line tells us how many steps it
168 took.
169
170 You can use the tape change output and generate an image that shows the tape
171 changes in a much visual way. See the Perl program [5] below.
172
173 To use the C++ program, you have to first compile it:
174
175 $ g++ busy-beaver.cpp -o busy-beaver
176
177 And then you can run it as any other program:
178
179 $ ./busy-beaver 3
180 Running Busy Beaver with 3 states.
181 0
182 10
183 101
184 111
185 1111
186 111101
187 111111
188 Busy Beaver finished in 14 steps.
189
190 [5]-draw_turing_machine.pl-Perl-program.
191
192 I also wrote a visualization program for the output from busy-beaver program.
193 It takes the 0's and 1's you see above and turns into a nice png image.
194
195 Take a look at the original article http://www.catonmat.net/blog/busy-beaver/
196 to see how these images look.
197
198 ------------------------------------------------------------------------------
199
200 That's it. Enjoy the beavers! :)
201
202
203 Sincerely,
204 Peteris Krumins
205 http://www.catonmat.net
206
Something went wrong with that request. Please try again.