Kamae, T.
Osaka J. Math.
10 (1973), 305-307

ON KOLMOGOROV'S COMPLEXITY AND INFORMATIONTETURO^KAMAE(Received July 15, 1972)
1. Summary. About Kolmogorov's complexity measure K, we prove
the following theorem, which seems rather unexpected.
Theorem, For any Cy there exists a sentence y such that
K(y)-K(y\x)>C
holds except for finitely many sentences x.
2. Preliminary.

Let 2 be any non-empty finite set of symbols. For n =0, 1, 2, •••, 2* denotes the n products of 2 . Let 2 * = U 2*. An element of 2*»=ois considered as a finite sequence of symbols belonging to 2 , and will be called
a sentence. Denote by A the unique element belonging to 2°. Let N= {1, 2, 3,•••} be the set of positive integers. A partial recursive function from 2*X N
to 2 * is called an algorithm. L e t / b e an algorithm. For sentences x and yy define{

min log2p••• if such p exists

oo... else.
An algorithm A is called an asymptotically optimal algorithm if for any algorithm/ , there exists a constant C such thatKA(y \x)<ooandKA(y\x)-K/y\x)£C
for any sentences x and y. It was proved in [1] that an asymptotically optimalalgorithm does exist and is unique in the sense that if A and B are asymptotically
optimal algorithms, then there exists a constant Csuch that \KA(y\x)—KB(y\x)\^ C
for any sentences x and y. Let A be any asymptotically optimal algorithm, which
is fixed throughout this paper. Denote KA(. \.) simply by K(. \.), which is called
Kolmogorov's complexity measure. Denote K(y)=K(y \ A) for any j G 2*,

306

T. KAMAE

3. Proof of Theorem. It is well known ([2]) that there exists a partial
recursive function ty from 2* X N X N to 2* such that(1) if s^ t, then i/r(.,., i) is an extension of ^ ( . , ., s),(2) ^4(#,/>)==y if and only if there exists t such that ty(x,p, t)=y, and(3) the domain of i/r is a recursive set of 2* X NX N.
For any p^Nand *eiV, define a subset S^, of 2* byFrom the property (3), it follows that the predicate about x, i and t that ^(A, i,is defined and equal to x is recursive.
Hence, {{x,p, t); x$Sp>t}
Theorefore,

is a recursive set of 2* XNXN.

L = {(/>, ^ f); ^ A , i, 0

w defined and yjr(Ay i,is a recursive set of NxNxN.
Define a partial recursive function j fromiVxiV to iV byj(t,p) = min {f; (p, f, i)GL} .
Let a- be a one-to-one recursive function from 2* onto iV. Finally, define analgorithm B bySince ^4 is an asymptotically optimal algorithm,Then, for any p^N, there exists the minimum /, which will be denoted by h(p)>such that A(A,j) is defined and does not belong to the set {A(A, i)\ z=l,2, ••*,p2}.
Put y(p)=A(A, h(p)). From the property (1) and (2), it follows that for anyp^N, there exists the minimum t, which will be denoted by T(p), such thatA(A, /)=i/r(A, z, t) for any i^h(p). This equality should be taken it for granted
that if one hand side is defined, then the other hand side is also defined and theycoincide. Then it is easy to verify that if t^r(p), then j(t,p) is defined andequal to h(p). Let Dp= {^G2*; <r(x)<r(p)}m Then Dp is a finite set for anyP^LN. Form the above descriptions, if »GS*-D p y then B(x,p) is defined andequal to y{p) for any p^ N. Since
K(y(p))>2log2p.
One the other hand, if x e S * - D f i , then

KOLMOGOROV'S COMPLEXITY AND INFORMATION

307

KB(y(p)\x)^log2p,since y(p)=B(x> p). Let Co be a constant sucn that
K(y\x)^KB(y\x)+C0for any ^,j;G2*. Let C be an arbitrary constant.
log2 p-C0^C.
Then

Select p so large thatfor any x^H*—Dpy which completes the proof of Theorem.
OSAKA CITY UNIVERSITY

References[1]A. N . Kolmogorov:Three approaches to the concept of "the amount of information",

Problems in the Transmission of Information, 1 (1965), 3-11.
[2] M. Davis: Computability and Unsolvability, McGraw-Hill, New York, 1958.