New Semester Started Get 50% OFF Study Help! --h --m --s Claim Now

Question Answers

Textbooks

Find textbooks, questions and answers

Oops, something went wrong!

Change your search query and then try again

Result Not Found

Books FREE
Study Help
Tutors
AI Study Planner NEW
Sell Books

Search
Sign In
Register

study help
business
elementary probability for applications

An Introduction To Kolmogorov Complexity And Its Applications 4th Edition Ming Li, Paul Vitányi - Solutions

[28] Let ω = ω1ω2 ... be an infinite binary sequence. The entropy function H(p) is defined by H(p) = p log 1/p+ (1−p) log 1/(1−p).(b) Prove the following: If the ωi’s are generated by coin flips with probability p for outcome 1 (a Bernoulli process with probability p), then for as n goes
[12] Show that given x, y, and C(x, y), one can compute C(x)and C(y) up to an additive logarithmic term O(log C(x, y)).Comments. Hint: use symmetry of information and upper semicomputability. Suggested by L. Fortnow.
[42] Let x be a string of length n.(a) Show that the equality C(x, C(x)) = C(C(x)|x) + C(x) + O(1) can be satisfied only to within an additive term of about log n.(b) Prove that C(x, y) = C(x|y) + C(y) can hold only to within an additive logarithmic term without using Exercise 2.8.1, Item (a), and
[17] The following equality and inequality seem to suggest that the shortest descriptions of x contain some extra information besides the description of x.(a) Show that C(x, C(x)) = C(x) + O(1).(b) Show that C(x|y, i − C(x|y, i)) ≤ C(x|y, i) + O(1).Comments. These (in)equalities are in some
[19] We define a variant of the busy beaver function BB(n)in Exercise 1.7.19 on page 45. Let BC(n) be the largest natural number m such that C(m) ≤ n. Let φ1, φ2,... be the standard effective enumeration of partial computable functions.(a) Show that BC(n) > φ(n), where φ = φk, for all n ≥
[37] A set H of natural numbers is called hyperimmune if there is no total computable function f such that f(i) > hi for all i, where hi is the ith element of H in increasing order. That is, H is immune(Exercise 2.7.14, page 187) but the variety of immunity of H is due to the fact that the function
[32] Show that there exists an immune set I (a set without an infinite computably enumerable subset, for instance the complement of a set B as in Theorem 2.7.1, Item (iii)), such that there is a probabilistic Turing machine that computes the characteristic function of some infinite subset of
[22] Show that the set K0 used in Lemma 1.7.6 on page 35 is not many-to-one reducible to the set B featured in Corollary 2.7.2 on page 179, while B is many-to-one reducible to K0.Comments. Hint: use Exercise 1.7.16.K0 is m-complete, while B is simple and hence not m-complete. The set K0 is of a
[20] Define the state complexity S(x) of a finite binary string x as the least n such that there is a Turing machine with n states that started in the standard initial conditions of empty tape and distinguished start state will eventually halt with x on its output tape. All machines considered are
[39] We assume familiarity with the notion of truth-table reducibility. Let χ be the characteristic sequence of a computably enumerable set A. Here C(χ1:n; n) is the uniform complexity of Exercise 2.3.2.(a) Show that A is complete under weak truth-table reducibility iff for some unbounded total
[42] Use Kolmogorov complexity to prove the existence of Turing degrees of unsolvability (Exercise 1.7.16) between the computable sets and Turing-complete sets (such as K0).Comments. Source: [R.P. Daley, J. Symb. Logic, 46(1981), 460–474; Inform. Contr., 52(1982), 52–67].
[30] This exercise assumes knowledge of the notion of Turing degree, Exercise 1.7.16.Every Turing degree contains a set A such that if χ is the characteristic sequence of A, then C(χ1:n|n) ≤ log n for all n.Comments. Hence, a high degree of unsolvability of a set does not imply a high
[32] Let φ1, φ2,... be the standard enumeration of partial computable functions. The diagonal halting set is {x : φx(x) < ∞} (also denoted by K). The Kolmogorov set is {(x, y) : C(x) ≤ y}. We assume familiarity with notions in Exercise 1.7.16.To say that a set A is computable in a set B is
[25] Consider an enumeration W1, W2,... of all computably enumerable sets. A simple set A is effectively simple if there is a computable function f such that Wi ⊆ A¯ implies that d(Wi) ≤ f(i) (where A¯ is the complement of A). The set A¯ is called effectively immune.(a) Show that the set B
[25] Prove the following strange fact (Kamae’s theorem). For every natural number m there is a string x such that for all but finitely many strings y, C(x) − C(x|y) > m.Comments. There exist strings x such that almost all strings y contain a large amount of algorithmic information about x.
[34] Is there a symmetric form of Theorem 2.7.2 (Barzdins’s lemma) using only unconditional complexities? The answer is negative.Show that there is a computably enumerable set A ⊆ N and a constant c such that its characteristic sequence χ satisfies C(χ1:n) ≥ 2 log n − c for infinitely
[27] Is there a symmetric form of Theorem 2.7.2 (Barzdins’s lemma) using only conditional complexities? The answer is negative.Show that there is no computably enumerable set such that its characteristic sequence χ satisfies C(χ1:n|n) ≥ log n + O(1) for all n.Comments. Hint: Let χ be the
• [26] Let A ⊆ N be a computably enumerable set, and let χ =χ1χ2 ... be its characteristic sequence. We use the uniform complexity C(χ1:n; n) of Exercise 2.3.2 on page 130.(a) Show that C(χ1:n; n) ≤ log n + O(1) for all A and n.(b) Show that there exists an A such that C(χ1:n; n) ≥
[10] Let A = {x|Cx) < l(x)/2}. Show that A is a simple set in the sense of E. Post.Comments. Thresholds l(x) − 1 or log lx work as well. Hint: use Theorem 2.7.1 Item (iii) on page 177.
[10] Show that there exists a constant c such that C(0n|n) ≤ c for all n, and C(0n) ≥ log n − c for infinitely many n.
[M35] A finite binary string x of length n is called δ-random if C(x|n) ≥ n−δ. A Turing machine place-selection rule R is a Turing machine that selects and outputs a (not necessarily consecutive) substring R(x) from its input x. If R is the kth Turing machine in the standard enumeration, then
[29] Let limn→∞ 1 nn i=1 ωi = p for an infinite binary sequenceω = ω1ω2 ..., for some p between 0 and 1 (compare Section 1.9).(a) Show that if C(ω1:n) ∼ n, then p = 1 2 .(b) Show that if p = 1 4 , then C(ω1:n) ≤ 0.82n asymptotically.(c) Show that in general, if c = p log 1/p + (1 −
[24] The great majority of binary strings of length n have a number of 0s in between 1 2n− √n and 1 2n+ √n. Show that there are x’s of length n with 1 2n + Ω(√n) many 0s, with C(x) = n + O(1).
[25] A sequence over a b-ary alphabet is normal in base b if every block of length k occurs (possibly overlapping) with limiting frequency 2−k. A sequence is normal if b = 2. A sequence is absolutely normal if it is normal in every base. A sequence (in base 2) is block-normal if for every m the
[M43] We assume familiarity with the unexplained notions that follow. We leave the arithmetic hierarchy of Exercise 2.5.22 and consider hyperarithmetic sets. Define an infinite binary sequence to be hyperarithmetically random if it belongs to the intersection of all hyperarithmetic sets of measure
[M42] We abstract away from levels of significance and concentrate on the arithmetic structure of statistical tests. Statistical tests are just Π0 n null sets, for some n (Exercise 1.7.21 on page 46). The corresponding definition of randomness is defined as, “an infinite binary sequence is Π0
[37] Let μ be a computable measure on the sample space{0, 1}∞. Recall from Section 2.5 Martin-L¨of’s construction of a constructive μ-null set using a notion of sequential test V with associated critical regions V1 ⊇ V2 ⊇··· of measures μ(Vi) ≤ 2−i, for i ≥ 1. A
[36] (a) Consider an infinite sequence of zeros and ones generated by independent tosses of a coin with probability p (0 ,for some i, j ≥ h(m), for some suitable nondecreasing total computable function. Compare with the universal Bernoulli test of Exercise 2.4.4 on page 142. Hint for Item (c):
[21] (a) Show that none of the variants of algorithmic complexity, such as C(x), C(x|l(x)), and C(x; l(x)), is invariant with respect to cyclic shifts of the strings.(b) Show that all these variants coincide to within the logarithm of the minimum of all these measures.Comments. Hint: use the idea
[33] (a) Show that there exists an infinite binary sequence ωthat is random with respect to the uniform measure, but for each constant c there are only finitely many n such that C(ω1:n|n) > n − c (the condition of Theorem 2.5.6 does not hold).(b) Show that there exists an infinite binary
[35] Show that there is no Mises–Wald–Church stochastic sequence ω (with limiting frequency 1 2 ) and with C(ω1:n) = O(log n).Comments. This exercise was open in the second edition of this book, solved in [W. Merkle, J. Comput. Syst. Sci., 74:3(2008), 350–357]. Compare Exercise 2.5.16.
[43] Let A be the set of Mises–Wald–Church stochastic sequences (with p = 1 2 ). The admissible place-selection rules are the partial computable functions.(a) Show that there is an ω ∈ A such that for each unbounded, nondecreasing, total computable functionf, we have C(ω1:n; n) ≤ f(n) log
[30] Show that the following statements are equivalent for an infinite binary sequence ω: There exists a c such that for infinitely many n, possibly different in each statement, C(ω1:n|n) ≤ c, C(ω1:n; n) ≤ l(n) + c, C(ω1:n) ≤ l(n) + c.The sequences thus defined are called pararecursive
• [31] Show that the following statements are equivalent for an infinite binary sequence ω: For some constant c and infinitely many n, possibly different in each statement, C(ω1:n|n) ≥ n − c, C(ω1:n; n) ≥ n − c, C(ω1:n) ≥ n − c.Comments. Hint: Use Claim 2.5.1 and Exercise
[44] Show that every infinite sequence is Turing-reducible (Exercise 1.7.16 on page 43, with sets replaced by characteristic sequences of sets) to an infinite sequence that is Martin-L¨of random with respect to the uniform measure.Comments. C.H. Bennett raised the question whether every infinite
• [27] Prove Corollary 2.5.3 rigorously: ω = ω1ω2 ... is random in the sense of Martin-L¨of with respect to the uniform measure iff there exists a constant c such that C(ω1:n|n) ≥ n − K(n) − c for all n.Comments. Source: [P. G´acs, Z. Math. Logik Grundl. Math., 26(1980), 385–394],
[35] (a) Show that for every positive constant c there is a positive constant c such that {ω1:n : C(ω1:n; n) ≥ n − c}⊆{ω1:n :C(ω1:n|n) ≥ n − c}.(b) Use the observation in Item (a) to show that Theorem 2.5.5 holds for the uniform complexity measure C(·; l(·)).(c) Show that if f is
[39] Consider the Lebesgue measure λ on the set of intervals contained in [0, 1) defined by λ(Γy)=2−l(y). (Recall that for each finite binary string y the cylinder Γy is the set of all infinite strings ω starting with y.) Let ω be an infinite binary sequence such that for every computably
[35] Show that there exists an infinite binary sequence ω which is not random in the sense of Martin-L¨of with respect to any computable measure.Comments. Source: [A.K. Zvonkin and L.A. Levin, Russ. Math. Surveys, 25:6(1970), 83–124]. Hint: Use a computably enumerable set whose characteristic
[19] Show that there exists an infinite binary sequence ω and a constant c > 0 such that lim infn→∞ C(ω1:n|n) ≤c, but for any unbounded function f we have lim supn→∞ C(ω1:n|n) ≥ n − f(n).Comments. The oscillations can have amplitude Ω(n). Hint: Use the nstrings as defined
[19] Consider infinite binary sequences ω with respect to the uniform measure. Show that if f is a computable function and 2−f(n)converges rcomputably and C(ω1:n) ≥ n − c for some constant c and infinitely many n, then C(ω1:n) ≥ n − f(n) for all but finitely many n.Comments. This
[09] Consider infinite binary sequences ω with respect to the uniform measure. Show that with probability one there exists a constant c such that C(ω1:n|n) ≥ n − c for infinitely many n.Comments. Hint: Use Theorem 2.5.6, Item (ii), and Claim 2.5.1.Source:[P. Martin-L¨of, Ibid.].
Source: [P. MartinL¨of, Z. Wahrsch. Verw. Geb., 19(1971), 225–230].
[M19] Let f be such that 2−f(n) < ∞. Show that the set of infinite binary sequences ω satisfying C(ω1:n|n) ≥ n − f(n) for all but finitely many n has uniform measure 1.Comments. Hint: The number of y with l(y) = n such that C(y)
[23] Let ω be any infinite binary sequence. Show that for all constants c there are infinitely many m such that for all n with m ≤n ≤ 2m, C(ω1:n) ≤ n − c.Comments. We are guaranteed to find long complexity oscillations (of length m) in an infinite binary sequence ω relatively near the
[21] Let ω = ω1ω2 ... be any infinite binary sequence. Defineζ = ζ1ζ2 ... by ζi = ωi + ωi+1, i ≥ 1. This gives a sequence over the alphabet {0, 1, 2}. Show that ζ is not random in the sense of Martin-L¨of under the uniform measure (extend the definition from binary to ternary
[21] Consider {0, 1}∞ under the uniform measure. Let ω =ω1ω2 ... ∈ {0, 1}∞.(a) Show that if there is an infinite computable set I such that either for all i ∈ I we have ωi = 0 or for all i ∈ I we have ωi = 1, then ω is not random in the sense of Martin-L¨of.(b) Show that if the set
[13] Consider {0, 1}∞ under the uniform measure. Let ω =ω1ω2 ... ∈ {0, 1}∞ be random in the sense of Martin-L¨of.(a) Show that ζ = ωnωn+1 ... is Martin-L¨of random for each n.(b) Show that ζ = xω is Martin-L¨of random for each finite string x.Comments. Source: [C. Calude and I.
[36] (a) Consider a finite sequence of zeros and ones generated by independent tosses of a coin with probability p (0
[35] Let x be a finite binary sequence of length n with fj =x1 + x2 + ··· + xj for 1 ≤ j ≤ n. Show that there exists a constant c > 0 such that for all m ∈ N , all > 0, and all x, C(x|n, fn) > log n fn− log(m4) + c implies max m≤j≤n fj j − fn n < .Comments. This result
[23] Let x1x2 ...xn be a random sequence with C(x|n) ≥ n.(a) Use a Martin-L¨of test to show that x10x20 ... 0xn is not random with respect to the uniform distribution.(b) Use a Martin-L¨of test to show that the ternary sequence y1y2 ...yn with y1 = xn + x1 and yi = xi−1 + xi for 1 < i ≤ n
[20] For a binary string x of length n, let f(x) be the number of ones in x. Show that δ(x) = log(2n−1/2|f(x) − 1 2n|) is a P-test with P the uniform measure.Comments. Use Markov’s inequality to derive that for each positive λ, the probability of 2n−1/2|f(x) − 1 2n| > λ is at most
[M34] To investigate repeating patterns in the graph of C(x) we define the notion of a ‘shape match.’ Every function from the integers to the integers is a shape. A shape f matches the graph of C at j with span c if for all x with j −c ≤ x ≤ j +c we have C(x) = C(j) +f(x−j).(a) Show
[HM35] We want to show in some precise sense that the real line is computationally a fractal. (Actually, one is probably most interested in Item (a), which can be proved easily and elementarily from the following definition.) The required framework is as follows: Each infinite binary sequence ω =
Item (e) means that in contrast to the differences between the measures C(·; l(·)) and C(·|l(·))exposed by the contrast between Items (c) and (d), Item (b) holds also for C(·|l(·)). Items (f) and (g) show a complexity gap, because C(n) can be much lower than l(n). Hint for Item (h): use Item
• [35] Let ω be an infinite binary string. We call ω computable if there exists a computable function φ such that φ(i) = ωi for all i > 0.Prove the following:(a) If ω is computable, then there is a constant c such that for all n, C(ω1:n; n) < c, C(ω1:n|n) < c, C(ω1:n) − C(n) < c.This
[27] Let BB be a variant of the busy beaver function defined in Exercise 1.7.19 on page 45, where BB(n) is defined as the maximal number of steps in a halting computation of the reference universal Turing machine when started on an m-bit input with m ≤ n.Show that C(BB(n)) = n+O(log n). Use
[23] Let φ1, φ2,... be the effective enumeration of partial computable functions in Section 1.7. Define the uniform complexity of a finite string x of length n with respect to φ (occurring in the above enumeration) as Cφ(x; n) = min{l(p) : φ(m, p) = x1:m for all m ≤ n} if such a p exists,
[15] Let φ(t, x) be a computable function and limt→∞ φ(t, x) =C(x), for all x. For each t define ψt(x) = φ(t, x) for all x. Then C is the limit of the sequence of functions ψ1, ψ2,... . Show that for each error and all t there are infinitely many x such that ψt(x) − C(x) > .Comments.
[37] Consider Clim(x) = min{l(p) : p(n) = x for all but finitely many n} and Clim sup(x) = min{m : for all but finitely many n there exists a p with l(p) ≤ m and p(n) = x}. Let C(x) denote the plain Kolmogorov complexity relativized to 0 (that is, the program is allowed to ask an oracle whether
[31] Consider two complexity measures for infinite binary sequences ω. Let C∞(ω) be the minimal length of a program p such that p(n) = ω1:n for all sufficiently large n. Let Cˆ∞(ω) be defined as lim supn→∞ C(ω1:n|n). Prove that C∞(ω) ≤ 2Cˆ∞(ω) + O(1), and that this bound is
[27] Let x ∈ A, with d(A) < ∞. Then in Section 2.2 the randomness deficiency of x relative to A is defined as δ(x|A) = l(d(A))−C(x|A). (Here C(x|A) is defined as C(x|χ) with χ the characteristic sequence of A and l(χ) < ∞.) If δ(x|A) is large, this means that there is a description of
[18] Let A be the set of binary strings of length n. An element x in A is δ-random if δ(x|A) ≤ δ, where δ(x|A) = n − C(x|A) is the randomness deficiency. Show that if x ∈ B ⊆ A, then log d(A)d(B) − C(B|A) ≤ δ(x|A) + O(log n).Comments. That is, no random elements of A can belong to
[26] Show that there are strings x, y, z such that C(x|y) +C(x|z) > C(x) + C(x|y, z) + O(1). For convenience prove this first for strings of the same length n; but it also holds for some strings x, y, z with l(x) = log n and l(y) = l(z) = n. Comments. This is a counterintuitive result. Hint: Prove
[27] We consider how information about x can be dispersed.Let x ∈ N with l(x) = n and C(x) = n + O(1). Show that there are u, v, w ∈ N such that(i) l(u) = l(v) = l(w) = 1 2n, C(u) = C(v) = C(w) = 1 2n (+O(1)), and they are pairwise independent: C(y|z) = 1 2n + O(1) for y, z ∈ {u, v, w}and y
[12] A Turing machine T computes an infinite sequence ω if there is a program p such that T (p, n) = ω1:n for all n. Define C(ω) =min{l(p) : U(p, n) = ω1:n for all n}, or ∞ if such a p does not exist.Obviously, for all ω either C(ω) < ∞ or C(ω) = ∞.(a) Show that C(ω) < ∞ iff 0.ω is
[25] Prove that for each binary string x of length n there is a y equal to x except for one bit such that C(y|n) ≤ n − log n + O(1).Comments. Hint: The set of binary strings of length n constituting a Hamming code has 2n/n elements and is computable. Source: personal communication, I.
[14] We can extend the notion of c-incompressibility as follows(all strings are binary): Let g : N→N be unbounded. Call a string x of length n g-incompressible if C(x) ≥ n−g(n). Let I(n) be the number of strings x of length at most n that are g-incompressible. Show that limn→∞ I(n)/2n+1 =
[33] Let x be a binary string. Show that for any positive integer d the number of different descriptions of length C(x) + d of x is O(2d).Comments. Source: [G.J. Chaitin, Theoret. Comput. Sci., 2(1976), 45–48]. See also [R.G. Downey and D.R. Hirschfeldt, Algorithmic Randomness and Complexity,
[19] (a) Show that there is a constant d > 0 such that for every n there are at least 2n/d strings x of length n with C(x|n) ≥ n and C(x) ≥ n.(b) Show that there are constantsc, d > 0 such that for every large enough n there are at least 2n/d strings x of length n − c ≤ l(x) ≤ n
[14] In Example 2.2.5 we call x an n-string if x has length n and x = n00 ... 0.(a) Show that there is a constant c such that for all n, every n-string x has complexity C(x|n) ≤c. (Of course, c depends on the reference Turing machine U used to define C.)(b) Show there is a constant c such that
[23] Assume that the elements of {1,...,n} are uniformly distributed with probability 1/n. Compute the expected value of C(x) for 1 ≤ x ≤ n.Comments. Hint: All n strings of length at least 1 and at most log n have complexity at most log n + O(1)—the length of a unique shortest program. Hence
[21] Let x satisfy C(x) ≥ n − O(1), where n = l(x). Show that for all divisions x = yz we have n−log n−2 log log n ≤ C(y) +C(z) and for some divisions we have C(y) + C(z) ≤ n − log n + log log n.
[15] Let x satisfy C(x) ≥ n − O(1), where n = l(x).(a) Show that C(y), C(z) ≥ 1 2n − O(1) for x = yz and l(y) = l(z).(b) Show that C(y) ≥ n/3 − O(1) and C(z) ≥ 2n/3 − O(1) for x = yz and l(z)=2l(y).(c) Let x = x1 ...xlog n with l(xi) = n/ log n for all 1 ≤ i ≤ log n. Show that
[08] Prove the following continuity property of C(x). For all natural numbers x, y we have |C(x + y) − C(x)| ≤ 2l(y) + O(1).
[18] Define the function complexity of a function f : N→N , restricted to a finite domain D, as C(f|D) = min{l(p) : ∀x∈D[U(p, x) = f(x)]}.(a) Show that for all computable functionsf, there exists a constant cf such that for all finite D ⊆ N , we have C(f|D) ≤ cf .(b) Show that for all
[13] Let φ1, φ2,... be the standard enumeration of the partial computable functions, and let a be a fixed natural number such that the set A = {x : φk(y) =a, x for some y ∈N} is finite. Show that for each x in A we have C(x|a) ≤ l(d(A)) + 2l(k) + O(1).
[12] (a) Show that C(x + C(x)) ≤ C(x) + O(1).(b) Show that if m ≤ n, then m + C(m) ≤ n + C(n) + O(1).Comments. Hint for Item (a): if U(p) = x with l(p) = C(x), then p also suffices to reconstruct x + l(p). Hint for Item (b): use Item (a). Source:[P. G´acs, Ibid.], result attributed to C.P.
• [19] We investigate the invariance of C under change of program representations from 2-ary to r-ary representations. Let Ar ={0, 1,...,r−1}∗, r ≥ 2, and A = N ∗ with N the set of natural numbers.A function φ : Ar × A → A is called an r-ary decoder. In order not to hide too much
[12] Show that if φ is a fixed one-to-one and onto computable function φ : {0, 1}∗ → {0, 1}∗, then for every x ∈ {0, 1}∗, C(x) − C(x|φ(x)) = C(x) + O(1) = C(φ(x)) + O(1).
[12] Let x, y, z, and φk be as before. Prove the following:(a) C(x, y) ≤ C(x)+2l(C(x)) + C(y|x) + O(1).(b) C(φk(x, y)) ≤ C(x)+2l(C(x)) + C(y|x)+2l(k) + O(1) ≤ C(x) +2l(C(x)) + C(y)+2l(k) + O(1).
[23] Show that 2C(x, y, z) ≤ C(x, y)+C(x, z)+C(y, z)+O(log n)for all strings x, y, z with C(x), C(y), C(z) ≤ n Comments. Hint: use conditional Kolmogorov complexities.
[11] Show that if C(x) ≤ n and C(y) ≤ n then C(x, y) ≤ 2n +O(1).Comments. Source (also for Exercise 2.1.8): [A.K. Shen, V.A. Uspensky, and N.K. Vereshchagin, Kolmogorov Complexity and Algorithmic Randomness, American Mathematical Society, 2017]. Compare with Example 2.1.5 on page 109.
[14] Let φk be any partial computable function in the effective enumeration φ1, φ2,... . Let x, y, z be arbitrary elements of N . Prove the following:(a) C(φk(x)|y) ≤ C(x|y)+2l(k) + O(1).(b) C(y|φk(x)) ≥ C(y|x) − 2l(k) + O(1).Assume that φk is also one-to-one. Show that(c) |C(x) −
[07] Below, x, y, and z are arbitrary elements of N . Prove the following:(a) C(x|y) ≤ C(x) + O(1).(b) C(x|y) ≤ C(x, z|y) + O(1).(c) C(x|y, z) ≤ C(x|y) + O(1).(d) C(x, x) = C(x) + O(1).(e) C(x, y|z) = C(y, x|z) + O(1).(f) C(x|y, z) = C(x|z,y) + O(1).(g) C(x, y|x, z) = C(y|x, z) + O(1).(h)
[12] Prove that for every x, there is an additively optimal function φ0 (as in Theorem 2.1.1) such that Cφ0 (x) = 0. Prove the analogous statement for x under condition y.
[14] Show that there are infinite binary sequences ω such that the length of the shortest program for reference Turing machine U to compute the consecutive digits of ω one after another can be significantly shorter than the length of the shortest program to compute an initial n-length segment
[10] Let x be a finite binary string with C(x) = q. What is the complexity C(xq ), where xq denotes the concatenation of q copies of x?
[15] (a) Show that C(0n|n) ≤c, where c is a constant independent of n.(b) Show that C(π1:n|n) ≤c, where π = 3.1415 ... and c is some constant independent of n.(c) Show that we can expect C(a1:n|n) ≤ 1 4n, where ai is the ith bit in Shakespeare’s Romeo and Juliet.(d) What is C(a1:n|n),
[37] Give a universal Turing machine with d(A)d(Q) ≤ 35.Comments. Such a construction was first found by M. Minsky [Ann.Math., 74(1961), 437–455].
[25] Show that each such Turing machine with state set Q and tape alphabet A can be simulated by a Turing machine with state set Q, d(Q) = 2, and tape alphabet A such that d(A)d(Q) ≤ cd(A)d(Q), for some small positive constantc. Determinec. Show that the analogous simulation with d(Q) = 1
[20] Define Turing machines in quadruple format with arbitrarily large tape alphabets A, and state sets Q, d(A), d(Q) < ∞. Show that each such Turing machine with state set Q and tape alphabet A can be simulated by a Turing machine with tape alphabet A, d(A) = 2, and state set Q such that
[12] It is usual to allow Turing machines with arbitrarily large tape alphabets A (with the distinguished blank symbol B serving the analogous role as before). Use the quadruple formalism for Turing machines as defined earlier. How many Turing machines with m states and n tape symbols are there?
[32] Prove Lemma 1.11.1.Comments. The notion of sufficient statistic is due to R.A. Fisher [Philos.Trans. Royal Soc., London, Sec. A, 222(1922), 309–368]. The mutual information version is given in [T.M. Cover, J.A. Thomas, Elements of Information Theory, Wiley, 1991, pp. 36–38]. Hint: The
[22] We derive a lower bound on the minimal average codeword length of prefix-codes. Consider the standard correspondence between binary strings and integers as in Equation 1.3. Define f(n) =l(n) + l(l(n)) + ··· + 2. Show that n 2−f(n) = ∞.Comments. Hint: Let the number of terms in f(n),
Hint: Use Cauchy’s condensation test for convergence of series. Source: [K. Knopp, Infinite Sequences and Series, Dover, 1956]. Attributed to N.H. Abel.
[M30] We consider convergence of the series n 2−f(k,α;n)for f(k, α; n) = log n + log log n + ··· + α log(k) n, with log(k) the kfold iteration of the logarithmic function defined by log(1) n = log n and log(k) n = log log(k−1) n for k > 1.(a) Show that for each k ≥ 2, the series above
Show that ln > l∗(n)− 2 log∗ n for infinitely many n.(b) Show that log∗ n is unbounded and primitive computable. In particular, show that although log∗ n grows very slowly, it does not grow more slowly than any unbounded primitive computable function.Comments. Hint: use exercises in
In that notation it is a sort of inverse of f(3, x, 2).(a) Let l1, l2,... be any infinite integer sequence that satisfies the Kraft inequality, Theorem
[29] The function log∗ n denotes the number of times we can iterate taking the binary logarithm with a positive result, starting from n. This function grows extremely slowly. It is related to the Ackermann function of Exercise

Showing 700 - 800 of 3340

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Last

Step by Step Answers

Services

Sitemap
Fun
Definitions
Become Tutor
Used Textbooks
Study Help Categories
Recent Questions
Expert Questions
Campus Wear
Sell Your Books

Company Info

Security
Copyrights
Privacy Policy
Terms & Conditions
SolutionInn Fee
Scholarship
Online Quiz
Give Feedback, Get Rewards

Get In Touch

About Us
Contact Us
Career
Jobs
FAQ
Student Discount
Campus Ambassador

Secure Payment

Download Our App

© 2026 SolutionInn. All Rights Reserved