FOM: Long sequence and the Friedman-Shoenfield debate on Incompleteness

[Joe Shipman]

Harvey points out that n(3), defined as
"the longest length of a finite sequence from 3 letters in which no
block x_i,...,x_2i
is a subsequence of any other block x_j,...,x_2j.",
is a very short description of a very large integer.

But he's calculated an upper bound for n(3) which implies that an even
shorter description of an even larger integer is
"A_9(9), where A_1(m) = 2m, A_n+1(m) =A_nA_n...A_n(1), where there are m
applications of A_n."

However, if you change "3 letters" to "4 letters" in the first
description you get
(according to Harvey) a MUCH larger integer, which is not even
describable by a term of feasible size involving the A_*(*) operator.
So an "objective" criterion for the significance of his result is that
no one has ever named a larger integer with a shorter description (here
I shall define "description" informally to mean "a sentence that is
sufficiently clear that an ordinary student at M.I.T., given the
description, could easily write a program to output the integer", though
you could make this more precise in many ways without affecting the
truth of "no one has ever named a larger integer with a shorter
description").

Can anyone think of a counterexample to this claim?  (No fair using
noncomputable functions like the Busy Beaver function and saying "the
largest integer put out by any 99-quintuple Turing machine that halts on
blank input"; by the way, does anyone know how the current Busy Beaver
record-holders compare to Harvey's n(3) and n(4)?)  The shortest
description I can think of for an integer that transcends the n(k)
methods of feasible expression would involve Goodstein sequences, which
are only mildly complicated to describe; can anyone do better?

The debate on Incompleteness seems to boil down to "who should care
about the unprovability of a statement"?  Shoenfield says that
specialists in the field are the most important judges (e.g. for set
theory, Solovay's opinion matters more than 20 Fields medalists
[presumably not including P.J. Cohen!]) -- Friedman says that if you can
get specialists in other areas of mathematics interested ("general
mathematical interest") there is much more (and longer-lasting)
significance to the result, and he has clearly accomplished this much.
He further says that if you can get high school students or the educated
man on the street interested ("general intellectual interest") there is
a great deal more significance still.  I agree that his n(k) result
meets the g.i.i. test but it is not independent; and his independent
finite combinatorial results meet the g.mi. test but do not *directly*
meet the g.i.i. test (they do indirectly because it is of g.i.i. that
ordinary professional mathematicians are beginning to need to upgrade
their foundations).  When his independent statements reach the "high
school" level of simplicity and immediacy that "n(k) exists" has, a
revolution will have taken place.

-- Joe Shipman