Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site cornell.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!harpo!seismo!cmcl2!floyd!vax135!cornell!dietz
From: dietz@cornell.UUCP (Paul Dietz)
Newsgroups: net.math
Subject: Interesting Numbers
Message-ID: <95@cornell.UUCP>
Date: Sun, 20-May-84 14:21:17 EDT
Article-I.D.: cornell.95
Posted: Sun May 20 14:21:17 1984
Date-Received: Mon, 21-May-84 05:45:05 EDT
Organization: Cornell Univ. CS Dept.
Lines: 15

A measure of how "interesting" a number is the size of the shortest Turing
machine that can print the number.  Interesting numbers can be printed by
very short Turing machines.  A number is random if the length of the
shortest turing machine that can print it is approximately equal to the
number of bits required to write out the number explicitly.  One can show
that most numbers are random (and hence uninteresting).  One can also show
that in any consistent formal system there exists a constant k such that for
nay number n, one cannot prove (in the formal system) that n can only be
printed by Turing machines with descriptions of length greater than k
(otherwise, one could construct a Turing maching which would search for such
proofs and print the first number it found; the length of this turing
machine being less than k, k chosen to be sufficiently large).  This is true
even though all but a finite set of numbers must have complexity greater
than k!  Look up papers by Kolmogorov or Chaitin (the latter had some papers
in JACM on the subject).