数学辅导计算理论 | COMS 331 Theory of Computing

本次北美math数学辅导主要是完成计算理论的相关作业

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等多个学科的作业辅导服务
Follow Us
联系我们
Address

3262 La Jolla Village Dr, La Jolla, CA 92037

WeChat

skygpa

Email

skygpa@outlook.com