Post by Peter Post by Paul Epstein
I had not even heard of the Moser number, though I had heard of Graham's
Here's another question: how will the post novel coronavirus national
debt compare to G and M?
To define large numbers, Graham and Moser (great drinking buddies though
they are) are not the way to go.
Busy beaver numbers are so large as to be non-computable and that's
only the first generation of non-computable numbers.
The definition of BusyBeaver(10) is [I hope]:
A deterministic finite state automaton S has 10 states and two
possible inputs -- 0 and 1.
A Turing tape is infinite in both directions with all squares initially 0,
and with a square designated as the starting square.
Assume that for each state and each input, S (deterministically) either
overwrites the current square with a 0 or overwrites it with a 1.
Similarly, depending on state and input, S either shifts one square to
the left or shifts one square to the right.
Similarly, depending on state and input, S either moves to a state or halts.
Assume also that S does halt eventually and that, after halting, at least
one 1 has been output and that all the 1s that have been written
BusyBeaver(10) is the maximum number of 1s that are possible in the output.
Since the machines halt and since there are only a finite number of
possible such machines, BusyBeaver(10) must be well-defined.
If you go like, BusyBeaver(1000), BusyBeaver(a trillion)
BusyBeaver(a trillion trillion trillion trillion trillion) etc.
[with the purpose of revisiting being 5 to 7 years old] then you
will get bigger numbers than the Graham/Moser way.