News for hackers. Stuff that matters.
Re:How the Slowest Computer Programs Illuminate Math’s Funda... by tzs on Friday December 11, 2020 @02:57PM (#25390142)
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).

Re:How the Slowest Computer Programs Illuminate Math’s Funda... by lisper on Friday December 11, 2020 @03:07PM (#25390281)
> 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 :-)

Re:How the Slowest Computer Programs Illuminate Math’s Funda... by tromp on Friday December 11, 2020 @03:56PM (#25390881)
> 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).

Re:How the Slowest Computer Programs Illuminate Math’s Funda... by lisper on Friday December 11, 2020 @04:10PM (#25391037)
Is there really any point in quibbling over a difference of +/- 1 when contemplating (because that's really all we can do) the value of BB(n)?