[FOM] Re: 204:Finite Extrapolation

Timothy Y. Chow tchow at alum.mit.edu
Tue Jan 20 13:28:31 EST 2004

Not all of the existing work on complexity of sequences is asymptotic.
See for example Knuth's Art of Computer Programming, Vol. 2, 3rd ed.,
section 3.5E, where among other things we find a definition of a random
finite sequence that causes there to be exactly 178 nonrandom binary
sequences of length 11.  (Sorry, I don't feel like typing them all in.)

Presumably the "limit" of Harvey Friedman's theory agrees with the known
asymptotic theories.  It would be interesting to see if there is a sense
in which it is consistent with the above definition of a nonrandom binary


More information about the FOM mailing list