Hm, interesting. I think the discrepancy comes about because Scott takes into account equivalence under state permutation, but I'd have to crunch some more algebra to be sure. In any case, I'd certainly accept Scott A. as an authoritative source on this.
[UPDATE] No, that can't be it. A two-state machine has no equivalent permutations because one state has to be a privileged start state. And even if it did, there are only two permutations of two states, so this can't possible explain the discrepancy.
[UPDATE2] Turns out there is a typo in Scott's formula. The correct answer is (4(n+1))^2n, not (4n+1)^2n. This is because each state transition has 4(n+1) possible values, 4 possibilities for the movement direction and symbol to write (with two possibilities each) and, independently, n+1 possible next states (including the halt state). The result for 2-state machines is, as /u/tromp correctly noted, 20736.
[UPDATE3] (I think I'm about to set some kind of record here.) As a sanity check, it's pretty easy to see that the result has to be an even number because every possible TM has a corresponding distinct TM where the direction of movement or written symbol in any state is changed to the opposite value.
OK, I looked at Aaronson's paper. Here is his description of a Turing machine:
> Following Radó’s conventions, we consider Turing machines over the alphabet {0, 1}, with a 2-way infinite tape, states labeled by 1, ... , n (state 1 is the initial state), and transition arrows labeled either by elements of {0, 1} × {L, R} (in which case the arrows point to other states), or else by “Halt” (in which case the arrows point nowhere).
Note that under this definition when the machine halts it does NOT write the tape or move the head.
That gives the machine 4n+1 ways to respond to a given input. If it is not halting, there are 4 actions it can take (0L, 0R, 1L, 1R) and n states it can go to. If it is going to halt, there is just one action. Hence, 4n + 1 possible responses.
With two possible inputs, that's (4n+1)^2 possible rules, and with n rules that's (4n+1)^(2n) possible machines as given by Aaronson and used by the article's author, which is indeed 6516 when n = 2.
For machines that do write and move even when halting, we can treat halt as an extra state, which gives the formula in your UPDATE2.
For completeness we should consider machines that write but do not move on halt. Their formula is (4n+2)^(2n), or 10000 for n = 2.
(That would also be the formula for rather pointless machines that move but do not write on halt).
> Note that under this definition when the machine halts it does NOT write the tape or move the head.
That's a good point. This is a more parsimonious definition because if it's going to halt we don't really care what it does immediately before.
I guess the real lesson here is that it's pointless to quibble about this because the number turns on arbitrary features of your definitions. (Also, if you think Scott Aaronson has made a mistake, even a trivial one, you are almost certainly wrong :-)
> if it's going to halt we don't really care what it does immediately before.
The final move does not matter, but the symbol written matters to the extent that BB(n) is defined as the number of 1s on the tape upon halting.
So, while redundant, the 4(n+1) count is chosen for parsimony. If one is willing to specialize the transition to halt to have no move and a mandatory write of 1, then a count of 4n+1 still agrees upon the same value of BB(n).
[UPDATE] No, that can't be it. A two-state machine has no equivalent permutations because one state has to be a privileged start state. And even if it did, there are only two permutations of two states, so this can't possible explain the discrepancy.
[UPDATE2] Turns out there is a typo in Scott's formula. The correct answer is (4(n+1))^2n, not (4n+1)^2n. This is because each state transition has 4(n+1) possible values, 4 possibilities for the movement direction and symbol to write (with two possibilities each) and, independently, n+1 possible next states (including the halt state). The result for 2-state machines is, as /u/tromp correctly noted, 20736.
[UPDATE3] (I think I'm about to set some kind of record here.) As a sanity check, it's pretty easy to see that the result has to be an even number because every possible TM has a corresponding distinct TM where the direction of movement or written symbol in any state is changed to the opposite value.