J003 - Fundamental Concepts of Computer Science
Prof. Juraj Hromkoviˇc
Exercise sheet 1
deadline: 17.4.2015
Common definitions
Σbool = {0, 1}
Definition 2.64 [Theoretical Computer Science, p.44]
A word x ∈ (Σbool)∗
is said to be random, if
K(x) ≥ |x|
A positive integer n is said to be random, if
K(n) = K(Bin(n)) ≥ log2(n + 1) − 1
Exercise 1.
Prove that, for every i ∈ N, the interval [2i
, 2i+1
− 1] contains at least one random integer.
Exercise 2.
Let wn = 02n2
for all n ∈ N. Give the best possible upper bound on the Kolmogorov
complexity of wn, measured in the length of wn. (You do not have to prove the optimality
of your bound.)
Exercise 3.
Let L ⊆ (Σbool)∗
be an infinite recursive language with the property that, for any length
k ∈ N, L contains exactly one word wk. How can the Kolmogorov complexity of wk be
bounded from above?
Exercise 4.
Define an infinite sequence of natural numbers y1, y2, y3, . . . with yi < yi+1 such that there
exists a constant c where, for all i ≥ 1,
K(yi) ≤ log2 log2 log2 yi + c
Exercise 5.
Prove that, for every n ∈ N and every i < n, the interval [2n
, 2n+1
− 1] contains at least
2n
− 2n−i
different numbers x such that K(x) ≥ n − i.
1
Exercise 6.
Prove that the following languages are not regular, using the method of Kolmogorov com-
plexity.
(a) L1 = {wwR
| w ∈ {0, 1}∗
}, where wR
denotes the reverse of w. (For w = a1a2 . . . an the
reverse of w is defined as wR
= anan−1 . . . a1.)
(b) L2 = {0n3
| n ∈ N}.
* Exercise 7.
Prove that there are at most finitely many prime numbers that can be viewed as random
numbers.
* Exercise 8.
We consider the language
Lkol = {w#x | K(w) ≤ Number(x); w, x ∈ Σ∗
bool}
(a) Prove that Lkol is undecidable.
(b) Is Lkol recursively enumerable?
2