Things We Should Know: ---------------------- Rice's Thm: For any nontrivial property C, it is undecidable if a given TM M Whether L(M) is an element of C or not. A property is a collection of Recursively Enumerable languages. RE = Recognizable Recursive = Decidable Chapter 1 - Regular Languages ----------------------------- Definition 1.7 40 [ Regular Language ] Regular Language - A language is called a regular language if some finite automation recognizes it Theorem 1.12 45 The class of regular languages is closed under the union operation. Theorem 1.13 47 The class of regular languages is closed under the concatenation operation. Theorem 1.19 55 Every nondeterministic finite automation has an equivalent deterministic FSA. Corollary 1.20 56 A language is regular iff some nondeterministic finite automation recognizes it. Theorem 1.22 59 The class of regular languages is closed under the union operation. Theorem 1.23 60 The class of regular languages is closed under the concatenation operation. Theorem 1.24 62 The class of regular languages is closed under the star operation. Theorem 1.28 66 A language is regular iff some regular expression describes it. Lemma 1.29 66 If a language is described by a regular expression, then it is regular. Lemma 1.32 69 If a language is regular, then it is described by a regular expression. Theorem 1.37 78 Pumping lemma If A is a regular language, then there is a number p (the pumping length) where, if s is any string in A of length p, then s may be divided into three pieces, s=xyz, satisfying the following conditions: 1. for each i >= 0, xy^iz is an element of A, 2. the length of y is greater than zero 3. the length of xy is <= p. Chapter 2 - Context-Free Languages ---------------------------------- Definition 2.4 98 [ Ambiguous ] Ambiguous - A string w is derived ambiguously in a context-free grammar G if it has two or more different leftmost derivations. Grammar G is ambiguous if it generates some string ambiguously. Definition 2.5 99 [ Chomsky Normal Form ] Chomsky normal form - A context-free grammar is in Chomsky normal form if every rule is of the form A -> BC A -> a Where a is any terminal and A, B, and C are nay variables - except that B and C may not be the start variable. In addition we permit the rule that S -> (empty string), where S is the start variable Theorem 2.6 99 Any context-free language is generated by a context-free grammar in Chomsky normal form. Theorem 2.12 106 A language is context free iff some pushdown automation recognizes it. Theorem 2.19 115 Pumping lemma for context-free languages if A is a context-free language, then there is a number p (the pumping length) where, if s is any string in A of length at least p, then s may b divided into five pieces s = uvxyz satisfying the conditions: 1. For each i >= 0, uv^ixy^iz is an element of A, 2. The length of vy is greater than zero and 3. the length of vxy is <= p. Chapter 3 - The Church-Turing Thesis ------------------------------------ Definition 3.2 130 [ Turing-recognizable ] Call a language Turing-recognizable if some TM recognizes it. Definition 3.3 130 [ Turing-decidable ] Call a language Turing-decidable or simply decidable if some TM decides it. Theorem 3.8 137 Every multi-tape Turing machine has an equivalent single tape Turing machine. Corollary 3.9 138 A language is Turing-recognizable iff some multi-tape TM recognizes it. Theorem 3.10 138 Every nondeterministic Turing machine has an equivalent deterministic TM. Corollary 3.11 140 A language is Turing-recognizable iff some nondeterministic TM recognizes it. Corollary 3.12 140 A language is decidable iff some nondeterministic TM decides it. Theorem 3.13 141 A language is Turing-recognizable iff some enumerator enumerates it. Figure 3.9 143 [ Church-Turing Thesis ] Intuitive notion of algorithms = Turing machine algorithms Chapter 4 - Decidability ----------------------- Theorem 4.1 152 A(DFA) = { | B is a DFA that accepts input string w} A(DFA) is a decidable language Theorem 4.2 153 A(NFA) = {|B is an NFA that accepts input string w} A(NFA) is a decidable language Theorem 4.3 154 A(REX)={|R is a regular expression that generates string w} A(REX) is a decidable language Theorem 4.4 154 E(DFA) = {| A is a DFA and L(A)={empty set}} E(DFA) is a decidable language. Theorem 4.5 155 EQ(DFA) = {| A and B are DFAs and L(A) = L(B)} EQ(DFA) is a decidable language. Theorem 4.6 156 A(CFG) = {|G is a CFG that generates string w} A(CFG) is a decidable language Theorem 4.6 157 E(CFG) = { | G is a CFG and L(G) = {empty set}} E(CFG) is a decidable language. Theorem 4.8 158 Every context-free language is decidable. Theorem 4.9 159 A(TM) = {|M is a TM and M accepts w} A(TM) is undecidable. (proved on pg 165) Definition 4.12 161 [ Countable ] Countable - A set A is countable i either it is finite or it has the same size as N (There exists a mapping from N to A.) Definition 4.14 162 The set of Real numbers is uncountable. Corollary 4.15 164 Some languages are not Turing-recognizable. Definition 167 [ Co-Turing Recognizable ] We say that a language is co-Turing-recognizable if it is the compliment of a Turing-recognizable language Theorem 4.16 167 A language is decidable iff it is both Turing-recognizable and co-Turing-recognizable. Corollary 4.17 168 The compliment of A(TM) is not Turing-recognizable. Theorem 5.1 172 HALT(TM) = { | M is a TM and M halts on input w} HALT(TM) is undecidable Theorem 5.2 173 E(TM) = { | M is a TM and L(M) = {empty set}} E(TM) is undecidable Theorem 5.3 175 REGULAR(TM) = { | M is a TM and L(M) is a regular language} This person who goes by the name "REGULAR(TM)" is undecidable. Theorem 5.4 176 EQ(TM) = { | M1 and M2 are TMs and L(M1) = L(M2)} This language is, you guessed it, undecidable. Definition 5.5 176 [ Accepting Computation History ] Accepting computation history - Let M be a Turing machine and w an input string. An accepting computation history for M on w is a sequence of configurations, C1, C2,...,Cl, where C1 is the start configuration of M on w, Cl is an accepting configuration of M and each Ci legally follows from Ci-1 according to the rules of M. Definition 5.6 177 [ Linear Bounded Automaton ] Linear bounded automaton - is a restricted type of Turing machine wherein the tape head isn't permitted to move off the portion of the tape containing the input. If the machine tries to move its head off either end of the input, the head stays where it is, in the same way that the head will not move off the left-hand end of an ordinary TM's tape. Theorem 5.8 178 A(LBA) = { | M is an LBA that accepts string w}. A(LBA) is decidable Theorem 5.9 179 E(LBA) = { | M is an LBA where L(M) = {empty set}} E(LBA) is undecidable Theorem 5.10 181 ALL(CFG) = { | G is a CFG and L(G) = Sigma-star} ALL(CFG) is undecidable Theorem 5.11 184 PCP = {

| P is an instance of the Post correspondence problem with a match} PCP, a dangerous hallucinogen, is undecidable. PCP is covered in notes for 9/27/99 Definition 5.12 190 [ Computable Function ] A function f that maps Sigma-star to Sigma-star is a computable function if some Turing machine M, on every input w, halts with just f(w) on its tape. Definition 5.15 191 [ Mapping Reducible ] Language A is mapping reducible to language B, written A <=m B, if there is a computable function f that maps Sigma-* to Sigma-*, where for every w, w is a member of A iff f(w) is a member of B. Theorem 5.16 191 If A <=m B and B is decidable, then A is decidable Corollary 5.17 192 if A <=m B and A is undecidable, then B is undecidable. Theorem 5.22 193 If A <=m B and B is Turing-recognizable, then A is Turing-recognizable. Corollary 5.23 193 If A <=m B and A is not Turing-recognizable, then B is not Turing-recognizable. Theorem 5.24 194 EQ(TM) is neither Turing-recognizable nor co-Turing-recognizable. Chapter 6 - advanced topics in computability theory --------------------------------------------------- Lemma 6.1 198 There is a computable function q that maps E* to E*, where for any string w, q(w) is the description of a Turing machine P sub w that prints out w and then halts. Theorem 6.2 200 [ Recursion Theorem ] Let T be a Turing machine that computes a function t: E*xE* --> E*. There is a Turing machine R that computes a function r:E* --> E*, where for every w, r(w) = t(,w). Theorem 6.3 202 ATM is undecidable Definition 6.4 202 [ Minimal ] Minimal - If M is a Turing machine, then we say that the length of the description of M is the number of symbols in the string describing M. Say that M is minimal if there is no Turing machine equivalent to M that has a shorter description. Let MINtm = { | M is a minimal TM}. Theorem 6.6 203 Let t:E* --> E* be a computable function. Then there is a Turing machine F wherein t() describes a TM equivalent to F. Theorem 6.10 207 Th(N,+) is decidable. Theorem 6.11 209 Th(N,+,*) is undecidable. Lemma 6.12 209 Let M be a TM and w a string. We can construct from M and w a formula Phi(M,w) in the language of TH(N,+,*) that contains a single free variable x, whereby the sentence "there exists x Phi(M,w)" is true iff M accepts w. Theorem 6.13 210 The collection of provable statements in Th(N,+,*) is Turing-recognizable Theorem 6.14 210 Some true statement in Th(N,+,*) is not provable. 6.15 cannot type this crap Definition 6.16 211 [ Oracle ] Oracle - an oracle for a language B is an external device that is capable of reporting whether any string w is a member of B. An oracle Turing machine is a modified Turing machine that has the additional capability of querying an oracle. We write M^B to describe an oracle Turing machine that has an oracle for language B. Definition 6.18 212 [ Turing reducible ] Turing reducible - Language A is Turing reducible to language B, written A <=T B,if A is decidable relative to B. Theorem 6.19 212 If A <=T B and B is decidable, then A is decidable. Definition 6.20 215 Descriptive Complexity AND Minimal Description - Let x be a binary string. The minimal description of x,written d(x), is the shortest string where TM M on input w halts with x on its tape. If several such strings exist, select the lexicographically first among them. The descriptive complexity of x, written K(x), is K(x) = |d(x)| Theorem 6.21 215 There exists c for al x [K(x) <= |x| + c] This theorem says that the descriptive complexity of a string is at most a fixed constant more than its length. The constant is a universal one, not dependent on the string. Theorem 6.22 215 There exists c for all x [K(xx) <= K(x) + c]. Theorem 6.23 216 There exists c for all x,y [K(xy) <= 2K(x) + K(y) + c] Theorem 6.24 217 For any description language p, a fixed constant c exists that depends only on p, where for all x [K(x) <= KsubP(x) + c]. Definition 6.25 218 [ Compressible string ] Let x be a string. Say that x is c-compressible if K(x) <= |x| - c Theorem 6.26 218 Incompressible strings of every length exist. Theorem 6.27 218 At least 2^n - 2^(n-c+1) + 1 strings of length n are incompressible by c. Theorem 6.28 219 Let f be a computable property that holds for almost all strings. Then, for any b>0, the property f is FALSE on only finitely many strings that are incompressible by b. Theorem 6.29 220 For some constant b, for every string x, the minimal description d(x) of x is incompressible by b. Chapter 7 - Time Complexity --------------------------- Definition 7.1 226 [ Running time or Time Complexity ] Running time or Time Complexity - Let M be a deterministic Turing machine that halts on all inputs. The running time or time complexity of M is the function f:N-->N, where f(n) is the maximum number of steps that M uses on any input of length n. If f(n) is the running time of M, we say that M runs in time f(n) and that M is an f(n) time Turing machine. Definition 7.2 227 [ Upper bound AND Asymptotic upper bound ] Let f and g be two functions f, g: N --> R+. Say that f(n) = O(g(n)) if positive integers c and n0 exist so that for every integer n >= n0 f(n) <= cg(n) When f(n)=O(g(n)) we say that g(n) is an upper bound for f(n), or more precisely, that g(n) is an asymptotic upper bound for f(n), to emphasize that we are suppressing constant factors. Definition 7.5 228 I can't type this Definition 7.7 229 [ Time Complexity Class] Let t: N ---> N be a function. Define the time complexity class, TIME(t(n)), to be TIME(t(n)) = {L | L is a language decided by an O(t(n)) time TM}. Theorem 7.8 232 Let t(n) be a function, where t(n) >= n. Then every t(n) time multi-tape Turing machine has an equivalent O(t^2(n)) time single-tape Turing machine. Definition 7.9 233 [ Running Time ] Running Time - Let N be a nondeterministic Turing machine that is a decider. The running time of N is the function f:N-->N, where f(n) is the maximum number of steps that N uses on any branch of its computation on any input of length n, as shown in the following figure. (no figure). Theorem 7.10 233 Let t(n) be a function, where t(n)>=n. Then every t(n) time nondeterministic single-tape Turing machine has an equivalent 2^(O(t(n))) time deterministic single-tape Turing machine. Definition 7.11 235 [ P ] P - P is the class of languages that are decidable in polynomial time on a deterministic single-tape Turing machine. Theorem 7.12 237 PATH = { | G is a directed graph that has a directed path from s to t}. PATH is an element of P. Theorem 7.13 239 Two numbers are relatively prime if 1 is the largest int that divides them both. RELPRIME = { | x and y are relatively prime} RELPRIME is an element of P. Theorem 7.14 240 Every context-free language is a member of P. Definition 7.15 243 A verifier for a language A is an algorithm V, where A = { w | V accepts for some string c} Definition 7.16 243 NP is the class of languages that have polynomial time verifiers. Theorem 7.17 244 A language is in NP iff it is decided by some nondeterministic polynomial time Turing machine. Definition 7.18 245 NTIME(t(n)) = {L | L is a language decided by O(t(n)) time nondeterministic TM}. Theorem 7.20 246 The clique problem is to determine whether a graph contains a clique of a specified size. CLIQUE = { | G is an undirected graph with a k-clique} CLIQUE is in NP. Theorem 7.21 246 We have a collection of numbers, x1,...,xk and a target number t. We want to determine whether the collection contains a sub-collection that adds up to t. Thus SUBSET-SUM = { | S = {x1,...,xk} and for some {y1,...,yl} subset of {x1,...,xk}, we have the sum of the ys = t} SUBSET-SUM is in NP Theorem 7.22 249 SAT is an element of P iff P = NP. Definition 7.23 250 [ Polynomial Time computable ] Polynomial time computable - A function f:E*-->E* is a polynomial time computable function if some polynomial time Turing machine M exists that halts with just f(w) on its tape, when started on any input w. Definition 7.24 250 [ Polynomial Time mapping reducible ] Polynomial time mapping reducible - Language A is polynomial time mapping reducible, or simply polynomial time reducible, to language B, written A <=P B, if a polynomial time computable function f:E*->E*exists, where for every w, w is an element of A iff f(w) is in B Theorem 7.25 251 If A <=P B and B is in P, then a is in P. Theorem 7.26 251 3SAT is polynomial time reducible to CLIQUE Definition 7.27 253 [ NP - Complete ] A language B is NP-complete if it satisfies two conditions: 1: B is in NP, and 2: every A in NP is polynomial time reducible B. Theorem 7.28 253 If B is NP-complete and B is in P, then P = NP. Theorem 7.29 253 If B is NP-complete and B <=P C for C in NP, then C is NP-complete. Theorem 7.30 254 SAT is NP-complete Corollary 7.32 259 3SAT is NP-complete Corollary 7.33 260 CLIQUE is NP-complete Theorem 7.34 261 If G is an undirected graph, a vertex cover of G is a subset of the nodes where every edge of G touches on of those nodes. The vertex cover problem asks for the size of the smallest vertex cover. Let VERTEX-COVER = {|G is an undirected graph that has a k-node vertex cover} VERTEX-COVER is NP-complete Theorem 7.35 262 HAMPATH is NP-complete Theorem 7.36 268 UHAMPATH is the problem of trying to find a Hamiltonian path in an undirected graph. UHAMPATH is NP-complete. Theorem 7.37 268 SUBSET-SUM is NP-complete.