nickdrozd

Congratulations! It's funny that the reward schedule is not based on importance. It's just 0x$1.00 for an error and 0x$0.20 for a suggestion, no matter what. Personally I have 0x$4.40 in the bank, more than the author's 0x$1.00, but none of my four errors and two suggestions were as important as this one. Getting your name in the book is pretty cool though!

This bug is only in the English description of the algorithm, right? No bug in either the MIX or MMIX implementations?

Here is an attempt:

  .de Q
  .nf
  .na
  .pso awk 'BEGIN{bs=sprintf("%c",92); pre=bs"&"} {out=pre; for(i=1;i<=length($0);i++){c=substr($0,i,1); if(c==bs) out=out bs bs; else out=out c} print out}' "\n[.F]"
  .ex
  ..
  .Q

Invoke with:

  nroff -U -Tascii quine.roff | sed -Ez '$ s/\n+$//'

Possibly relies too much on awk + sed. So maybe not A+, but better than nothing.

I gave a few attempts with ChatGPT and DeepSeek. Neither of them could get it right. So this goalpost can remain in place for the time being.

(I am assuming that the task is actually possible to accomplish. If it isn't possible, then it isn't a very good goalpost!)

How would your views about AI change if that goal were achieved? When my personal goal was reached, I found myself a little bit at a loss for words.

What would be a better way to measure intelligence?

Turing machine program states are conventionally represented with letters: A, B, C, etc. The starting state is A.

Now suppose you are running a Turing machine program from the beginning. The only state it has visited so far is state A. It runs until it reaches a state that has not been visited yet. What state is it? B? C? D? According to "tree normal form", the name for that next state just is the earliest unused state name, which in this case is B.

Visited states so far are A and B. Run until an unvisited state is reached again. What is its name? C? D? E? Tree normal form says that the state will be called C. And the next newly visited state will be D, etc. In general, the canonical form for a Turing machine program will be the one that puts initial state visits in alphabetical order. (This concept also applies to the multi-color case.)

It's not possible to tell of an arbitrary TM program whether or not that program is in tree normal form. But this proof doesn't look at arbitrary programs. It generates candidate programs by tracing out the normal tree starting from the root, thereby bypassing non-normal programs altogether.

That is what "essentially different" means here.

Great post. Some general takeaways for people who want Knuth checks:

1. You are unlikely to find errors in the algorithms themselves, especially if they've been officially published. You might find some infelicities, but these are not counted as full errors. For example, the author here found some confusing-but-not-wrong comments about local variables and unused registers. These are counted as "suggestions" (worth 0x20¢) rather than "errors" (worth 0x$1.00).

2. Knuth is pretty generous with credit -- if your suggestion leads him to find an error, you get credit for the error. The author here said that some defined variables went unused. Knuth pointed out that those variables were in fact used in an exercise. However, in looking this up he noticed a variable-related error in that exercise. Author is credited with 0x$1.00!

3. Exercises are more likely to contain errors and infelicities than the main text. And there are an awful lot of exercises.

4. Knuth includes a whole bunch of stuff in his books that is not related to CS. Lots of weird trivia and references. This stuff is more likely to be wrong than the main text. For example, Knuth mentions "icosahedral objects inscribed with Greek letters" and includes a reference to an article in the Bulletin de l’Institut français du Caire. But the author points out that the article is actually in the Bulletin de l’Institut français d’archéologie orientale. Whoops! 0x$1.00 for you!