1. 12

  2. 7

    I suggest replacing the programming tag with the compsci tag.

    This article doesn’t explain what it means by “Busy Beaver programs”. I had heard before of some busy beaver function that took a long but finite time to run, and I was confused why the article showed only control flow graphs and not code. It turns out that formally, in the busy beaver game, “a player should conceive a transition table aiming for the longest output of 1s on the tape while making sure the machine will halt eventually.” Busy beaver programs are a class of programs defined by their transitions; there is not just one, and they are not written in traditional programming languages.

    1. 1

      The final control-flow graph reminds me of the basics of chaos theory. One of the hallmarks of chaos is that if we have control flow with feedback which lets us pick one of two states arbitrarily and switch between them, then there can be paths which have any string of those states as subpaths. The feedback between the C and D states seems like it could be chaotic.