FOM: RE: Chaitin

[hrant@arm.hpl.com]

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
          Additively Optimal Recursive Functions. Matematika, 
          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 
a more readable form 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