Description

Sundry
Before you start writing your final homework submission, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.)
1 Unprogrammable Programs
Prove whether the programs described below can exist or not.
(a) A program P(F,x,y) that returns true if the program F outputs y when given x as input (i.e. F(x)= y) and false otherwise.
(b) A program P that takes two programs F and G as arguments, and returns true if F and G halt on the same set of inputs (or false otherwise).
2 Computations on Programs
(a) Is it possible to write a program that takes a natural number n as input, and finds the shortest arithmetic formula which computes n? For the purpose of this question, a formula is a sequence consisting of some valid combination of (decimal) digits, standard binary operators (+, ×, the “^” operator that raises to a power), and parentheses. We define the length of a formula as the number of characters in the formula. Specifically, each operator, decimal digit, or parentheses counts as one character.
(Hint: Think about whether it’s possible to enumerate the set of possible arithmetic formulas. How would you know when to stop?)
(b) Now say you wish to write a program that, given a natural number input n, finds another program (e.g. in Java or C) which prints out n. The discovered program should have the minimum execution-time-plus-length of all the programs that print n. Execution time is measured by the number of CPU instructions executed, while “length” is the number of characters in the source code. Can this be done?
(Hint: Is it possible to tell whether a program halts on a given input within t steps? What can you say about the execution-time-plus-length of the program if you know that it does not halt within t steps?)
3 Kolmogorov Complexity
Compressing a bit string x of length n can be interpreted as the task of creating a program of fewer than n bits that returns x. The Kolmogorov complexity of a string K(x) is the length of an optimally-compressed copy of x; that is, K(x) is the length of shortest program that returns x.
(a) Explain why the notion of the “smallest positive integer that cannot be defined in under 280 characters” is paradoxical.
(b) Prove that for any length n, there is at least one string of bits that cannot be compressed to less than n bits.
(c) Say you have a program K that outputs the Kolmogorov complexity of any input string. Under the assumption that you can use such a program K as a subroutine, design another program P that takes an integer n as input, and outputs the length-n binary string with the highest Kolmogorov complexity. If there is more than one string with the highest complexity, output the one that comes first alphabetically.
(d) Let’s say you compile the program P you just wrote and get an m bit executable, for some m ∈ N (i.e. the program P can be represented in m bits). Prove that the program P (and consequently the program K) cannot exist.
(Hint: Consider what happens when P is given a very large input n.)
4 Five Up
Say you toss a coin five times, and record the outcomes. For the three questions below, you can assume that order matters in the outcome, and that the probability of heads is some p in 0 < p < 1, but not that the coin is fair (p = 0.5).
(a) What is the size of the sample space, |Ω|?
(b) How many elements of Ω have exactly three heads?
(c) How many elements of Ω have three or more heads?
(Hint: Argue by symmetry.)
For the next three questions, you can assume that the coin is fair (i.e. heads comes up with p = 0.5, and tails otherwise).
(d) What is the probability that you will observe the sequence HHHTT? What about HHHHT?
(e) What is the chance of observing at least one head?
(f) What about the chance of observing three or more heads?
For the final three questions, you can instead assume the coin is biased so that it comes up heads with probability p = .
(g) What is the chance of observing the outcome HHHTT? What about HHHHT?
(h) What about the chance of at least one head?
(i) What about the chance of ≥ 3 heads?
5 Ball-and-Bin Counting Problems
Say you have 5 bins, and randomly throw 7 balls into them.
1. What is the probability that the first bin has precisely 3 balls in it?
2. What is the probability that the third bin has at least 3 balls in it?
3. What is the probability that at least one of the bins has precisely 3 balls in it?
6 Monty Hall’s Revenge
(a) There are n doors for some n > 2. One has a car behind it, and the remaining n−1 have goats. As in the ordinary Monty Hall problem, Monty will reveal one door with a goat behind it after you make your first selection. How would switching affect the odds that you select the car?
(Hint: Think about the size of the sample space for the experiment where you always switch. How many of those outcomes are favorable?)
(b) Again there are n > 2 doors, one with a car and n−1 with goats, but this time Monty will reveal n−2 doors with goats behind them instead of just one. How does switching affect the odds of winning in this modified scenario?
(c) Finally, imagine there are k<n−1 cars and n−k goats behind the n> 2 doors. After you make your first pick, Monty will reveal j < n−k doors with goats. What values of j,k maximize the relative improvement in your odds of winning if you choose to switch? (i.e. what j,k maximizes the ratio between your odds of winning when you switch, and your odds of winning when you do not switch?)