Re: Panu Raatikainen's review of two of Chaitin's books.

From: Ralph Hartley (hartley_at_aic.nrl.navy.mil)
Date: 05/19/04 

Date: Tue, 18 May 2004 18:06:48 -0400

Daryl McCullough wrote:

> The only way that I can think of for Chaitin's connection between
> complexity and power is to make it true by definition: Letting
> K(T) = Kolmogorov complexity (the size of the smallest Turing
> machine that can generate the theorems of T), we define
> (in the case T is a subset of True Arithmetic, and S is a
> true sentence in the language of arithmetic)
>
> hardness(S) = min { K(T) | T is a subset of True Arithmetic,
> and T proves S }
>
> power(T) = max { hardness(S) | T proves S }
>
> These definitions have the consequence that more powerful theories
> can prove harder theorems, but I don't think they capture the
> intuitive notion of "hardness" very well. In particular, this
> definition of "hardness" makes it impossible to have a simple
> sentence that is hard to prove, because every true sentence S
> can be trivially proved by the theory { S }, whose power
> is at most K(S).

Here's a likely looking definition.

Given T and a statement S, such that T+S is consistent, the information
content of S relative to T (let's write it I(S|T)) is the length of the
shortest set of axioms A such that S is a theorem of T+A and ~S is not.

This definition is not limited to "true arithmetic" (whatever that is).

If S is a theorem of T, then then I(S|T)=0.

You can always prove S by adding S as an axiom, so I(S|T) <= |S|.

You might want to call any statement for which I(S|T) = |S| a "random fact".

There is no algorithm that takes T and S and computes I(S|T) (or even tells
if it is zero or not).

This definition has a problem!

The problem is that it depends critically on the language in which axioms
are written. We would like something that only depends on logical
relationships, and not on syntax.

One might replace the length of the axioms with their Kolmogorov
complexity, but that doesn't really help. It just replaces one dependency
with another.

Actually, I'm pretty sure I've seen a definition like this before. I's been
a long time since I studied this stuff.

Ralph Hartley

Relevant Pages

  • Re: Godel proved maths inconsistent not incompleteness theorem
    ... you are using them in a standard way in CBL. ... assertion that the set of theorems is ... Any system where PR being the set of theorems satisfies the axioms. ... theorems or truths of any given system besides your say so. ...
    (sci.logic)
  • Re: primitive recursive: obsolete?
    ... we have to add more axioms. ... all true sentences of arithmetic in the language of PA. ... logic we define the set of sentences true in the standard model of PA ... theorems" or not has no bearing on the fact that what I said is ...
    (sci.logic)
  • Re: Godel proved maths inconsistent not incompleteness theorem
    ... It's the *axioms* ... If no more theorems to generate, ... Otherwise it's not an axiomatic system. ... The program was to be able to rewrite all mathematics starting using ...
    (sci.logic)