How was the busy beaver candidate for 6 states calculated?

Question

The current busy beaver candidate on 6 states, with the original binary alphabet configuration, produces about 10^18267 1's, according to the wiki page on Busy Beaver. I could not find any working links to research that further. My question is, what methods were applied to emulate such a long running Turing machine? I am also interested in general methods that could produce that kind of a result, even if they were not applied in this case.

Answer 1

Heiner Marxen provides a description of several techniques used to simulate extremely long-running Turing machines: http://www.drb.insel.de/~heiner/BB/mabu90.html

First some notation: A TM configuration can be represented like: 10 B> 111101. Which means that it is in state B and the head is over the 1 at position 3 from the left (the symbol that the > points to). If this TM has a transition (B, 1) -> (0, R, B) then the next configuration will be 100 B> 11101.

There are specifically 3 techniques:

1. Tape compression: Represent a long tape as 1 0 B> 1^18 0 1^2 instead of 10 B> 111111111111111111011. In addition to potential space savings, this can lead to time savings when you have transitions like (B, 1) -> (0, R, B) which can jump over the entire stack of symbols: 1 0 B> 1^18 0 1^2 -> 1 0^19 B> 0 1^2.
2. Macro machine: Instead of considering the TMs actions on each individual symbol, think of it as acting on blocks of N symbols. This allows us to compress the tape like: 11 10 A> 01^6 11. Many TMs which do not compress well with (1) will with some Macro machine for some block size N.
3. Proof system: Finally, by automatically detecting, proving and applying generic rules to specific configurations, you can get significant time improvements for some machines (including all record-holding TMs). An example rule might be: 100^a B> 010^(b+1) -> 100^(a+2b) B> 010^1 for any a,b >= 0 in b^2 - b + 4 steps.