CSC 341: April 23, 2007
From CSWiki
Notes for the class session
We started off the class with a look at Turing reducibility, where Theorem 6.20 states that Language A is Turing reducible to language B, written 
, if A is decidable relative to B. (This works in the same sense that mapping reducibility 
does. An example of this that came up was that 
is Turing reducible to 
.
The focus of the lecture for today was compressibility and incompressibility. The information content of event P is 0 − log2(P). So P has a higher information content if it's harder to guess the value of P. (10101010101 has less information content than 01110010000 because it's easier to guess the digits of the first than the digits of the second.) So it might be more practical to write the input 900 and the TM to write x copies of the string "01" than to simply write out a string of 1800 characters. It might be important to note, however, that the encoding for the smallest TM, a TM that always fails is ({q0, q1}, {}, {}, q0, q0, q1). I believe we also derived the number representing this TM in recursive function notation, but I didn't write any of that down.
A minimal length description for a string ω is the smallest representation of an input and a TM that outputs string ω. (This works intuitively in the same way that writing 
is easier than writing 18446744073709551616, although they both represent the same value. In this case 2 and 64 are inputs to what can be thought of as a mental Turing machine, represented by the exponent, that takes 64 copies of 2 and multiplies them all together. If remembering all that is easier than remembering "18446744073709551616" then we know that "18446744073709551616" is not a minimal length description.)
Finally, we noted that finding a minimal length string for a complex string is not in general feasible.
Study questions
- What is the minimal description of
?
- Suppose that we encode Turing machines as bitstrings by writing them out as tuples in ordinary mathematical notation (as in the textbook) and then taking the UTF-8 encoding of the strings that we write. Suppose further that we then encode descriptions, as described on page 235 of the textbook, by doubling every bit of the Turing machine's encoding, appending the delimiter 01 and appending the binary-encoded input string after that. What then is the descriptive complexity of ?
- Prove that there is a positive integer c such that, for every string x,
.
Proposed Solutions
-
-
-
We can build a Turing machine T that on input <M, w>, runs M with input w and outputs the reverse what's on the tape when M halts. Then <T, d(x)> is a description of the reverse of x, where d(x) is a minimal description of x. Therefore, the length of the minimal description of the reverse of x exceeds the length of the minimal description of x by no more than the length of a description, <T> of T, plus the extra characters required to separate T from d(x), which have length approximately log |<T>|.
