Math 597B – Homework #5

April 13, 2007

1. A set A ⊆ ℕ is said to be simple if (a) A is recursively enumerable,

(b) ℕ \ A is infinite, and

(c) ℕ \ A includes no infinite recursively enumerable set. Let A be a simple, recursively enumerable set. Prove that A is neither recursive nor many-one complete.

2. For m, n ∈ ℕ let us write m ≪ n to mean that f(m) < n where f is some fixed fast-growing recursive function. For instance, we could take f(m) = a stack of 2’s of height m. For n ∈ ℕ let us write C(n) = C(⟨\underbrace{1, …, 1}_{n}⟩).

Prove that the set {n ∈ ℕ | C(n) ≪ n} is simple.

3. Prove that C(τ) ≤ |τ| + O(1).

This means: (∃c) (∀τ ∈ 2^{<ℕ}) (C(τ) ≤ |τ| + c).

4. Prove that C(τ) ≤ K(τ) + O(1).

5. Prove the following series of inequalities:

(a) K(τ) ≤ 2C(τ) + O(1).

(b) K(τ) ≤ C(τ) + 2 log C(τ) + O(1).

(c) K(τ) ≤ C(τ) + log C(τ) + 2 log log C(τ) + O(1).

(d) Et cetera. Here log n is defined to be the base 2 logarithm of n.

6. (a) Prove that K(|τ|) ≤ K(τ) + O(1).

(b) Prove Zambella’s Theorem: For each c, the cardinality of

{τ | |τ| = n, K(τ) ≤ K(|τ|) + c}

is bounded by a constant which is independent of n.

(c) In fact, this constant is O(2^{c}).