Busy Beaver

Author

Eric W. Weisstein
April 16, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/ComputationalSystems/BusyBeaver.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/BusyBeaver.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Additional Authors

Based on ideas in Stephen Wolfram's A New Kind of Science

Figures adapted from Stephen Wolfram's A New Kind of Science

Legacy documentation for NKSExplorer package available at https://reference.wolfram.com/legacy/applications/nksx/

Code

RuleList[n_]:=Flatten[Outer[List,Range[n],{1,0}],1]

BusyBeaver[2]:=Thread[RuleList[2]->{{2,1,1},{2,1,-1},{0,1,1},{1,1,1}}]
BusyBeaver[3]:=Thread[RuleList[3]->{{0,1,1},{2,1,1},{3,0,1},{2,1,-1},{1,1,-1},{3,1,-1}}]
BusyBeaver[4]:=Thread[RuleList[4]->
{{2,1,-1},{2,1,1},{3,0,-1},{1,1,-1},{4,1,-1},{0,1,1},{1,0,1},{4,1,1}}]
BusyBeaver[5]:=Thread[RuleList[5]->
{{3,1,1},{2,1,-1},{2,1,-1},{3,1,-1},{5,0,1},{4,1,-1},{4,1,1},{1,1,1},{1,0,1},{0,1,-1}}]

Maximal Σ(3)

shallit=Thread[RuleList[3]->{{3,1,-1},{2,1,1},{2,1,1},{1,1,-1},{3,1,1},{2,1,-1}}]

Show[Graphics[{
Rectangle[{-.17,.85},{1.17,1},NKSGraphics[78.1,{shallit}]],
Rectangle[{0,0},{1,.8},NKSGraphics[78.2,{shallit,10,13}]]
},PlotRange->All]]

V5

Show[Graphics[{
Rectangle[{-.17,.85},{1.17,1},NKSGraphics[78.1,{shallit}]],
Rectangle[{0,0},{1,.8},NKSGraphics[78.2,{shallit,10,13}]]
},PlotRange->All]]

Maximal S(n)

2

With[{bb=BusyBeaver[2]/.{0,x__}:>{1,x}},
Show[Graphics[{
Rectangle[{-.17,.85},{1.17,1},NKSGraphics[78.1,{bb}]],
Rectangle[{0,0},{1,.8},NKSGraphics[78.2,{bb,6,6}]]
},PlotRange->All]]
]

V5

With[{bb=BusyBeaver[2]/.{0,x__}:>{1,x}},
Show[Graphics[{
Rectangle[{-.17,.85},{1.17,1},NKSGraphics[78.1,{bb}]],
Rectangle[{0,0},{1,.8},NKSGraphics[78.2,{bb,6,6}]]
},PlotRange->All]]
]

3

With[{bb=BusyBeaver[3]/.{0,x__}:>{1,x}},
Show[Graphics[{
Rectangle[{-.17,.85},{1.17,1},NKSGraphics[78.1,{bb}]],
Rectangle[{0,0},{1,.8},NKSGraphics[78.2,{bb,7,21}]]
},PlotRange->All]]
]

V5

With[{bb=BusyBeaver[3]/.{0,x__}:>{1,x}},
Show[Graphics[{
Rectangle[{-.17,.85},{1.17,1},NKSGraphics[78.1,{bb}]],
Rectangle[{0,0},{1,.8},NKSGraphics[78.2,{bb,7,21}]]
},PlotRange->All]]
]

4

With[{bb=BusyBeaver[4]/.{0,x__}:>{1,x}},
Show[Graphics[{
Rectangle[{.4,.85},{.6,1},NKSGraphics[78.1,{bb}]],
Rectangle[{0,0},{1,.8},NKSGraphics[78.2,{bb,30,107}]]
},PlotRange->All]]
]

V5

With[{bb=BusyBeaver[4]/.{0,x__}:>{1,x}},
Show[Graphics[{
Rectangle[{.4,.85},{.6,1},NKSGraphics[78.1,{bb}]],
Rectangle[{0,0},{1,.8},NKSGraphics[78.2,{bb,30,107}]]
},PlotRange->All]]
]

Best known S(5) and Σ(5)

With[{bb=BusyBeaver[5]/.{0,x__}:>{1,x}},
Show[Graphics[
NKSGraphics[78.1,{bb}]
]]]

V5

With[{bb=BusyBeaver[5]/.{0,x__}:>{1,x}},
Show[Graphics[
NKSGraphics[78.1,{bb}]
]]]