# 数学代写计算理论 | COMS 331 Theory of Computing

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<n. Provethatthereisaconstantc∈Nsuchthat,foralln∈N,

C(zn) ≤ 2 log (n + 1) + c.

2

## 联系顾问微信, 24小时在线报价 SkyGPA是一家覆盖70+学科的专业代写公司，我们为您提供100%原创、100%满意承诺，包括金融、经济、统计、Marketing、Accounting、Computer Science、MATH 数学、土木工程、生物信息、EE等多个学科的作业代写服务