Re: Technology Advancements (was: Generation gap)

Anders Sandberg (asa@nada.kth.se)
13 Oct 1997 19:28:12 +0200


"Lee Daniel Crocker" <lcrocker@mercury.colossus.net (none)> writes:

> The only objective meaning of "infinitely complex" I can think of is
> axiomatically true: "mathematics" is simply "the set theorems expressible
> in mathematical terms". The cardinality of that set is that same as the
> cardinality of largest set of symbols in the language. We can never
> actually write down more than Aleph-null theorems (the number of integers),
> but since mathematics includes real numbers, of which there are Aleph-one,
> the cardinality of mathematical theorems is at least that.
>
> Godel really has nothing to do with complexity at all. It is nothing more
> than the proof that of that infinite number of mathematical theorems,
> the set of "true" theorems and the set of "provable" ones differ.

Actually, you can define infinite complexity if you are using
algorithmic information theory. The algorithmic complexity of something
is the length of the shortest computer program (for a given Turing machine)
that can produce it; for a random sequence of bits the complexity is
maximal. If something that has an infinite size can be generated by
a finite program it has a finite complexity, of course. But one could
imagine systems that require infinite programs. Gödel's theorem seem
to imply that such programs are needed for sufficiently complex
formal systems: you cannot generate all theorems using any finite
program; however, you can at least create a program of "length"
Aleph-null to generate them (simply by concatenating all the
possible theorems and adding a trivial lookup function so that
it can give you theorem X). So mathematics is infinitely complex,
for the right definition of complexity.

Personally I'm not sure algorithmic complexity is the best definition;
but at least we can use it and it has interesting ties to a lot of other
fields.

[Fun idea: systems where the cardinality of theorems is larger than
Aleph-null. For example, the axioms may be parametrized with real
numbers like "if X is a theorem, then S(X,lambda) is a theorem for
all real lambda". Or can they be collapsed into the "usual" kind of
systems?]

-- 
-----------------------------------------------------------------------
Anders Sandberg                                      Towards Ascension!
asa@nada.kth.se                            http://www.nada.kth.se/~asa/
GCS/M/S/O d++ -p+ c++++ !l u+ e++ m++ s+/+ n--- h+/* f+ g+ w++ t+ r+ !y