CPSC 421/501: Skeletal notes of what will be covered in class. ------------------------------------------------------ Sept 9 (What we actually did): Discussed self-referential statements like: - This is a lie. - The smallest positive integer not described by a sentence of fifty words or fewer. - Let S be the set of all sets that don't contain themselves. (Russell's paradox) Sept 11: - Standard resolution of Russell's paradox - Pidgeon Hole Principle, i.e., Drawers Principle, i.e., TV Principle (if a house has 15 TV's and 16 people watching TV, then at least two people are watching the same TV). "Strings" over the "alphabet" A = {a,b,c} is the set A^* = A^0 union A^1 union A^2 ... where A^k is the set of strings of length k over A. C Program = special type of ASCII string, Python Program = special type of ASCII string, Java Program = special type of ASCII string, etc. So { C Programs } is countable Some strings over {1,2,...,8,9,0} are primes. So PRIMES is a subset of the set of strings over {1,2,...,8,9,0}. A "language" is a subset of the set of all words over an alphabet (think of English, French, etc.) Claim: The set of C programs is countable, whereas the set of languages over {1,2,...,9,0} is uncountable (bigger than countable). -------- - Theorem: For any set S, |S| < |PowerSet(S)|. Proof: Otherwise there would be an f : S --> PowerSet(S) such that each PowerSet occurs in the image. Now let T = { s in S such that s not in f(s) } . Then T is a subset of S, and hence T = f(t) for some t in S. Claim: t in T is impossible, but t not it T is also impossible. Corollary: if N = { 1,2,3,... } then PowerSet(N) is not countable (i.e., is "bigger" than infinitely countable. Sept 14: Sept 16: ------------------------------------------------------ ------------------------------------------------------- THIS PLAN IS TENTATIVE: MATERIAL WILL BE ADDED AND MODIFIED. -------------------------------------------------------- September 9-16 or so: Paradoxes, Counting in Sections 1-4 of "Uncomputability and Self-Referencing in CPSC 421." The main point of this article is to discuss two subtle ideas in this course, used to prove that certain problems "cannot be solved": namely (1) counting arguments, and (2) specific problems which--in a sense--involve self-referencing. We will cover the rest of this article AFTER we cover Section 4.2 of Sipser's textbook Remarks on the handout "Uncomputability and Self-Referencing in CPSC 421": * Sections 1 and 2 describe some very general "paradoxes," and not all "paradoxes" listed there are true paradoxes. * Section 3 is very easy (regarding finite sets), but is really a warm-up for Section 4 (regarding countable and uncoutable infinite sets). * The rest of the article deals with the Halting Problem and uncomputability in a number of contexts. Most first courses in computation theory (in my humble opinion) do this too quickly, so that the fundamental ideas are not well understood. In particular, the Halting Problem can be stated for C programs, Java programs, Turing Machines, RAMs (Random-Access Machines), etc. List paradoxes in handout. Give example of making things precise. We typically use languages to describe any yes/no 0/1 true/false question, a subset of strings/words over an alphabet. * Introduce Sigma, Simga^*, empty string, etc. * Give examples of how to make "paradoxes" precise, when they lead to a real paradox, when they don't * Embark on making some of them precise. General Counting * The rational numbers are countable, the real numbers uncountable (see Sipser 4.2). * The set of strings over a finite alphabet is countable. * The set of languages over a non-empty alphabet is uncountable. * The set of subsets of a countable set is not countable. Generally, set of subsets of a set, S, cannot be put into 1-1 correspondence with S. Proof: if f:S->P(S), let T={s s.t. f(s) does not contain s}. Contradiction (similar to Russell's Paradox and to diagonalization). ---------------------------------------------------------------- Specifics: September 9: Some paradoxes (they are all self-referential): (2) This statement is a lie. (3) This sentence referes to the smallest positive integer not defined by a sentence of thirty words or fewer. (6) Let S = "The set of all sets that don't contain themselves". Does S contain itself? (7) "This is a C progrma that takes a string, s, as input and (i) loops infinitely if s is a valid C program that halts on input s, and (ii) halt otherwise." How does this program behave on its own input? OR (7') Can you input a computer program "to itself"? Sometimes paradoxes give theorems, sometimes they are resolved by telling you what you can't allow yourself to do, etc. ------------- Self-referencing occurs--in a sense--in "diagonalization arguments." Define two types of infinities: "countably infinite" and "uncountably infinite". Def: A set, S, is **countable** if there is a sequence of elements of S, s1, s2, s3, ... such that each element of S appears in this sequence at least once. Remark 1: Any finite set is countable: e.g., S = {1,3,4}, then the sequence 1,3,4,4,4,4,... is a sequence in S that contains each element of S. Remark 2: The rational numbers are countable: consider the following lists: List 1: 0 List 2: 1/1, -1/1 List 3: 2/1, -2/1, 1/2, -1/2 List 4: 3/1, -3/1, 2/2, -2/2, 1/3, -1/3 etc. The lists in order give a sequence: 0, 1/1, -1/1, 2/1, -2/1, 1/2, -1/2, ... such that any rational number occurs at least one in this sequence. Theorem: The real numbers are uncountable (i.e., not countable). Two proofs (very similar). The first proof is like that in Sipser 4.2: First proof: If r1, r2, r3, ... is any sequence of reals, let r be real such that the i-th digit to the right of the decimal point disagrees with ri (and doesn't equal 9 or 0, to avoid problems such as 3.2699999... = 3.270000... ) If you draw a picture, you read off the digits of r from the "diagonal". Second proof: This requires an important lemma. Lemma: Let S be a set. Then Power(S), the set of all subsets of S, is "larger" than S, i.e., there is no map f : S -> Power(S) such that the image of f is all of Power(S). Proof: Assume (for the sake of contradiction) that such an f exists. Let T = { s in S such that s is not in f(s) }. Can there exist a t in S such that f(t) = T ? No: get contradiction. You can actually see this proof in action. For example, let S = { 1,2,3 }, and let f : S -> Power(S) be given by f(1) = {1,3}, f(2)= {1,2,3}, f(3)={1} . Then T = { 3 }. But now we claim that for t=1,2,or 3, f(t) cannot equal T. Second proof: To each subset, S, of {1,2,3,...} define r(S) = sum_{s in S} 1/(10)^s. Then r : Power({1,2,3,...}) -> reals is injective (i.e., two distinct subsets are taken to distinct real numbers. "Hence" (see class discussion) the real numbers are at least as "large in cardinality" than Power({1,2,3,...}); but this power set is uncountable. Hence the reals are uncountable. The term "Hence" is really the following lemma: Lemma: Let A be uncountable, and let r : A -> B be an injective map (i.e., r takes distinct elements of A to distinct elements of B). Then B is uncountable.