Nick Drozd

To know whether you'd enjoy it (which is the only measure of “worth it” I can think of in relation to this book), you could start with one of the recent sections on combinatorial algorithms (Volume 4A and part of Volume 4B have been published so far): http://www.cs.utsa.edu/~wagner/knuth/

For example, 7.2.1.2 on generating all permutations (http://www.cs.utsa.edu/~wagner/knuth/fasc2b.pdf) has a lot of cool mathematics, some low-language programs, some alphametic puzzles, .... Or 7.1.4 on Binary Decision Diagrams (http://www.cs.utsa.edu/~wagner/knuth/fasc1b.pdf) is on a little-known (IMO) data-structure presented in Knuth's unique way, which can solve many counting problems.

Stepping back a little, there are two ways you could read this book:

• Try to engage with the mathematics, try each exercise for at least half an hour before giving up and looking at the solution, etc. (Doing it this way can definitely be a massive time investment.) If you'd like to do this, and find the mathematics difficult, you should read Concrete Mathematics which Knuth co-wrote with Ron Graham and Oren Patashnik, which is a highly enjoyable book in itself.

• As mentioned in a recent post (https://nickdrozd.github.io/2019/05/17/knuth-check.html):

> By the way, if you’ve ever thought about reading TAOCP, give it a try. A lot of people will tell you that it’s a reference work, and it’s not meant to be read straight through, but that isn’t true. The author has a clear point of view and a narrative…

The machines used in the article don't have to halt whereas the busy beaver only admits Turing machines that halt. For the purpose of this article the Turing machine either has to halt or has to enter some kind of degenerate state where it can still technically run forever but is in some sense stuck in a trivial infinite loop. The precise details of this degenerate state are explained in this article:

https://nickdrozd.github.io/2021/01/14/halt-quasihalt-recur.html

This degenerate state is known as quasihalting. The author points out that for the traditional busy beaver function, let's call it BB, then BB(4) = 107. For this modified busy beaver function, let's call it, QQ, QQ(4) ~= 33 million.

The article goes into some detail why considering Turing machines that quasi halt instead of strictly halting provides some insight into some interesting questions, notably the spaghetti code conjecture.

Great writeup! I ended up following a few of the links and came across perhaps my favorite hand waving of all time for the validity of "The Spaghetti Code Conjecture"[1]. Basically:

For N=0,1: the problem is trivaial/degenerate.

For N=2: the Turing machine must go back and forth between states or else it'd just be stuck in one state forever, which wouldn't be very busy beaverish.

For N=n+1: well we just proved it up till n, so it seems pretty unlikely that n+1 would be different, things don't really just suddenly change like that y'know?

QED

So I'm not too surprised that this conjecture is being called into question.

[1]: https://nickdrozd.github.io/2021/01/26/spaghetti-code-conjecture.html

Counting the number of distinct TMs is not a simple task. The way you count it is the most broad (the count of all tables of values where each cell can have any (symbol, direction, state) combination). But this is a significant overcount of the bits needed to describe an arbitrary TM. for the BB(3, 4) case, there are only about 600B distinct TMs using the Tree Normal Form aka Brady's algorithm (https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html) which comes out to <40 bits.