Re: Question on Chaitin
- From: stevendaryl3016@xxxxxxxxx (Daryl McCullough)
- Date: 14 May 2005 08:24:51 -0700
Timothy Murphy says...
>Taking the informational content (or entropy) H(A) of an axiomatic system A,
>one could identify A with the set of provable theorems in the system,
>and then define H(A) to be the minimal entropy of a Turing machine
>which outputs these theorems.
>(Here the entropy of a machine T is the length of the shortest string t
>such that U(ts) = T(s) for all s, where U is the chosen universal machine.)
>
>This ignores the ways in which the theorems are proved;
>and an alternative definition of H(A) would be that it is
>the minimal entropy of a machine which outputs proofs of the theorems.
>This is the same, up to a constant, as the entropy of a machine
>which given a provable theorem in the system
>will output a proof of that theorem.
>
>It is not clear to me that these two definitions
>will give the same value to H(A), up to a constant.
Definitely not. Two axiomatic systems A1 and A2 may have exactly the
same theorems, but wildly different axioms, so that it is
much harder to prove things in A2 than in A1.
I think that a mathematical theory is usually identified with its
set of theorems, regardless of how those theorems are proved. So
it's better to use the first definition, which doesn't care about
proofs.
I think that that is the reason that Chaitin's connecting complexity
with the "power" of a theory is misleading. ZFC is not much more
complex than PA, but it is much more powerful. There are certainly
much more complex theories than ZFC which are weaker than ZFC. Also,
any theory with an infinite number of theorems can of course prove
theorems of arbitrarily high complexity. So it's just false to say
that the complexity of a set of axioms limits the complexity of
what can be proved.
What is true is that if T is a consistent theory whose complexity is K,
then T cannot *prove* that any theorem has complexity much greater than K.
But there will be theorems of T with complexity much greater than K.
--
Daryl McCullough
Ithaca, NY
.
- References:
- Question on Chaitin
- From: David Costa
- Re: Question on Chaitin
- From: Torkel Franzen
- Question on Chaitin
- Prev by Date: Re: A simple undiagonalisable list - ILLUSTRATED
- Next by Date: Re: Question on Chaitin
- Previous by thread: Re: Question on Chaitin
- Next by thread: Re: Question on Chaitin
- Index(es):
Relevant Pages
|
