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

From: Torkel Franzen (torkel_at_sm.luth.se)
Date: 05/13/04 

Date: 13 May 2004 16:12:26 +0200

erayo@bilkent.edu.tr (Eray Ozkural exa) writes:

> The correlation I have on my mind is digital. But let me first become
> sure of your reference in "a set of axioms of enormous complexity that
> proves only a set of truths of the form s+t=u".

  Trivially, for every n there is an arithmetical axiom A of the form
k+1=1+k such that the Kolmogorov complexity of A is greater than
n. Anything A proves is a consequence of the low-complexity axiom
(x)(x+1=1+x). Thus it is unclear what you have in mind in speaking of
a direct dependence between the complexity of a formal system and its
capacity to prove theorems. How is this dependence to be spelled out?

Relevant Pages

  • Re: a complexity measure for subsets of R
    ... The goal is to define a "complexity measure", ...    A' and B' are disjoint and measurable, ... c is translation invariant -- that is, ... Axiom should be retained. ...
    (sci.math)
  • Re: Raatikainens Complexity Complex
    ... Thus I believe the Kolmogorov ... > I cannot say what effect this interpretation has on the rest of his ... stands for the axiom schema of F1. ... A1 can have high complexity. ...
    (sci.math)
  • Re: a complexity measure for subsets of R
    ... of complexity. ...     A' and B' are disjoint and measurable, ... about Axiom. ... If all non-measurable sets are equally complex, ...
    (sci.math)
  • Re: Raatikainens Complexity Complex
    ... Thus I believe the Kolmogorov ... > I cannot say what effect this interpretation has on the rest of his ... stands for the axiom schema of F1. ... A1 can have high complexity. ...
    (comp.theory)
  • Re: Panu Raatikainens review of two of Chaitins books.
    ... >> is no direct dependence between the complexity of an axiom system and ... > complexity of a formal system and its capacity to prove theorems? ... sure of your reference in "a set of axioms of enormous complexity that ...
    (comp.theory)