Question

In: Advanced Math

Compression of a bit string x of length n involves creating a program shorter than n...

Compression of a bit string x of length n involves creating a program shorter than n bits that returns

x. The Kolmogorov complexity of a string K(x) is the length of shortest program that returns x (i.e.

the length of a maximally compressed version of x).

(a) Explain why "the smallest positive integer not definable in under 100 characters" is paradoxical.

(b) Prove that for any length n, there must be at least one bit string that cannot be compressed to

fewer than n bits.

(c) Imagine you had the program K, which outputs the Kolmogorov complexity of string. Design

a program P that when given integer n outputs the bit string of length n with the highest

Kolmogorov complexity. If there are multiple strings with the highest complexity, output the

lexicographically first (i.e. the one that would come first in a dictionary).

(d) Suppose the program P you just wrote can be written in m bits. Show that P and by extension,

K, cannot exist, for a sufficiently large input n.

Solutions

Expert Solution

Colby Messinger answered 2 years ago
Next > < Previous

Related Solutions

Recall that a 5-bit string is a bit strings of length 5, and a bit string...
Recall that a 5-bit string is a bit strings of length 5, and a bit string of weight 3, say, is one with exactly three 1’s. a. How many 5-bit strings are there? b. How many 5-bit strings have weight 0? c. How many 5-bit strings have weight 1? d. How many 5-bit strings have weight 2? e. How many 5-bit strings have weight 4? f. How many 5-bit strings have weight 5? g. How many 5-bit strings have weight...
An n-bit binary string is a sequence of length n over the alphabet {0,1}. How many...
An n-bit binary string is a sequence of length n over the alphabet {0,1}. How many n-bit binary strings are there? How many n-bit binary strings b1,…,bn are there such that b1b2≠00? In other words, how many n-bit binary strings don't begin with 00? How many n-bit binary strings b1,…,bn are there such that b1b2≠00 and b2b3≠11? How many n-bit binary strings b1,…,bn are there such that b1b2≠00 and such that b2b3≠01?
When subjected to a force of compression, the length of a bone (compression Young's modulus 9.4 x 109 N/m2, tensile...
When subjected to a force of compression, the length of a bone (compression Young's modulus 9.4 x 109 N/m2, tensile Young's modulus 1.6 x 1010 N/m2) decreases by 2.7 x 10-5 m. When this same bone is subjected to a tensile force of the same magnitude, by how much does it stretch?Type your question here
Suppose that you pick a bit string from the set of all bit strings of length...
Suppose that you pick a bit string from the set of all bit strings of length ten. Find the probability that the bit string has exactly two 1s; the bit string begins and ends with 0; the bit string has the sum of its digits equal to seven; the bit string has more 0s than 1s; the bit string has exactly two 1s, given that the string begins with a 1.
Suppose that you pick a bit string from the set of all bit strings of length...
Suppose that you pick a bit string from the set of all bit strings of length ten. Find the probability that the bit string has exactly two 1s; the bit string begins and ends with 0; the bit string has the sum of its digits equal to seven; the bit string has more 0s than 1s; the bit string has exactly two 1s, given that the string begins with a 1.
A 99% CI on the difference between means will be (longer than/wider than/the same length as/shorter...
A 99% CI on the difference between means will be (longer than/wider than/the same length as/shorter than/narrower than )a 95% CI on the difference between means. In semiconductor manufacturing, wet chemical etching is often used to remove silicon from the backs of wafers prior to metalization. The etch rate is an important characteristic in this process and known to follow a normal distribution. Two different etching solutions have been compared, using two random samples of 10 wafers for each solution....
1. How many 12-bit strings (that is, bit strings of length 14) start with the sub-string...
1. How many 12-bit strings (that is, bit strings of length 14) start with the sub-string 011? 2. You break your piggy bank to discover lots of pennies and nickels. You start arranging them in rows of 6 coins. How many coins would you need to make all possible rows of 6 coins (not necessarily with equal numbers of pennies and nickels)? 3. How many shortest lattice paths start at (4, 4) and end at (13, 13)? 4. What is...
find a recurrence relation for the number of bit strings of length n that contain the...
find a recurrence relation for the number of bit strings of length n that contain the string 10. What are the initial conditions? How many bit strings of length eight contain the string 10
find a recurrence relation for the number of bit strings of length n that contain two...
find a recurrence relation for the number of bit strings of length n that contain two consecutive 1s. What are the initial conditions? How many bit strings of length eight contain two consecutive 1s
I want this code to be written in c++. Take a string of length n as...
I want this code to be written in c++. Take a string of length n as an input from the user such that n>=8 and only lower-case letters (a-z) are allowed as valid string characters. Deleting a letter from the string removes all the occurrences of that letter. The objective is to find the longest possible string such that it is left with only two unique letters and no two consecutive characters in a string are the same. If there...
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT