| abstract | - In a contest on the XKCD forums to name the largest well-defined computable integer, Eliezer Yudkowsky submitted: Let T be the first-order theory of Zermelo-Fraenkel set theory plus the Axiom of Choice plus the axiom that there exists an I0 rank-into-rank cardinal. This is the most powerful known large cardinal axiom, AFAIK. I think that one such cardinal implies the existence of an infinite number of them, but if not, consider that condition added. Starting with P = 10:
* Search through all Turing machines with at most P states.
* Search through all proofs in T of length at most 2^^P that the program halts.
* Run all programs such that a halting proof exists, until they halt.
* Add up all the running times of all those programs.
* Set P to this sum. Repeat 10 times. The end result should be roughly equal to the fast-growing hierarchy at the proof-theoretic ordinal of T, plus 1, applied to 10. Since nobody can constructively characterize the proof-theoretic ordinal for second-order arithmetic, let alone ZFC, let alone ZFC plus large cardinal axioms, this computer program should compute a larger number than the fast-growing hierarchy for any ordinal for which we could directly write a computable ordering... So far as I know this should be the largest sort of number humanity can currently specify a program for computing, without new mathematics being done. You can add one to the resulting number, or run the program on 11 instead of 10, or play other trivial games like adding a copy of the small Veblen ordinal to the fast-growing hierarchy level or whatever, but you can't go significantly further until a significantly larger large cardinal is invented.
|
