5
$\begingroup$

But for how long? Let's take it from the top!

enter image description here

Be ready to allocate upwards of 16.7KB of memory for this task, you eager beavers you.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
6
$\begingroup$

It is hinted

from the words "busy" and "beaver" that the image is a depiction of a Turing machine (a busy beaver is a halting 2-symbol Turing machine printing the most ones). The markings on the ends of the edges denote various aspects of the transition (no flipping!)

Number the states 0 to 5 starting from the top and going clockwise. The transitions are given below in (old state, old symbol, new symbol, movement direction, new state) format:
(0,0,1,L,1)
(0,1,1,L,0)
(1,0,1,R,2)
(1,1,1,R,1)
(2,0,0,R,5)
(2,1,1,R,3)
(3,0,1,L,0)
(3,1,0,R,4)
(4,0,0,L,0)
(4,1,1,R,2)
(5,0,1,L,4)
(5,1,halt)

We start at state 0 ("take it from the top").

Now

when implemented in C++ the above Turing machine halts after 13,122,572,796 steps, which is how long they'll be kept busy for. 204,918 positions are used, of which 136,610 are ones.

Improve this answer
$\endgroup$
6
  • $\begingroup$ All correct! I took the Turing machine from this page (itself from the "Historical Survey of Busy Beavers"), and I actually realize now that my "1.7KB" clue was off by a decimal place (thankfully it's more just a retrospective easter egg); I've fixed it to be 16.7KB (as that is approximately how much information is contained in 136,612 bits, although of course any implementation will likely in practice need more like your 204,918 figure). $\endgroup$
    – Feryll
    Commented Jun 20, 2021 at 7:58
  • $\begingroup$ @Feryll hey, I'm a brony too. Is there a way we could keep in touch? $\endgroup$
    – Parcly Taxel
    Commented Jun 20, 2021 at 8:01
  • $\begingroup$ Consider it done :) $\endgroup$
    – Feryll
    Commented Jun 20, 2021 at 8:05
  • $\begingroup$ Ah, beat me to it - I was running it on a simulator but had to let it run overnight. Nicely solved! $\endgroup$
    – Deusovi ♦
    Commented Jun 20, 2021 at 13:48
  • $\begingroup$ @Desuovi My code took less than two minutes to find the solution. I thought this was going to be much lengthier than lunch, but I was wrong. $\endgroup$
    – Parcly Taxel
    Commented Jun 20, 2021 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.