FOM: RE: Chaitin

hrant@arm.hpl.com hrant at arm.hpl.com
Wed Apr 4 12:33:40 EDT 2001

Reply to Friedman 8:50PM 3/30/01.

Harvey Friedman wrote:

> What is the result in your paper of which your Theorem is an evident
> consequence? Perhaps this might tell us why your Theorem was perhaps not
> more widely known to people studying Chaitin?

Below I will try to answer, at leat partially, to that questions.

Above all, I beg your pardon for a wrong citation given in my previous letter.

The paper I should citate is the following:

H.B.Marandjian, On  Strongly Effective Immunity of Pivots of
Izvestija Akademii Nauk Armjanskoj SSR, 1972,vol.VII,
No. 6,391-398, (in Russian, English summary).

The proofs are presented there in the language of the constructive
mathematics and require some skills and familiarity with
the works of A.A.Markov and N.A.Shanin.
May be this circumstances may answer the second part of the question.

Actually, in constructive mathematics (CM) as well as in intuitionistic
mathematics (IM), as we all well know, if \alpha is an asymptotically
optimal function then K_\alpha is not a function at all (because it
cannot be computed effectively), so K_{\alpha}(n) >= f(n) is meaningless,
and hence all the proofs there are to be done with predicates expressing
that facts.
Notice, that in general, one cannot prove that the values K(n) do exist
in CM or IM but due to existence of computable upper bound for K(n) it
is possible to prove the double negation of existence of values K(n).

English translation of works of the present author concerning
complexity (particularly, Kolmogorov complexity, and containing
the material contained in the paper cited above) is presented in

H. B. Marandjian, Selected Topics in Recursive Function Theory in
Computer Science,DTH (Denmark Technical University),
Lyngby, 1990.

The theorem used to prove the statement given in my previous letter
is the following (it is presented here in common words):

THEOREM. For any partial recursive function f, if for any n
convergence of f(n) implies K(n) >= f(n) then f is constructively
bounded.

Hence if W_m consists of pairs <i,j> such that K(i)>=j then the set of
j-s is constructively bounded. Let denote the bound by C.
Then no pair <i,C+1> can belong to W_m.

Thank you very much for patiency.

Hrant