Quiz Solutions

1. A collection of 30,000 random characters would be far more complex, given that the characters are random and would require that every single character be specified if one wanted to reproduce all 30,000 in order. The CS research paper, however, contains words that follow certain rules. For example, each word ought to contain at least one vowel, and there should be spaces separating the words, and the words probably shouldn't be any longer than twenty letters or so. These rules reduce the complexity of the research paper, making it less complex.

2. The second thousand decimal digits would be more complex; in order to produce a string of the first thousand digits of sqrt(2), one only needs to calculate those thousand digits. However, in order to return the second thousand, one must still start at the beginning and calculate a full 2000 digits, then specify where to begin (i.e. digit 1000). Therefore, any program returning the second thousand digits would be longer.

3. Either proof from the lecture notes would suffice - equivalence to the halting problem, or proof by contradiction.