COMS 331: Theory of Computing, Spring 2021 Homework Assignment 9
Due at 10:00PM, Wednesday, April 14, on Gradescope.
Recall that a real number x ∈ R is computable if there is a computable function f : N −→ Q such that, for all r ∈ N,
|f(r) − x| ≤ 2−r.
Problem 57. Let x, y ∈ R. Prove: If x and y are computable, then x+y is computable.
Problem 58. Prove that the upper graph
G+ ={(x,n)∈{0,1}∗ ×N|C(x)≤n}
of the Kolmogorov complexity function is c.e. but not decidable.
Recall that s0, s1, s2, … is the standard enumeration of {0, 1}∗.
Problem 59. Prove that there is a constant c ∈ N such that, for all n ∈ N,
|C(sn) − C(sn+1)| ≤ c.
Define the tower function T : N −→ N by the recursion T(0) = 0
T (n + 1) = 2T (n)
for all n ∈ N.
Problem 60. Prove that there exist infinitely many strings x ∈ {0, 1}∗ such that
T(C(x)) < |x|. 1
Problem 61. Prove: If A ⊆ {0, 1}∗ is decidable, then there is a constant c ∈ N such that, for all x ∈ A,
C(x) ≤ log |A ∩ {0, 1}≤|x|| + c.
Problem 62. Let A ⊆ {0,1}∗, and let t be a real number with 0 < t < 1. Prove: For every n ∈ N such that |A ∩ {0, 1}n| > 2tn, there exists x ∈ A such that |x| = n and C(x) ≥ tn.
Recall the diagonal halting problem
K = {k ∈ N|Mk(k) ↓}. Problem 63. For each n ∈ N, define the string
by
zn = b0b1…bn−1 ∈ {0, 1}n 1 ifk∈K
bk= 0 ifk∈/K
forall0≤k