### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# THEORY OF COMPUTATION CSCE 551

GPA 3.61

### View Full Document

## 20

## 0

## Popular in Course

## Popular in Computer Science and Engineering

This 111 page Class Notes was uploaded by Trace Mante MD on Monday October 26, 2015. The Class Notes belongs to CSCE 551 at University of South Carolina - Columbia taught by Staff in Fall. Since its upload, it has received 20 views. For similar materials see /class/229596/csce-551-university-of-south-carolina-columbia in Computer Science and Engineering at University of South Carolina - Columbia.

## Reviews for THEORY OF COMPUTATION

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/26/15

Theory of Computation Lecture 17 Time Complexity Max Alekseyev University of South Carolina April 7 2009 Running Time Previously we were interested in whether a TM ever takes a finite or infinte amount of steps to compute Depending on that we classified TMs into deciders and recognizers From now on we will be interested in more detailed running time analysis of deciders that halt on any input Running Time Previously we were interested in whether a TM ever takes a finite or infinte amount of steps to compute Depending on that we classified TMs into deciders and recognizers From now on we will be interested in more detailed running time analysis of deciders that halt on any input Definition A running time or time complexity in a worst case of a decider M for some language is a function f N a N where fn is the maximum number of steps that M uses on any input of length n If fn is a running time of a TM M or an algorithm we say that M runs in time fn and that M is an fn time TM Asymptotic Analysis gt Often the exact running time of an algorithm is a complex expression V The exact running time may depends on minor inessential details such as a precise definition of a TM while there are many different but equivalent definitions of a TM gt In most cases to determine whether an algorithm is fast or to compare it to other algorithms it is enough to knowjust the highest order term of its time complexity gt As the size of input grows the contribution of the lower order terms in the running time becomes negligible as compared to the highest order term V Finding the highest order term of an algorithm39s time complexity is called asymptotic analysis Highest Order Term Informally speaking the highest order term of a function fn is a term that grows with n most quickly as compared to the other terms For example the function fn 6n3 2n2 20n 45 has four terms and the highest order term is 6n3 Asymptotic U pper Bound Definition Let f and g be functions g N H724 We say that if there exist positive constants c and no such that for every integer n 2 no fn cgn When fn Ogn we say that gn is an asymptotic upper bound for fn Note that the big O notation can suppress any constant factors For fn 6n3 l 2n2 l 20n l 45 we can say fn 06n3 as well as fn On3 due to the following bound fn 6n3 2n2 20n 45 6n3 2n3 2073 4573 7373 Examples Usually for logarithms we need to specify a base such as logz n But since for any fixed base b gt 1 there is an identity log2 n we can write log2 n Ologb n or simply logz n Olog n as the base of logarithm does not matter Q Why the inequality b gt1 is important Examples Usually for logarithms we need to specify a base such as logz n But since for any fixed base b gt 1 there is an identity log2 n we can write log2 n Ologb n or simply logz n Olog n as the base of logarithm does not matter Q Why the inequality b gt1 is important logz logz n Olog log n because for any base b gt 1 log2 log2 n log2 log2 logb n 7 log2 logb2 7 log2 logb2 OIogb Iogb n Similarly log n Olog2 n and nl g2 nol g provel However nl g2 7 Onl g Examples Usually for logarithms we need to specify a base such as logz n But since for any fixed base b gt 1 there is an identity log2 n we can write log2 n Ologb n or simply logz n Olog n as the base of logarithm does not matter Q Why the inequality b gt1 is important logz logz n Olog log n because for any base b gt 1 log2 log2 n log2 log2 logb n 7 log2 logb2 7 log2 logb2 OIogb Iogb n Similarly log n Olog2 n and nl g2 nol g provel However nl g2 7 Onl g The upper bound is not uniquely defined for example we can say log n Olog2 n or log n On or log n On log n or log n On100 whichever is the most suitable for our needs Polynomial vs Exponential Bounds We will distinguigh between algorithms with polynomial running time of the form n6 which is the same as now or 200 g from algorithms with exponential running time of the form 2 Polynomial vs Exponential Bounds We will distinguigh between algorithms with polynomial running time of the form n6 which is the same as now or 200 g from algorithms with exponential running time of the form 2 Often we will deal with integer inputs and outputs written in the binary form ie over the alphabet 07 The length n of a binary represention of an integer m is bounded by n 1log2 m Olog m Note that the running time is always viewed as a function of the length of the input In terms of an input In if it is an integer running time is polynomial if it is log mo1 but not mow the latter may be exponential in log m Small o Notation Definition Let f and g be functions g N H724 We say that quot39me m 0 In other words fn ogn means that for any real number 6 gt 0 there exists a number no such that for every integer n 2 no fn lt cgn While the big O notation says that one function is asymptotically not greater than the other the small o notation says that one function is asymptotically smaller than the other Further Examples om n onogog n n log log n on log n n log n 0n2 n2 0n3 fn is never ofn VVVVVV Complexity Classes Definition Let t N a 72 be a function The time complexity class TIMEtn is a collection of all languages that decidable by an Otn time TM The elements of the class TIMEn have linear time complexity TIMElog log n C TIMElog n C TIMEn C TIMEnloglog n C C TIMEnlog n C TIMEn2 C TIMEn2 log n Complexity in Other Models Theorem Let tn be a function such that tn 2 n Then every tn time multitape TM has an equivalent Ot2n time single tape TM see Sipser Theorem 78 p 254 Theorem Let tn be a function such that tn 2 n Then every tn time nondeterministic single tape TM has an equivalent 20mm time deterministic single tape TM see Sipser Theorem 711 p 256 Theory of Computation Lecture 18 Classes P and NP Max Alekseyev University of South Carolina April 14 2009 Polynomial vs Exponential Running Time We distinguish between algorithms with polynomial running time of the form nc which is the same as now or 200 g r0 from algorithms with exponential running time of the form 2 5 where c and 6 are positive constants Any exponential function fn grows faster than any polynomial function gn so that for all large n fn is much greater than gn For example if fn 2 and gn n3 we may have fn lt gn for small n eg n 2 but for large n such as n 1000 the value of fn becomes extremely large while the value ofgn grows moderately If 2 and n3 are the running time of two algorithm for the size of input n 1000 we could execute the latter but not the former one Polynomial vs Exponential Running Time We distinguish between algorithms with polynomial running time of the form nc which is the same as now or 200 g r0 from algorithms with exponential running time of the form 2 5 where c and 6 are positive constants Any exponential function fn grows faster than any polynomial function gn so that for all large n fn is much greater than gn For example if fn 2 and gn n3 we may have fn lt gn for small n eg n 2 but for large n such as n 1000 the value of fn becomes extremely large while the value ofgn grows moderately If 2 and n3 are the running time of two algorithm for the size of input n 1000 we could execute the latter but not the former one We view algorithms with polynomial running time as practical while algorithms with exponential running time as intractable Exhaustive Search Algorithms A typical example of algorithms with exponential running time are given by the exhaustive search or brute force search that explore a space of all possible solutions whose amount is often exponential in the size of the input Exhaustive Search Algorithms A typical example of algorithms with exponential running time are given by the exhaustive search or brute force search that explore a space of all possible solutions whose amount is often exponential in the size of the input For example checking whether a given positive integer m of length roughly n z logz m is prime can be done by going over all integers from 2 to m 71 and checking whether either of them is a divisor of m If no divisor found In is declared prime while if a divisor is found In is declared composite In the worst case when m is indeed prime the running time of this algorithm would be proportional to m z 2 which is exponential in n Exhaustive Search Algorithms However existence of an exponential time algorithm does not mean that the problem cannot be solved in polynomial time Usually designing a polynomial time algorithm requires deeper understanding of the problem In particular for a number of decades it was not known whether it is possible to solve the primality testing problem in polynomial time This uncertainty was resolved only in 2002 by Agrawal Kayal and Saxena who gave first polynomial time algorithms for primality testing now called AKS test Why polynomial An algorithm is usually supposed to read its input Hence the minimal complexity of a non trivial algorithm is proportional to n where n is the length of the input We often combine existing algorithms eg use them as subroutines to get new ones Q What would be the minimal complexity class containing all algorithms constructed this way Properties of Polynomials Let fm and gm be polynomials in variable In Then each of the following functions is also a polynomial 1 fx gx 2 x an 3 fgX In other words the class of polynomials is closed under addition subtraction multiplication and composition Properties of Polynomials Let fm and gm be polynomials in variable In Then each of the following functions is also a polynomial 1 fx gx 2 x an 3 fgX In other words the class of polynomials is closed under addition subtraction multiplication and composition Q Suppose that deg fm p and deggm q What would be the degree of fx gx fx gx and fgx 7 Complexity Classes Definition Let t N a 72 be a function The time complexity class TIMEtn is a collection of all languages that decidable by an Otn time TM The elements of the class TIMEn have linear time complexity TIMElog log n C TIMElog n C TIMEn C TIMEnloglog n C C TIMEnlog n C TIMEn2 C TIMEn2 log n The class P From now on we will be interested in principal possibility to solve problems in polynomial time Namely we will try to determine whether a given language can be decided in polynomial time If so we will say that this language belongs to the class P Definition P is the class of languages that are decidable in polynomial time on a deterministic singletape Turing machine In other words P U TIMEnquot k0 The class P plays a central role in theory of computation since gt P is invariant for all reasonable models of deterministic computations gt P roughly corresponds to the class of problems that can be realistically solved on a computer CSCE 551 Course Notes Stephen A Fenner April 25 2008 1 1142008 Course website http www cse sc eduquotfennercsceSSlindex html 11 Automata Computability Complexity Complexity Why are problems easy Hard Computability What problems are solvable Solvable vs insolvable An initial motiviation early 1900s Given a mathematical statement is it true ls this solvable via algorithmic com putation Framework for classifying problems by their di iculty Time eg cryptography and space Automata automate is plural for automaton This is a simple formal mathematical model of a computational device that can do rudimentary but still useful pattern matching in a string It is good formal practice for dealing with real models 12 Mathematical Preliminiaries A set is a collection of things the members or elements of the set Sometimes we can describe a set just by listing its members separated by commas and enclosed in braces squiggly brackets For example the statement S 7 1519 says that S is a set containing exactly three members the numbers 7 15 and 19 The statement implies for example that 7 E S the E relation means is a member of and that 10 S the relation means is not a member of Although a set may contain objects it itself is a single object that is necessarily distinct from its members This means for example that sets can be elements of other sets The set 1 5 2 4 9 10 15 17 has exactly three members namely 15 2 and 49 10 15 17 Each of these members is itself a set of numbers A set is determined entirely by its members ie which objects are elements of the set This principle is called the Axiom of Extensionality and its precise statement is If A and B are sets such that for all z z E A ltgt z E B then A B That is two sets are equal if they have exactly the same members The order that elements are listed in a set does not matter neither does it matter that an element is listed more than once duplicates Thus 7 15 19 157 19 1977 157 The set with no members is called the empty set and is denoted either by or by 0 Note that we can say the empty set instead of just an empty set because by Extensionality there can only be one empty set In some situations when we list elements we do want duplicates to matter but still not order These things are called multisets or bugs Eg 7157 715 as sets but 7 157 7 715 as multisets Let A and B be sets We say that A Q B read A is a subset of B iff if and only if every element of A is also an element of B Thus 719 Q 7 1519 but 719 3 715 If A B then clearly A Q B and B Q A The converse holds by Extensionality If A Q B and B Q A then A B S0 A B if and only if A Q B and B Q A This is the most useful way to show that two sets are equal show that each is a subset of the other Note that Q Q A for any set A We say that A C B read A is a proper subset of B to mean that A Q B but A 7 B ie every element of A is an element of B but there is at least one element of B that is not an element of A Note iff means if and only if Natural numbers The Sipser book de nes the natural numbers to be N 123 as is common practice in mainstream mathematics especially algebra and number theory I and most of my colleagues in Computer Science Logic and Set Theory de ne the natural numbers as N w 0 1 2 that is the same as N but including zero Because of the potential confusion I will try to avoid the term natural number altogether and instead use the term positive integer to refer to an arbitrary element ofN and nonnegative integer to refer to an arbitrary element of N Some people use the term whole number to mean positive integer The integers are de ned as Z7271012 Sets given by rules The list of members approach to describing a set is getting unwieldy especially for large or in nite sets An alternative way to de ne a set is by giving some criterion for membership in the set 71 l rule about 71 or n rule about 71 where rule about 71 is some statement whose truth or falsehood may depend on the value of n The set described this way contains as members exactly those 71 that satisfy the rule ie those 71 for which the rule is true You can read it literally as the set of all n such that rule about 71 For example 71 l n is an even integer 7472024 de nes the set of n such that n is an even integer ie the set of all even integers Sometimes for shorthand we include part of the rule to the left of the vertical bar The expression 71 E Z l n is even also describes the set of all even integers You can read it literally as the set of all integers n such that n is even77 Another variation is to give some expression to the left of the bar that denotes some object and to the right of the bar put some rule regarding the components of the expression Thus 2n l n is an integer literally the set of all things of the form 2n where n is an integer also denotes the set of all even integers Every set can be given in a rule based form For example 71519nln7Vn15Vn19 where V77 means inclusive OR 121 Operations on Sets Let A and B be sets A U B read A union B77 or the union of A and B is the set of all things that are either in A or in B or both A O B read A intersect B77 or the intersection of A and B is the set of all things common to A and B ie things that are both elements of A and elements of B 71519LJ71921 7151921 71519rw71921 719 Venn diagram of A U B and A B A 7 B read the complement of B in A77 or the relative complement of B with respect to A also denoted AB is the set of all things that are in A but not in B Venn diagram For any set A the powerset of A denoted 73A is the set of all subsets ofA That is an object 2 is a member of73A just in case that 2 Q A For example 7317 273 S l S g 17 273 07 17 27 37 17 27 1737 27 37 17 27 Sequences A sequence is a list of things In a sequence both order and duplicates matter We can give a sequence by listing its elements surrounded by parentheses 7191520H Two sequences are equal only if they have the same length and each element of one sequence is equal to the element in the same position in the other sequence A nite sequence is called a tuple A sequence with k elements is a k tuple A 3 tuple is also called a triple and a 2 tuple is also called a pair or ordered pair Note zy yz only if m y Cartesian product For sets A and B we de ne AXBmylm AAyEB where A means AND Alternatively 7 p is a pair whose rst element is in A and A X B 7 p whose second element is in B The cardinality of a set A denoted lAl is the number of elements in A the size of A Fact lA x Bl lAl B for sets A and B For sets A1 A2 Ak we can de ne the Cartesian product A1 x A2 x x Ak to be the set of all k tuples 11012 ak where a 6 Ai for all 1 g1 k Also AkAxAxxA k times More general unions and intersections If X is a set of sets then UX 2 l 3A 6 Xz 6 Al is the union of all elements of X If X 7 0 then we can also de ne OX 2 l VA 6 Xz E A which is the intersection of all elements of X For example if X 6 4 67 2 3 6 then UX 234 67 OX 6 2 1162008 3 1232008 31 More Mathematical Preliminaries I m assuming you ve picked up on the following 0 Graphs undirected graphs 7 vertices nodes edges arcs 7 incidence adjacency neighbors 7 degree labeled graph 7 path simple path connected graph cycle simple cycle 7 acyclic graph 7 tree leaf root Digraphs directed graphs 7 indegree outdegree directed path 7 strongly connected directed paths in both directions 0 Strings and languages 7 alphabet any nite set members are symbols 7 string over an alphabet 7 av is concatenation of strings u and v 7 length of w is denoted lwl empty string is 6 identity under concatenation reverse of w is w 7 substring 7 lexicographic ordering is length rst then dictionary order between strings of the same length 7 language set of strings over a given alphabet o Boolean logic 7 Boolean values true and false 1 true and 0 false 7 Boolean operations conjunction and A disjunction or V negation not exclu sive or xor 69 7 book equality lt gt me and others equivalence biconditional 7 book implication 7 me and others conditional 7 operands 7 Both A o and V o are complete set of Boolean connectives 7 distributive laws 32 De nitions theorems and proofs and lemmas corollaries A formal proof of statement S is a sequence of mathematical statements written in a rigorously de ned syntax such that each statement is either an axiom or follows from some previous statements in the sequence by a rule ofinference and whose last statement is S S is then considered a theorem 0 The syntax speci cation is a formal language 0 The speci cation of axioms and rules of inference is a formal system The idea is that at least in principle a proof can be checked for correctness by a computer using a purely algorithmic procedure based solely on the proofs syntactical form without regard to its meaning Formal proofs even of simple theorems are almost always long and dif cult for a human to read and digest therefore they almost never appear in the mathematical literature lnstead what appear are informally written but still rigorous proofs Such an informal proof is written basically as prose7 but may include mathematical formulas It is a piece of rhetoric meant to convince the mathematically intelligent reader beyond any doubt that the proposed assertion is true a theorem7 that is7 that a formal proof exists The informal proof can appeal to previous theorems It can also appeal to the reader s mathematical understanding and intuition In this case7 the prover must be prepared to explain or ll in77 more formally these appeals if challenged to do so Writing a proof is more of an art than a mechanical exercise It contains elements of style7 as with any good writing The best way to learn to write good proofs is to read good proofs that others have written 321 Proof methods construction contradiction induction Theorem 31 There are real irrational numbers a7 1 gt 0 such that a17 is rational Proof We know that is irrational lf is rational we are done set a b Otherwise7 is irrational Set a and b Then ab n 2 2 which is certainly rational7 so the theorem is proved D Proof that 7139 gt 3 Proof that area of circle is 7rr2 Lemma 32 Every acyclic graph with n gt 0 vertices contains a vertex of degree 0 or 1 Proof By contradiction and the pigeonhole principle Suppose there is a nonempty acyclic graph every vertex of which has degree at least 2 Let G be such a graph Choose any vertex 121 of G 121 has at least two neighbors7 so choose a neighbor 122 of U1 arbitrarily Now 122 has at least one neighbor besides 121 so choose such a neighbor v3 arbitrarily Continue in this way to pick 124125 such that Ul39 is adjacent to Ui1 and Ul39 7 Ui2 for everyi 2 1 Since G has only nitely many vertices7 by the pigeonhole principle there must be some i lt j such that Ul39 127 and 1113111447 712711 are all distinct Then vi712141 7127 forms a simple cycle in G7 which contradicts the fact that G is acyclic Thus G must have at least one vertex of degree at most 1 lntuition is crucial in forming a proof Pictures and diagrams are very helpful7 however7 they cannot replace a formal argument Theorem 33 No graph with n 2 2 vertices and fewer than n 7 1 edges can be connected Proof Uses the minimum counterexample idea7 which combines induction with contradiction Also uses cases Suppose there is a connected graph with n 2 2 vertices and m lt n 7 1 edges Let G be such a graph with the least number of edges of all such graphs There are two cases Case 1 G contains a cycle We select an edge e of G that lies on some cycle 0 and remove it The resulting graph G is still connected any path joining two vertices of G that used to go through e can be rerouted around the rest of the cycle 07 giving a path in G But G has fewer edges than G7 which contradicts the minimality of G Case 2 G is acyclic Let n be the number of vertices of G and let in be the number of edges of G By assumption in lt n71 The graph with two vertices and no edges is clearly disconnected so G must have at least three vertices ie n 2 3 By Lemma 32 G has some vertex v with degree 0 or 1 If degv 0 then u is isolated making G disconnected and so we must have degv 1 Remove 1 and its only incident edge from G The resulting graph G is clearly still connected and furthermore G has n 7 1 2 2 vertices and m 7 1 lt m g n 7 1 7 1 edges Since G has fewer edges than G this contradicts the minimality of G The cases are exhaustive and in either case we arrive at a contradiction Thus no such graph can exist Theorem 34 Any graph with n 2 3 vertices and m 2 n edges must contain a cycle Proof Same minimal counterexample technique Suppose there is some acyclic graph with n 2 3 vertices and at least n edges Let G be such a graph whose n value the number of vertices is least among all such graphs The graph only graph with three vertices and at least three edges is the triangle which is clearly cyclic so we must have n 2 4 By Lemma 32 G has a vertex v with degv 1 Remove 1 and its incident edge if there is one from G to obtain a new graph G G is clearly acyclic because G is acyclic Furthermore G has n 7 1 2 3 vertices and at least n 7 1 edges which contradicts the minimality of G Thus no such graph can exist De nition 35 A tree is a connected acyclic graph Corollary 36 Any tree with n gt 0 vertices has exactly n 7 1 edges 4 1282008 41 Overview of computation The theory was mapped out in 20s 30s before electronic computers Church Hilbert Kleene Goedel to clarify the concept of mathematical proof Turing s and von Neumann s ideas led to rst electronic computer 42 Regular languages The nite state machine automaton7simplest computational model models limited memory com puters 421 Examples Door opener states closed open input conditions front rear both neither nonloop transitions closed 7 open on front open 7 closed on neither probabilistic counterpart Markov chain Other examples number of 1s is even number of 0s is multiple of 4 automaton for strings ending in 00 422 Formal De nitions De nition 41 Let E be a nite set A string ouer E is a nite sequence of elements of Z We may call 2 an alphabet and it elements symbols We write a string by writing its constituent symbols one after another If w is a string we let lwl denote the length of w number of symbols of w There is a unique string of length 0 which we call the empty string denoted by e We can identify the symbols of E with strings of length 1 If x and y are two strings over 2 we let my denote the concatenation of z and y which is the string starting with z and immediately followed by y For example the concatenation of 00110 and 111011 is 00110111011 The empty string contatenated with any string is just the latter string we 6w w for any string w So 6 is the identity under concatenation Concatation is a binary operator like multiplication that takes two strings as arguments and produces a string as a result Concatenation is associative ie for any strings m y and z and we denote this string by zyz We can also drop parentheses in the usual way when concatenating more than three strings etc De nition 42 A deterministic nite automaton DFA is a 5 tuple Q 26q0 F where c Q is a nite set members of Q are called states 0 E is a nite set called the alphabet members of E are called symbols 0 6 Q X E gt Q is the transition function 0 go 6 Q is the start state and o F Q Q is the set of accepting states or nal states Here s an example of a DFA M1 with state set Q q1 q2 qg alphabet E 01 start state ql nal state set F qg and transition function 6 given by the following table Draw corresponding transition diagram a directed graph Describe computation informally using a tape cells with symbols and a nite state control with a read head advancing over the input The DFA accepts the input if its state after reading all the symbols is in F Otherwise it rejects Consider the empty string as input too De nition 43 Let E be an alphabet We let 2 denote the set of all strings over 2 A language ouer E is any subset of 2 ie any set of strings over 2 We use languages to encode decision problems Given an input string is the answer yes or no Strings for which the answer is yes are called yes instances and the others are no instances The language corresponding to a decision problem is just the set of strings encoding yes instances De nition 44 Let M be a DEA with alphabet 2 and let A Q 2 be a language over 2 We say that M recognizes A iff M accepts every string in A and rejects every string in 2 7 A We let LM denote the language recognized by M Thus recognizing a language means being able to distinguish membership from nonmembership in the language7 thus solving the corresponding decision problem Every DFA recognizes a unique language Example DFA recognizing B z 6 01 l 2 2 and the 1st symbol of z equals the last symbol of Draw a seven state DFA for B Whoops7 there is a vestate DFA as well ls ve states the fewest possible We ll see how to answer this question later 5 1302008 51 Formal De nition of a DEA Computation We now de ne a DEA computation formally De nition 51 Let M Q72767q07F be a DEA and let w E 2 be a string over 2 Suppose w w1w2 wn where w E 2 for all 1 g i g n The computation ofM on input w is the unique sequence of states so7 31 7 5 where 0 each 3139 E Q o 50 qo7 the start state7 and o sl 6si1wi for all 1g i g n The computation so7 7 5 is accepting if sn 6 F7 and is rejecting otherwise If the former holds7 we say that M accepts u7 and if the latter holds7 we say that M rejects w Thus so7 31 is the sequence of states that M goes through while reading w from left to right7 starting with the start state Example DFA that recognizes multiples of 3 in unary7 binary Example DFA that accepts strings over a7 b7 c containing abacab as a substring Idea is useful for text search Example Strings over 07 1 with an even number of 1s Strings over 07 1 with an even number of 1s or an odd number of 0s De nition 52 A language A Q 2 is regular iff some DFA recognizes it7 ie7 A LM for some DFA M 52 Nondeterm inism In a DFA the next state is completely determined by the current state and the symbol being scanned according to the transition function 6 In a nondeterministic nite automaton there may be a choice of several states to transition into at each step and we may decide not to advance the read head The machine accepts the input iff there is some series of choices that can lead to an accepting state having read the entire input Transition diagram may have any number of edges with the same label leaving the same state There can also be e edges meaning make the transition without reading the symbol or advancing the read head Example The substring recognizer above Add an e transition and explain it 6 242008 Given an alphabet Z we de ne ES E U 6 which is the set of all strings over 2 of length 0 or 1 Recall from set theory For any set A the set 73A called the power set ofA is the set of all subsets of A For example P17 273D 07 1L 2 172k 3 173k 273k 17 273 De nition 61 A nondeteiministic nite automaton NFA is a 5 tuple Q 26 qo F where c Q is a nite set the set of states 0 E is a nite set the alphabet o 6 Q x 25 H 73Q is the transition function 0 go 6 Q is the start state and o F Q Q is the set of nal states accepting states Notice that 6q a is now a set of states instead ofjust a single state It is the set of possible successor states of q reading a Note also that 6q e is also de ned to be a set of states This is the set of possible successors to q via an e transition Such a transition when taken does not advance the read head Given an NFA M and an input string w there may now be many possible computations or computation paths of M on w We say that M accepts w iff at least one of these computation paths ends in a nal state after reading all of w lnformally M accepts if there is a correct set of transition guesses that leads to an accepting state and reads the entire input Example with detecting a substring in a larger string Easier with an NFA Explain getting stuck that computation path rejects even if it gets stuck in a nal state De nition 62 Let M QE6q0F be an NFA and let w E 2 be a string A complete computation of M on input w is a pair of tuples 50 smw1 wm where 10 allthesiEQfor0 i m 0 all the w 6 25 for 1 g i g m that is each w is either a symbol in E or the emptystring e o w wl wm 0 so go and 0 316 6si71wi for all 1 g i g m The complete computation above is accepting iff 3m 6 F otherwise it is rejecting We say that M accepts w if there exists some accepting complete computation of M on w A complete computation represents a legal path through the NFA while reading the entire input e transitions correspond to steps where w e As with DFAs before we de ne the language LM recognized by NFA M to be the set of all input strings accepted by M We say that two automata NFAs or DFAs are equivalent iff they recognize the same language 61 Equivalence of DFAs and NFAs Here we show that DFAs and NFAs are equally powerful models of computation that is they recognize the same class of languages ie the regular languages We show this in two steps 1 For every DFA there is an equivalent NFA 2 For every NFA there is an equivalent DFA One direction is obvious for any DFA make an equivalent NFA with the same transition diagram Each 6q a is a singleton for a E E and 6q e 0 More formally ifM Q E 6 go F is a DFA de ne the NFA N 622 6 go F where o 6 qa 6qa for all q E Q and a E E and o 6 qe Q for all q E Q It s easy to see that LN LM ie that N is equivalent to M Other direction is nontrivial and somewhat surprising Theorem 63 For every NFA there is an equivalent DFA We give a sketch of a proof which includes the construction of the equivalent DFA but does not verify that it is correct The idea is that as we simulate a given NFA we keep track of the set of all states we could be in after reading each successive symbol of the input Fix an NFA M We ll build an equivalent DFA N If S is the set of all states of M we could possibly get to by reading the input up to but not including a symbol a then the set S of states of M that we could possibly be in after reading a only depends on S and a and can be computed from the transition diagram of M We make each possible set S of states in M a single state of the new DFA N and the transitions of N correspond to shifting the set of possible states of M upon reading each symbol For example the transition S g S would be a transition in N There are only nitely many subsets of M so N is really a deterministic nite automaton 11 M may have e transitions so to nd S from S we rst follow any a transitions from states in S then follow any e transitions thereafter possibly several in a row You may think that we should also follow any e transitions before the a transitions but this won t be necessary as we ll see below The start state of N corresponds to the set of states of M that one could possibly be in before reading any input symbols This is exactly the set of states reachable from the start state of M via e transitions only A set S of states of M constitutes an accepting state of N iff it includes at least one accepting state of M ie the computation could possibly be in a nal state of M Here is the formal construction Fix an NFA M Q 26q0 For any set S Q Q of states of M we de ne the e closure of S denoted ES to be the set of states reachable from S via zero or more e transitions in a row More formally for i 2 0 we de ne inductively to be the set of states reachable from S via exactly i many e transitions E0S S and for all i 2 O Ei1ltsgtr 6 Q l Sq 6 E45 6 6mm U we qEEiS This lets us de ne namely the set of all states reachable from S via zero or more e transitions Note that ES is closed under e transz39tz39ons ie there are no e transitions from inside ES to outside We are now ready to de ne precisely the DFA N equivalent to M we let N 73Q E A S0 f where o 73Q is the powerset of Q 0 S0 Eq0 the set of states reachable from go via e transitions o f S Q Q l S O F 7 0 the set of sets of states of M which contain nal states of M and o for everySQ Q andaEE Ms a E U 6q a 165 From the above de nition every state of N that is reachable from the start state So is closed under e transitions so there is no need to follow e transitions before a transitions in the de nition of A 7 262008 Corollary 71 A language is regular z it is recognized by some NFA Quick example three states with an epsilon move When an NFA is converted to an equivalent DFA often not all the possible sets of states of the NFA are used so not all the DFA states are reachable from the start state and they can be eliminated eg any state sets which are not closed under s transitions As a practical matter instead of including all possible subsets of states of the NFA it s better to grow the DFA states from the start state by following transitions You will usually wind up with a lot fewer DFA states this way Example Here s an NFA that recognizes the language of strings over 1 b that start with b and contain either mm or abbaa as a substring b g a 0 b b m 1 a 8 ab ab To construct the equivalent DFA we build its states one by one starting with its start state then following transitions Whenever we encounter a new set of states of the NFA we add it as a new state to the DFA The general algorithm is as follows lnput NFA M QE6q0F Output equivalent DFA N Q E AS0f Set A 0 no transitions yet Set f 0 no nal states yet Set S0 Eq0 the states reachable from go via paths of s transitions Set Q S0 While there is an unmarked S E Q do For each a E 2 do Let T be the set of states reachable from states in S via a single a transition followed by any number of s transitions Add the transition AS a T to A If T Q then Q Q U T lfT F7 0thenffUT End for Mark S as nished End while Return N QE AS0f End algorithm Let s apply this algorithm to the transition diagram above The start state of the DFA is SO Compute the transitions from S0 First the a transition there is nothing reachable from state 0 following a so the new state of the DFA is Q and we have AS0 a 0 which is a new state so we call it S1 and add it to Q We now have Q S0 S1 where S1 Q and the diagram looks like this 0 GD Starting back at state 0 and following I the only state we can reach is 1 so we have a new state 52 1 and set ASob 1 How about transitions from 1 51 has no states of the NFA so we cannot get anywhere from 51 following any symbol Thus ASla A51 b 0 17 and we should add two self loops from 1 to itself The diagram becomes a a o b SO and 51 are both nished at this point Now SQ Following a from state 1 of the NFA we can get to states 1 and 2 then following the s transition from 2 we can get to 4 Thus we have a new state 53 1 2 4 ASga Following 1 from state 1 we can only get back to state 1 so AltSgb 1 SQ and we put a self loop 52 i SQ Here s the new diagram a e co b 0 b Now we follow transitions from 53 For the a transition the NFA has transitions 1 g 1 1 g 2 and 4 g 5 In addition we can get from 2 to 4 again by following 8 So we have a new state S4 1 2 4 5 ASg a For the b transition the NFA has 1 l 1 and 2 i 3 with no additional 6 moves So we have a new state S5 13 ASg b and the diagram for the DFA is now a b a 611 b 69 14 Following a from S4 the NFA has a transitions to states 1 2 5 and 6 with an s move to 4 So we get a new state 56 124 56 AS4a Since 56 O F 6 7 0 6 is our rst nal state Following 1 from states in S4 we can reach states 1 and 3 and no others and there are no additional s transitions possible Since S5 1 3 we have AS4 b S5 a a cow b 82 090 b b We continue this way until each state of the DFA has a single outgoing edge for every alphabet symbol The complete DFA looks like this a e gtw b a A a 1 124 States are labeled with the states of the NFA that they contain Note that this is not an optimal solution For example all the accepting states can be coalesced into a single accepting state 71 Operations on languages Fix an alphabet 2 Given two languages A B Q 2 we have already de ned A U B and Am B Here are some other useful operations o A 2 7 A7 the complement of A in 2 This is the set of all strings over 2 that are not in A 0 AB mg l x E A and y E B the set of all concatenations of a string in A followed by a string in B Book A o B This operation on languages is associative o Ak A A k times By convention7 A0 o A A0 U A1 U A2 U This is called the Kleene closure of A All these operations preserve regularity7 ie7 if A and B are regular7 then so are all the resulting languages above Draw Cartesian product construction for DFAs for intersection A DFA for A is the same as a DFA for A but with the nal status of every state swapped nal states become non nal states and vice versa By DeMorgan s laws7 we get that union preserves regularity This will be easier to see with NFAs in a minute This is not in the book The notion of a clean NFA pops up on several occasions De nition 72 Let M be an NFA We say that M is clean iff o M has exactly one nal state7 which is distinct from the start state7 o M has no transitions into its start state even self loops7 and o M has no transitions out of its nal state even self loops Proposition 73 For any NFA M there is an equz39ualent clean NFA N Proof If M is not clean7 then we can clean it up77 by adding two additional states 0 a new start state with a single e transition to Ms original start state which is no longer the start state7 and o a new nal state with e transitions from all of Ms original nal states which are no longer nal states to the new nal state The new NFA is obviously clean7 and a simple7 informal argument shows that it is equivalent to the original M For concatenation and union7 we give the NFA construction series and parallel connections7 respectively De ne the clean version of an NFA and do the loop construction for the Kleene closure Point You can t get the Kleene closure for free77 just via an in nite union of nite concatena tions Only nite unions preserve regularity in nite ones do not preserve regularity in general 72 Regular expressions regexps We x an alphabet E for the following discussion Here7 a language is any set of strings over the alphabet E A regular expression or regexp for short7 is an expression that denotes a particular language over 2 Primitive atomic regular expresions are c Q denoting the empty language 0 6 denoting the language 6 consisting ofjust the empty string and o a denoting the language a consisting ofjust the string a of length 1 for any symbol a E E If r is a regular expression we write Lr for the language denoted by r We may also just use the regexp itself in place of the language it denotes Additionally regular expressions can be combined with three possible operators union con catenation and Kleene closure If r and s are regexps then so are c r U s denoting the language Lr U Ls the union of Lr with Ls 0 rs denoting the language LrLs the concatenation of Lr with Ls o F denoting the language Lr the Kleene closure of Lr No other regular expressions are possible This is an inductive aka recursive de nition since it de nes new regular expressions in terms of shorter ones subexpressions Parentheses are only used for grouping and can be dropped if we assume the following syntactic precedences r before V before rs before r U 3 Both binary operations are associative so we don t care how they associate Examples Pascal like oating point constants etc 8 2112008 The language denoted by a regular expression is always regular because the union concatenation and Kleene closure operations preserve regularity Draw DFAs for the atomic regexps An actual proof could be by induction on the length of the regexp Proposition 81 Euerg regular regular expression denotes a regular language The proof is by induction on the complexity or length of a regular expression using the closure properties of regular languages Somewhat surprisingly the converse is true The next theorem is the converse of Proposition 81 Theorem 82 Euerg regular language is denoted by some regular expression The proof given below is by construction of a regular expression for a language A given an NFA recognizing A The construction uses a generalized form of NFA Two operations in terms of transition diagrams parallel edge combination and vertex removal De nition 83 Let REGEXP be the class of all regular expressions A generalized nondetermin istic nite automaton GNFA is a 5 tuple N Q 26q0 F where c Q is a nite set the set of states 0 E is a nite alphabet 0 go 6 Q the start state o F Q Q the set of nal states and o 6 Q x Q a REGEXP is the transition function The transition diagram for a GNFA is the same for an NFA except that there is exactly one edge from each state q to each state r and the edges are labeled with regular expressions the edge q r being labeled with 6q r Any edge labeled with the regexp Q can be omitted from the diagram they can never be followedisee below A complete accepting computation can be de ned for GNFAs analogously to the case of NFAs The idea is that you can follow an edge by reading a pre x of the remaining input that matches the edges label ie you read a string that is in the language denoted by the label which is a regexp If you really want it here s a formal de nition Note how similar it is the corresponding de nition for NFAs De nition 84 Let N Q 26 qo F be a GNFA and let w E 2 be a string We say that N accepts w if there exist strings w1 wk 6 2 and states so 3k 6 Q for some k 2 0 such that w wl wk 30 q07 0 5k 6 F and o w E L6si1 for all 1g i g k The language recognized by N denoted LN is the set of all strings over 2 accepted by N If k 0 above then the right hand side of the rst item is the empty concatenation which is e by convention so w 6 Also qo so 5k 6 F and the last item is satis ed vacuously Note that there is no a prion length restrictions on the strings w for a GNFA whereas each w must have length at most 1 for an NFA Also note that acceptance only depends on the languages denoted by the various regexps on the transitions not the syntax of the regexps themselves That is if any regular expression 6 p q is replaced with an equivalent regular expression denoting the same language then the resulting GNFA is equivalent to the original one Finally note that along any accepting path above each language L6si1 is nonempty it contains the string w and so no edges labeled with Q are ever traversed We can de ne a clean GNFA analogously to a clean NFA A GNFA is clean iff 1 it has exactly one nal state which is distinct from the start state 2 all transitions from the nal state are labeled 0 and 3 all transitions into the start state are labeled 0 Given an NFA it is easy to construct an equivalent GNFA Let N Q E 6 go F be any NFA De ne the GNFA G to be Q E6 q0F where for any pq E Q we de ne the regexp 6 p q to be the union of all strings in ES labelling transitions from p to q in N That is WW1 U w wezziqe nw Each string w 6 ES is clearly a regexp It is possible the union on the right is empty in which case an empty union of regexps is naturally Q by convention G allows exactly the same state to state transitions as N does reading the same strings so it is clear that N and G are equivalent Also if N is clean then G is certainly also clean Now for the proof of Theorem 82 Let A Q 2 be any regular language over 2 Let N be some NFA recognizing A We can assume WLOG that N is clean thus N QE 6q0 qf for some unique nal state qf 7 go Let G Q E 6 go qf be the equivalent clean GNFA constructed from N as in the previous paragraph Starting with G we will repeatedly remove states not in q0 qf producing a series of equivalent GNFAs until we get a GNFA with only two states go and qf and a single nonempty transition7labeled by some regexp R7going from go to qf This last GNFA clearly recognizes the language LR and it is equivalent to the original NFA N so we will have A LN LR which proves the theorem All we have to do now is describe how to remove a nonstarting non nal state from a clean GNFA G QE6 q0 qf to get an equivalent GNFA H Suppose we remove a state q E Q 7 q0qf from C it doesn t matter which q we pick We need to de ne H to accommodate any accepting path in G that may have gone through q allowing it to bypass q Such a path would enter q from some other state 3 7 q loop some number of times at q then exit to some other state if 7 q The path could neither start nor end at q because q is not the start state or a nal state Let x 6 sq let y 6 q q and let 2 6 q t z y and z are regexps Any path from 3 tot that goes through q as above reads a string matching m followed by zero or more strings matching y followed by a string matching 2 all concatenated together Equivalently this path reads a string matching zyz so we need to include mgfz as a possible transition in H from s to t We do this for all pairs of states st E Q 7 q and it follows from our general considerations that H must equivalent to G We can prove this last fact formally using De nition 84 but the proof is rather tedious and so we won t bother Formally let G and q be as above We de ne H to be the GNFA Q 7 q26 q0 qf where for each st E Q 7 q 6 st 6st U mfz where z 6 sq y 6 q q and z 6 q t We may simplify 6 s t if possible In particular if Lm Q or Lz Q then Lzyz 0 and so in this case we can set 6 s t 6 st If we simplify in this way then we see that we make H clean provided G is clean Also H has one fewer states than G so repeating this process will lead to a clean equivalent GNFA with state set q0qf after a nite number of steps This concludes the proof of Theorem 82 9 2182008 91 Proving languages nonregular Let A 0 1 l n 2 0 This language is easy to recognize given an input string w E 0 1 1 reject if there is a 1 followed by a 0 somewhere in w else 2 count the number of 0 s and 1 s if the numbers are equal then accept else reject Yet we ll see in a minute that A is not regular ie no DFA equivalently NFA can recognize A lntuitively a DFA can only scan from left to right and has a xed nite amount of memory its state When it passes from the 0 s to the 1 s it can t remember exactly how many 0 s it has seen 19 so it can t compare this with the number of 1 s That A is not regular speaks more to the weakness of the DFA model than it does to the dif culty of A Lemma 91 Pumping Lemma NFA version IfA is a regular language then there exists an integerp gt 0 such that for any string w E A with lwl 2 p there exist strings z yz such that zyz w lxyl S p lyl gt 0 and for alli Z 0 mylz E A The Pumping Lemma says that if A is regular then every suf ciently long string w E A may be pumped that is some substring y in w may be repeated any number of times and the resulting pumped string is still in A We call this pumping on y Applications 0 0 1 l n 2 0 is not regular 0 0m1 l 0 g m g n is not regular 0 s 6 01 l s has the same number of 0 s as 1 s is not regular 0 0 2 l n 2 0 is not regular 0 ww l w 6 01 is not regular 0 02 l n 2 0 is not regular 10 2202008 101 Minimal DFAs A DFA M is minimal if there is no DFA N equivalent to M with fewer states We will assume a xed alphabet 2 throughout For convenience we make the following de nition suppose N Q 26 qo F is a DFA For any state q E Q and string w over 2 de ne 6q w to be the unique state resulting from starting in state q and reading w on the input That is 5 extends 6 to strings of any length More formally we can de ne 6 Q x 2 a Q inductively Base case 5q6 q Inductive case 5qaw 56qaw for a E E and w E 2 It is clear by the de nition that for any strings z and y and state q 5q my 55qz Note also that a string w is in LN iff 6q0w E F ie 6q0 w is an accepting state Let L be any language not necessarily regular over 2 For every string w de ne Lw x l wm E L Note that LS L and if Lw Lw then Lwa Lwa for any a E 2 because zELwa ltgt wamEL ltgt azELw ltgt 1356sz ltgt w azeL ltgt zELwa De ne CL Lw w 62 Theorem 101 Myhill Nerode LetL be any language L is regular if and only ifCL is nite and in this case there is a unique minimal DFA recognizing L with lCLl many states We ll prove Theorem 101 via three lemmata The rst lemma shows that lCLl is a lower bound on the number of states of any DFA recognizing a language L Lemma 102 If a language L is regular recognized by some DFA N with state set Q then lCLl S lQl39 Proof Suppose N QE6q0F For any state p E Q de ne NZ to be the DFA that is the same as N but whose start state is p That is N QE6p So for example N Nqo Now let w be any string over 2 and let q 5q0 w We claim that Lw LNq To see this note that for any string z E 2 we have x E Lw ltgt wm E L by de nition of Lw wm E LN since L LN 5W07 wm E F de nition of acceptance 55q0 w z E F since this is the same state 5q z e F de nition of q m E LNq MUM So with N xed we see that Lw only depends on the state obtained by starting in go and reading w and thus the number of distinct Lw is no more than the number of states of N CI The next lemma gives lCLl if CL is nite as an upper bound on the number of states necessary for a DFA to recognize L Lemma 103 LetL be a language IfCL is nite then L is regular recognized by a DFA ML with exactly lCLl many states Proof We construct ML having state set CL We let ML CLE 6q0F where qo Ls L7 0 6Lwa Lwa this is well de nedl and oFq CLle q Note that if we start in the start state go of ML and read a string w then we wind up in state Lw that is 5q0w Lw You can see this by induction on The base case is when lwl 0 that is when w 8 In this case reading w keeps us in go But qo Lg Lw by de nition so we wind up in state Lw in this case Now suppse lwl gt 0 and so w ya for some string y and alphabet symbol a By the inductive hypothesis reading y lands us in state Ly but then further reading a moves us to state 6Ly a Lya Lw lntuitively the state Lw coincides with the set of all strings x such that starting in this state and reading z would lead us to accept um This is why we make Lw itself to be an accepting state when we do if reading 6 should make us accept w Immediately after this proof we give a concrete example of an ML We must show that L LML For any x E 2 we have below go 5 and F are all with respect to ML z E L ltgt 6 E Lm by de nition of Lm ltgt Lm E F by de nition of F ltgt 5q0z E F since Lm 5q0 z from above ltgt z E LML by de nition of acceptance Thus ML recognizes L El Example Let E ab and let L be the set of all strings that contain three consecutive b s somewhere in the string So L is denoted by the regular expression a UbbbbaU b With a little thought we can see that CL 4 In fact CL L5 LbLbb Lbbb These four languages are all distinct 0 LS L 0 Lb contains bb which is not in LS but does not contain 1 0 L55 contains 1 which is neither in LS nor in L5 but does not contain 8 0 L555 contains all strings over 11 including 8 Furthermore any Lw is equal to one of these four For example Labaabb L5 and Lbbbaaaaa Lbbb For any w how do you tell which of the four Lw is We thus get the following DFA ML for L as constructed in the proof of Lemma 103 o The state set is CL 0 The start state is L5 0 The sole accepting state is Lbbb as this is the only one of the four languages that contains 8 o The transition function 6 is as follows I 7 La 7 3st b L177 6Lba Lba Lg 6Lbb7 a Lbba L57 6Lbb7 5 Lbbln 6Lbbb7a Lbbba mbll Lbbln 6Lbbb7 5 Lbbbb Lbbb D The third and nal lemma proves that ML is unique thus completing the proof of Theorem 101 First we will say that a DFA N QE6q0Fgt is economical if every state of N is reachable from the start state that is for every q E Q there is a string w such that q 8q07w Clearly a DFA N is equivalent to an economical DFA with the same number or fewer statesijust remove any states of N that are unreachable from qo These states will never be visited in a computation so they are completely irrelevant Lemma 104 Let L be a regular language The DFA ML of Lemma 103 is the unique up to renaming of states minimal DFA recognizing L Proof Let N Q E 6 go F be any economical DFA recognizing L We can map the states of N surjectively onto the states of M L in a way that preserves the transition function start state and accepting states For every q E Q de ne fq LNq where Nq is as in the proof of Lemma 102 This de nes a mapping f with domain Q mapping states to languages We will verify the following properties of f H The range of f is exactly CL that is 1 maps Q onto CL the state set of ML 2 fq0 LS L the start state of ML 03 Let q E Q be a state and let w be any string such that fq Lw such a w exists by item For any a E Z we have f6qa Lwa which is the result of the transition function of ML being applied to the state Lw fq and a F For any q E Q we have q E F if and only ife E fq that is if and only if fq is an accepting state of ML For 1 First let q be any state in Q Since N is economical there is some string w such that q 5qow In the proof of Lemma 102 we showed that Lw LNq Since LNq fq by de nition this shows that fq 6 CL and thus the range of f is a subset of CL Lastly we must show that every element of CL is equal to fq for some q E Q Given any string w we de ne q 5qow Then again by the proof of Lemma 102 we have L LNq which also equals fq Thus every Lw is in the range of f and so 1 maps Q surjectively onto CL For 2 Clearly fq0 LNq0 LN L L5 23 For 3 Let r 6q a For any string m we have m E ltgt m E LNT ltgt rm E F ltgt qaz E F ltgt am 6 LNq ltgt am 6 M ltgt am 6 Lw ltgt wam E L ltgt z E Lwa Therefore fr Lwa For 4 Clearly q E F if and only if e E LNq because 6qe q Now we re ready to prove the lemma Let ML CLE6 LSF be the minimal DFA for L constructed in the proof of Lemma 103 Suppose N QE6q0F is any minimal DFA recognizing L We show that N and ML are the same DFA after relabelling states Since N is minimal it must also be economical otherwise we could remove at least one unreachable state to get a smaller equivalent DFA Thus we have the surjective mapping f Q a CL de ned above Also by Lemmata 102 and 103 we must also have lQl CL since N is minimal Thus 1 must be a bijection perfect matching between Q and CL This is the relabelling we want 1 maps the start state of N to the start state of ML by 2 it maps accepting states to accepting states and nonaccepting states to nonaccepting states by 4 nally it preserves the transition function that is for any q E Q and a E E f5q7a Lwa 6 fq7a by 3 where w is any string such that fq Lw This shows that N and ML are identical up to the relabelling 1 which proves the lemma D 102 Minimizing a DFA Nice as they are the results in the last section do not give an explicit general procedure to construct a minimal DFA equivalent to a given DFA Often one can determine ML by inspection as we did in the Example above Nevertheless we would like a general algorithm that given a DFA N QE 6q0F constructs ML where L LN The algorithm to do this works in two steps 1 remove all states of N that are not reach able from qo making N economical and 2 collapse remaining states together that we nd are equivalent We ll assume that we have already performed 1 so that N is economical For any state q E Q de ne Nq as in the proof of Lemma 102 above 1021 State equivalence and distinguishability We say that two states p and q in Q are distinguishable if LNp 7 LNq that is there is some string x such that one of 6p z and 6q z is accepting and the other is not Such a string m if it exists distinguishes p from q Such an x is in LNp ALNq the symmetric difference of LNp and LNq1 If p and q are indistinguishable ie not distinguishable by any string ie LNp LNq then we say p and q are equivalent and write p x q This is obviously an equivalence relation Intuitively p x q means that our acceptance or rejection of any string w does not depend on whether we start in state p or in state q before reading w Although it s not necessary for the current development you may observe that p x q iffp and q are mapped to the same state by the 1 de ned in the proof of Lemma 104 The meat of the algorithm is to determine which pairs of states are equivalent This is done using a table lling technique We methodically nd distinguishable pairs of states when we can t nd any more the pairs of states left over must be equivalent For convenience assume that Q 1 n We use a two dimensional array T with entries Tpq for all 1 g p q n We ll keep T symmetric in what follows ie any value assigned to TLpq will automatically also be assigned to Tqp implicitly Also we will have no use for diagonal entries TLpp so actually only the proper upper triangle of T need be stored those entries Tp q where p lt q We proceed as follows Initially all entries of T are blank FOR each pair p q of states with p lt q DO IF p E F or q E F but not both THEN Tlpi ql 7 X REPEAT FOR each pair p q with p lt q and each a E 2 DO IF TLp q is blank and T6pa6q a X THEN Tlpi ql 7 X UNTIL no entries are marked X in one full iteration of this loop When nished it will be the case that an entry Tp q is blank if and only ifp x q To see the if part notice that we only mark an entry with X if we have euidence that the two states in question are distinguishable If Tp q gets marked in the initial FOR loop it is because 6 distinguishes p from q For entries marked in the REPEAT loop we can proceed by induction on the number of steps taken by the algorithm when an entry is marked to show that the corresponding states are distinguishable if TLp q is marked in the REPEAT loop it is because T6p a 6q a was marked sometime previously for some a E Z By the inductive hypothesis 6p a and 6qa are distinguished by some string w But then aw clearly distinguishes p from q so marking TLp q is correct This proves the if part To show the only if77 part we need to show that all distinguishable pairs of states are eventually marked with X Suppose this is not the case We call p q a bad pair ifp q but Tpq is left blank by the algorithm Our assumption is that there is at least one bad pair Let w be a string distinguishing some bad pair p q and assume that w is as short as any string distinguishing any bad pair It must be that w 7 6 since otherwise 6 distinguishes p from q which in turn implies that either p E F or q E F but not both but then Tpq is marked X in the initial FOR loop so p q is not a bad pair So we must have w ay for some a E E and y E 2 Then y distinquishes r 6p a from s 6q a and since lt lwl r s is not a bad pair by the minimality of w 1For any sets A and B we de ne AA B A 7 B U B 7 A A U B 7 A B ie the set of all z such that z E A or z E B but not both So TV 3 is marked with an X at some point But then on the rst iteration of the REPEAT loop following the marking of Tr s we mark TLp q with X which contradicts the assumption that p q is a bad pair Thus there are no bad pairs Now that we can tell whether any two states are equivalent we are ready to construct the minimum DFA M for L Let the state set of M be the set Qz of equivalence classes of Q under the z relation For any q E Q we let q denote the equivalence class containing q We de ne the transition function 6M for M as follows for any q E Q and a E 2 let 5Mlql7a 6q7al This is a legitimate de nition because p x q clearly implies 6p a z 6q a and so the transition does not depend on which representative of the equivalence class we use Also note that when we extend 6M to 6M acting on all strings we can routinely check that 514061110 5617 wl for all q E Q and w E 2 We de ne the start state of M to be go and the set of accepting states of M to be FM M l r e F We must verify two things 1 M recognizes L and 2 M is minimal For 1 let w be any string wEL ltgt Aq0w 6F ltgt 5q07wl 6 FM ltgt 5Mq0w 6 FM ltgt w E Thus L For 2 rst note that since N is economical so is M if r is any state of M let w be such that 5q0 w r then 5Mq0 w Wm 10 r and thus r is reachable from the start state go via w Now we show that CL LMq l q E By adapting the proof of Lemma 102 we get that Lw LMq for any string w where q 5Mq0w But since M is economical every state of M is of this form for some w so indeed CL LMq l q E We ll be done if we can show that any two distinct states of M are distinguishable for then LMZ 7 LMq for all 19 q E Qz and so it must be that lLMq l q E lCLl which implies that M is minimal by Lemmata 102 and 103 To see that all distinct states of M are distinguishable notice that if 7 q then p q and so p and q are distinguished in N by some string x We claim that the same string z also distinguishes from q in M Let r 5p z and let 3 5qm Then either r E F or s E F but not both We also have r and Mqz s by de nition so we re done if either r or s is accepting in M but not both Suppose WLOG that r E F Then T is accepting 26 in M by de nition Further 3 F This implies that 5 cannot be accepting in M otherwise there is some 3 E 5 O F but then s z s and so 3 F because 3 Ficontradiction Thus 3 is not accepting in M Any equivalence class in Qz either contains only accepting states or only nonaccepting states A similar argument works assuming 3 E F Thus and q are distinguishable in M 11 2252008 Example Consider the following DFA which is not minimal We use the table lling method described above to nd all distinguishable pairs of states lnitially T is all blank We rst look for pairs of states p q that are s distinguisable ie where one of p and q is a nal state but not both Such pairs are 1 2 23 and 24 We put an X in the corresponding entries of T making sure that if we mark Th y with an X we also mark Ty m with an X Entering the REPEAT loop rst iteration we look for transitions into previously marked ie s distinguishable pairs of states We only look for transitions from pairs of states for which T has a blank entry We nd the pair 1 3 because 61 a 4 63 a 2 and T4 2 T2 4 X Transitioning on the symbol a again we also nd 14 because T61a64 31 T42 T24 X Thus we set T13 T31 T14 T41 X We don t nd anything else looking for b transitions so the table after the rst full iteration of the REPEAT loop is 3 4 X X X X We then run the second iteration of the REPEAT loop again looking for transitions into previously marked pairs of states We don t nd anything new so we break out of the loop and out of the table building algorithm with the nal table as it is above The only missing X is for the pair 3 4 So states 3 and 4 are indistinguishable and all other pairs of distinct states are distinguishable So for the minimum DFA we collapse states 3 and 4 into a single state and also collapse transitions as you would expect Here is the equivalent minimum DFA 111 Introduction to Turing machines Tun39ng machines TMs are formal devices just like DFAs but they are much more powerful and their behavior is correspondingly more subtle They can be used as formal renderings of what we informally call algorithms Turing machines have a o oneway in nite readwrite tape head can move in both directions 0 nitestate control 0 accepting and rejecting states two halting states take effect immediately 0 start state and o nite transition function qa 3 q a d where d is either L left or R right 28 Turing program M1 for B wwlwin01 On input w H Scan input to make sure it contains a single symbol If not reject to Zig zag across crossing off left symbol and checking corresponding symbol on right side If different reject Otherwise cross off right symbol OJ When all left symbols crossed off check right to see if any symbols left If so reject else accept De nition 111 Formal De nition ofa TM A Turing machine TM is a 7 tuple Q E P 6 go qawept maggot where c Q is a nite set the set of states 0 E is a nite alphabet the input alphabet o P is a nite alphabet the tape alphabet where E Q P q07 qaoceph qreject E Q and qaocept 7 qreject go is the Start 5tate7 and qaccept and qreject are the two halting statesithe accepting state and rejecting state respectively and o 6 Q x P a Q x P x L R is a function the transition function where L and R are distinct objects denoting left and right respectively Also P O Q 0 not in the textbook and P contains a special blank symbol that is not in E A TM M Q EF6 q0qawept qmgm computes as follows Start with input string w E 2 on the leftmost part of the tape the rest of the tape blank state go the tape head scanning the leftmost square Repeatedly apply the transition 6 function based on the current state q and the symbol a currently being scanned The value of 6q a is a triple r b d that says what to do next change the state to r write b on the tape where the head is thus overwriting a then move the head one cell in direction at either left or right If M tries to move off of the left end of the tape the head stays put instead Note the differences between a TM and a DFA A TM can exhibit much more subtle and complex behavior 0 A TM s head can move in both directions one cell at a time o A TM can alter the contents of its tape 0 A TM can use as much of the blank portion of its tape beyond the input as it wants 0 A TM can use any symbols in its tape alphabet P but it only computes on input strings over the input alphabet E o A TM s computation ends just when it enters one of the two halting states This can happen at any time eg before or long after it has read the entire input 0 A TM may neuer enter either of its halting states In this case the TM runs forever and we say that the TM loops Give a diagram for M1 Show how it computes on 101110111 Some conventions Omit qmvm and any transitions to it Omit any transitions out of qawept Here is a simpli ed transition table for M1 0 is the start state 00 gt gt 1mR 01 gt gt 2mR 0 gt gt 7R 10 gt gt 10R 11 gt gt 11R 1 gt gt 3R 20 gt gt 20R 21 gt gt 21R 2 gt gt 4R 3m gt gt 3mR 30 gt gt 5zL 4m gt gt 4mR 41 gt gt 5zL 5m gt gt 5zL 5 gt gt 6L 60 gt gt 60L 61 gt gt 61L 6m gt gt 0mR 7m gt gt 7mR 7 H accept M1 actually has ten states We don t list the rejecting state at all and we don t bother listing any transitions out of the accepting state Any missing transitions above go to the rejecting state in that case we don t care what is written or which way the head moves 12 2272008 We need to formalize the notion of a TM computation First we need the concept of a con guration A con guration of a TM M is a snapshot of Ms computation at a given time We can represent con gurations by strings More formally De nition 121 Let M 622P6q0qaweptqmject be a TM A con guration of M is rep resented by a string of the form uqv where 741 6 W and q E Q We call q the state of the con guration The string uqv represents the state of Ms computation at some point in time It means that Ms current state is q the entire current tape contents to the left of the cell being scanned is u and 1 represents the contents of the tape starting with the scanned cell and extending at least 30 through the rightmost nonblank symbol Note that the same con guration can be represented by more than one string namely by padding it on the right with blanks Thus 1101q00 1101q00 1101q00 etc all represent the same con guration Let M be as in De nition 121 above and let C1 and Cg be con gurations of M We say that C1 yields Cg if M can legally go from con guration C1 to con guration Cg in a single step More formally let ab E P be any symbols over F let u u E F be any strings over F and let p E Q be any nonhalting state There are two cases one for each possible direction the head can move 1 Suppose 6p a q c R for some q E Q and c E P Then any con guration represented by upau yields the con guration represented by ucqu 2 Suppose 6p b q c L for some q E Q and c E P Then a any con guration represented by uapbu yields the con guration represented by uqacu and b any con guration represented by pb u yields the con guration represented by qcu You should check that these cases match up with your intuition about Ms computation De nition 122 Let M be as in De nition 121 and let w E 2 be any string over M s input alphabet o The start con guration of M on input w is represented by qow c Any con guration with state qacwpt is an accepting con guration of M c Any con guration with state amigo is a rejecting con guration of M o A halting con guration of M is either an accepting or rejecting con guration of M Note that a halting con guration does not yield any further con gurations and a nonhalting con guration yields exactly one con guration De nition 123 Let M and w be as in the previous de nition The computation of M on input w is the unique sequence C0 C1 Cg of con gurations of M such that CO is the start con guration of M on w each C yields Ci and either 1 the sequence is nite ending with an accepting con guration 2 the sequence is nite ending with a rejecting con guration or 3 the sequence is in nite containing no halting con guration In Case 1 we say that the computation is accepting and that M accepts w In Case 2 we say that the computation is rejecting and that M rejects w In Case 3 we say that the computation is in nite or looping and that M runs foreuer or loops on w ln Cases 1 or 2 we also say that M halts on w For each TM and input w there is a unique computation and it is one of the three types above Also you can generate any nite amount of itl We can de ne language recognition for TMs just as we did for DFAs De nition 124 Let M be as in the previous de nition The language recognized by M or the language of M denoted is de ned as LM w E 2 l M accepts w The next de nition is analogous to the way we de ne a language to be regular via DFAs De nition 125 A language is Turing 39 aka I t L or recursiuely enumerable iff some TM recognizes it If a TM M does not accept an input string w then it either rejects or loops on w If the latter is often difficult or impossible to tell in advance that this will happen So we have the strange and uncomfortable situation where w LM but we never know for sure that this is the case We can start simulating the computation of M but we can only discover nitely much of it in any given nite amount of time and that may not be enough to predict M s eventual behavior lt s generally desirable when this situation can never arise De nition 126 A TM is a decider iff it halts on all its inputs lf TM M recognizes language A that is A and is a decider then we also say that M decides A De nition 127 A language is decidable aka computable or recursiue iff some TM necessarily a decider decides it Box and lightbulb picture of TMs Transducers A TM can do more than accept reject or loop on an input We can use TMs to compute functions 2 a 2 Such TMs are called transducers De nition 128 A function f 2 a 2 is computable if there is a Turing machine M that on every input w E 2 halts with just fw on its tape 13 332008 131 Hacking TMs You can think of TMs as programs in some rudimentary programming language such as assembly language or machine language Despite their simplicity they are just as powerful as any higher level general purpose programming language or any other mathematical model of computation this is also true of assembly and machine language The next couple of lectures is meant to convince you of this What are the building blocks of general purpose programming Data types and structures numbers integers and niteprecision oating point character strings arrays lists records trees etc operations on data structures assignment arithmetic operations on numbers array index ing stringlist splicing and concatenation etc and high level algorithm building components sequences of statements if then else constructs while and other kinds of loops procedures and functions recursion All of these can be implemented with TMs Example Maintaining a list Given strings m1 mn E 2 we can represent the list n tuple ml zn by the string z1 zn where is a separator symbol not in 2 Putting an end marker on the left exercise Compute the length of a list Given 0139 nd mi Go to higher level descriptions of TMs 132 Multitape TMs Let k 2 1 A k tape TM has k separate 1 way in nite tapes numbered 1 to k with a head scanning each one The machine changes state and moves each head in some direction depending on the combination of k symbols being scanned De nition 131 Let k 2 1 A k tape Turing machine is a tuple M QEP 6q0qacwptqmject where all components are as with a standard 1 tape TM except that 6 Q x Pk a Q x Pk x L S Rk Here L S and R denote the head movement directions left stationary and righ respec tively 77 Let M be a k tape machine as above and let w E 2 The computation of M on w starts in state go with w being in the leftmost portion of tape 1 also called the input tape The rest of tape 1 is blank and all the other tapes are completely blank initially and the heads are all scanning the leftmost cells of their respective tapes At any point in the computation M will be in some state q and the heads will be scanning symbols a1 ak E P on tapes 1 k respectively If 6q a1ak r b1bkd1dk say and q is not a halting state then for all 1 lt 2 lt k 0 each a is overwritten with b on tape 2 the ith head either moves one cell right if 1 R stays put without moving if 1 S or moves one cell left if d L with the usual exception of not moving if scanning the leftmost cell and 0 Ms state becomes r This all constitutes one step of the computation Note that the transition depends on the state and all k symbols being scanned More examples Reversing a string exercise Addition of unsigned integers Basic list opera tions head tail empty test list construction 14 352008 141 Encoding 0f Finite Objects By nite object I mean any piece of data that s representable in computer memory Such an object contains a nite amount of information and can be encoded as a nite binary string in some reasonable way When you store data in a le you are essentially encoding it as a binary string because a le is just a nite sequence of bits You store it in a way that you can easily retrieve it later This makes the encoding reasonable Lots of different types of nite objects can be easily encoded as binary strings 33 natural numbers eg usual binary representation integers eg two s complement o strings possibly over a bigger alphabet eg replace each symbol with a xed length binary string nite lists of objects eg rst encode each object as a binary string then build the list using separators as we did in the previous lecture with alphabet 0 1 then re encode this string as a binary string as in the last item above 0 nite sets eg as lists of their members 0 relations over nite sets eg as nite sets of ordered pairs which themselves are 2 element lists 0 functions with nite domain and codomain eg as relations above 0 graphs trees etc The reason to encode objects as strings is so that TMs can compute with them Formally TMs only compute with strings but under reasonable encodings we can imagine that TMs are computing with these other kinds of nite objects as well For any nite object O we let lt0 denote the encoding of O as a binary string under some reasonable encoding If 91 On are nite objects we use lt01 On to denote the string encoding the list of the objects Here are some more types of easily encodable objects that we ve been introduced to in this class DFAs NFAs regexps and TMs These are all nite objects built out of components in the list above For example a TM M can be encoded as a string that is input to another TM What can TMs do with TMs as inputs One answer simulate them 142 TMs Simulating TMs One of the most important capabilities of a TM is that it can simulate other TMs One can easily conceive of a 3 tape TM U that takes as input a string of the form M w where M is a 1 tape TM and w is a string over M s input alphabet and proceeds to simulate the computation of M on input w For instance it may copy to tape 2 leaving just an encoding of w on tape 1 then repeatedly scan the string encoding M on tape 2 to see what M s next move is based on the encoded symbol currently being scanned on tape 1 and the current state of M which is maintained in encoded form on tape 3 It would be quite tedious to write down a complete formal description of U but you could do it if pressed We haven t completely speci ed U because we haven t said what U does with input strings that are not of the form M w where M is a TM and w is a string We often don t care what U does but just for completeness In this and in all future cases we ll assume that the TM rst checks the syntax of its input string and rejects if the string is not of the assumed form The machine U is called a universal Tun39ng machine because it can mimic the behavior of any Turing machine on any input whatsoever given a string describing the machine and its input It was Alan Turing who rst showed that universal TMs exist and they served as the chief inspiration for the stored program M is the program w its input electronic computers that came later and that are ubiquitous today Can U simulate itself U has three tapes and it only simulates TMs with one tape But below we show that any k tape machine can be simulated by a onetape machine so we can assume WLOG that U is a standard 1 tape machine Exercise 141 Given U as above and any string w show how to generate an in nite sequence of distinct strings 101102 such that U behaves the same on inputs 101102 as it does on w SPOILER The solution to the exercise is instructive Given a string w let wi ltU7 wgt7 102 ltU w1gt wi1 U7 w gt7 This solution does not even attempt to analyze the innards of U or how its computation proceeds and such an attempt would usually be futile Turing machines can be devious that way In general TMs can defy any attempt to determine beforehand their eventual behavior There are lots of variations on the universal machine concept There is a Turing machine C that given input ltMwtgt where M is a TM w is a string over M s input alphabet and t is a nonnegative integer simulates M on input w for t steps or until M halts whichever comes rst If M does not halt on w within t steps then C rejects ltMwtgt I ll call such a machine C a clocked uniuersal Turing machine You can also imagine a TM that takes encodings of two or more TMs with inputs and simulates them all simultaneously alternating one step at a time for each Recall the de nitions of decidability and Turing recognizability T recognizability It is obvious that if a language A is decidable then it is T recognizable We ll see later that the converse does not hold But we do have the following facts Proposition 142 If a language A is decidable then its complement A is decidable Given a decider for A just swap the accepting and rejecting states to get a decider for A Proposition 143 Let A be any language If both A and its complementA are Turing recognizable then A is decidable Proof Suppose A LM1 and A LM2 for some TMs M1 and M2 To decide whether or not some string w is in A run the two machines M1 and M2 simultaneously on input w Exactly one of these machines will eventually accept w lf M1 accepts then w E A if M2 accepts then w A Here s the algorithm On input w 1 Run M1 and M2 simultaneously on input w until one of them accepts 2 If M1 accepts then accept else reject77 35 Let M be a TM that implements this algorithm It is clear that M is a decider and that A LM therefore M decides A El We will often describe algorithms in an informal high level way like this It should come as no surprise that the algorithm above can be implemented by a Turing machine but formally describing such a machine is astoundingly tedious and not particularly illuminating 143 Simulating a ktape TM with a standard ltape TM Book method maintain a k tuple on the tape whose entries are the contents of the k tapes of the machine being simulated Mark the location in each entry where the head should be Each step of the k tape machine is simulated by scanning and updating the entire list left to right then right to left Alternate method use bigger tape alphabet and multitrack tape Each tape alphabet symbol encodes corresponding contents of the k tapes and for each tape whether or not the head is scanning that cell Technicality must rst prepare the active region of the tape mark beginning and end Each step of the k tape machine is simulated by a full pass of the active region of the 1 tape machine 0 going left to right gather information about which symbol is being scanned on which tape 0 going right to left simulate the writing and head movement for each tape All additional information including the state of the k tape machine constitutes a xed nite amount of information and so can be stored in the state of the simulating machine On to a formal description This is the last time 1711 describe a Turing machine formally We x a k tape TM M Q7 27 P7 67 q07 quest2pm grant We ll refer to the cells on each tape as cell 012 starting with the leftmost cell We build a standard 1 tape Turing machine M Q7 1va A7 Q07 Qacoeph Qreject to simulate M where the i1st cell ofM contains within a single multitrack symbol information about all the contents of the ith cells of the k tapes of M along with whether or not each cell is currently being scanned by one of Ms heads This makes M s tape alphabet rather large f r o 0 Man X P where represents disjoint unionithe union of sets assumed to be disjoint As well as containing all of Ms tape alphabet and a new end marker P also contains the multitrack symbols which we will depict as k x 2 arrays For example a typical multitrack symbol looks like gt a b c b for a 4 tape machine Here a b c E P and the arrows indicate which cells are being scanned This symbol represents the situation where some cell on tape 1 contains an a and is being scanned the cell right below it on tape 2 contains 1 not scanned the cell below that on tape 3 has 0 scanned and below that there is a b not scanned on tape 4 The transition diagram of M consists of a preparation phase followed by the main simulation loop The preparation phase starts with some input string w E 2 on the tape and ends with the tape recording the starting con guration of M The main loop is composed of two subloops the reading subloop where the head moves from left to right gathering transition information and the writing subloop where the head alters the tape accordingly while moving from right to left For simplicity our M will only mimic M in terms of accepting rejecting or looping and we won t care about what is left on Ms tape at the end The states of Q are as follows 0 the start state Q0 0 preparation states P1a for all a E F and P2 and P3 0 reading states Rq17 where q E Q and each 17 is a length k column vector of symbols in P that may be only partially lled in writing states Wr m where r E Q and each m is a k x 2 array where the rst entry in each row is a symbol from P and the second entry is a direction in LSR Only some of ms rows may be lled in 0 head placement states Hr mi d for all r and m as in the previous item all 1 g i g k and all 1 E L R and nally halting states Qampt and 628750 1431 The Transitions of M We now describe M s transition function A from the start state onward You should draw the transition diagram from the information below The preparation phase Remember that initially M is given some input string w E 2 on its tape The rst job is to prepare the initial con guration of M along with an end marker to delineate the nonblank portion of Ms tape As usual any missing transitions are assumed to go directly to 625750 1 For all a E P set AQ0a P1aR Actually we only need to do this for all a E E U since that s all we would ever see 1 1 2 For all a E E and b E P set AP1ab P102 R where J is the multitrack symbol corresponding to an a on tape 1 blanks on all the other tapes and no scanning heads 3 Set AP1 P2 L Here J is the multitrack symbol representing all blanks and no scanning with heads 4 Set AP2A 13214 L for all A e f 7 5 Set AP2 3 P3R a a a 4 a 6 For all a E P set A P3 P3 3 L where g is the multi track symbol with a on tape 1 blanks elsewhere and all cells being scanned with heads all arrows in the rst column 1 Set AP3 R go R where l is the empty column vector of symbols no symbols lled in This ends the preparation phase Note that the current state of M is R go D which records that the current state of M is go its start state M s head is scanning the leftmost multitrack symbol just to the right of the in the leftmost cell The reading phase A state of the form Rq 17 records the current state of M as q and records the scanned symbols seen thus far in the reading phase The main simulation loop starts with state R go D which begins the reading phase and records the current state of M as go and the fact with a completely blank vector that we have not found any scanned symbols on Ms tapes yet We start moving to the right gathering information about scanned symbols We do this by setting for every nonhalting state q E Q7 gaming qmjm partially lled k vector 17 and multitrack a1 symbolA g ARq7177A Rq7 E7A7R7 where 17 is the same as 17 except that for every row 1 of A that has an arrow we ll in the empty 1th entry of 17 with ai This effectively records in Ms state the symbol being scanned on the 1th tape of M Of course if there are no arrows in A then 17 17 so we keep the same state and just move to the right When all entries of the vector 17 are lled in we have complete information about what transition M will take and we know we will not see any more arrows in the multitrack symbols so the reading phase ends Transition to the writing phase Given a reading state Rq 17 ofM where all the k entries of 17are lled in with symbols from P we make a transition to a writing state that depends on q 17 and the xed transition function 6 of M This is the only place in the simulation where we use 6 Suppose a1 that 17 g for some a1ak ET and that 6qa1ak rb1bkd1dk ak where r E Q 131 bk 6 P and 11 dk E LSR Then we set 71 d1 ARq17A W 1 g g AL bk 11k for any A E The new writing state records the output of Ms transition function 6 ie the actions to be performed on each of Ms tapes For example if d R for some i then when we nd an arrow in the ith row of a multitrack symbol we must change the corresponding P symbol to b and move the arrow to the neighboring multitrack symbol to the right The writing phase We scan M s tape from right to left altering symbols and moving arrows according to the information contained in Ms writing state Moving an arrow to the right presents no dif culty but there is a slight technical dif culty if an arrow moves to the left we will encounter that arrow again in our scan and we don t want to be confused about whether we already moved that arrow or not To deal with this whenever we perform the action on the ith tape in state Wr m we remove the entries in the 2th row of m making that row empty We then only take action on tape i if the ith row of m is nonempty This guarantees that we only act on each of Ms tapes once Let Wr m be any writing state where r E Q and m is any k x 2 array whose rst column contains symbols from P and whose second column contains directions from L S R and were some of ms rows may be empty Let A E T be any multitrack symbol and let i be least such that the ith row of m is nonempty and there is an arrow in the ith row of A If no such i exists then there is no action to be performed at this step and we just set AWr m A WU m A L Otherwise we perform the required action on Ms ith tape Let b d be the ith row of m so I E P and d E L SR There are two cases depending on whether the ith head moves or not In either case let m be m with its ith row emptied out 1 S The head does not move We set AWr m A WU m A where A is the same as A except the second entry of its ith row is b d E L R The head moves Let A be the same as A except that the arrow in thei row is removed and the second entry in the 2th row is I Set AWrmA HM m i d A 1 Head placement states The job of the head placement state Hr mi d is to place an arrow in the ith row of the multitrack symbol being scanned by M then move M s head back to where it just came from the direction opposite 1 Let 1 be the opposite of d that is d E L R 7 Note that this uniquely de nes 1 since 1 E L Let A be any multitrack symbol and let A be the same as A except that there is an arrow in the ith row of A Set AHrmidA WU m Ad There are two exceptional transitions out of Hr m i 1 One is where d R and M is scanning the regular blank symbol E P This occurs when Ms ith head moves further to the right than any of M 7s heads have moved before and thus we must lay down a new multitrack symbol increasing the range of our tape simulation In this case set AHrmiR ltWrm a where the new multitrack symbol has all blanks in the second column and a single arrow in the rst column at the 2th row The other case is where M s ith head tries to move left but can t because it is already scanning the leftmost cell of its tape We notice this when we scan the end marker In this case all we need to do is move M s head one to the right before planting the arrow Set AHr m i L HM mi L R 39 You should convince yourself that this quick x works The writing phase ends when we are in some writing state Wr m and scanning the end marker in the leftmost cell We then transition to the start of the next iteration of the simulation loop AWrm R a R for all r E Q and k x 2 arrays m This concludes the description of the writing phase and the whole simulation loop Halting transitions Finally when we are at the start of a simulation loop and we notice that M is in a halting state then we immediately halt in the same way For any 17 and A E P set ARqaccept7 17 3 Quest2pm A7 L7 ARqreject7 17 3 QTBjBCt7 A7 All this guarantees is that M will halt iff M halts and if so in the same way accepting or rejecting This is ne for language recognition and language decision but we may have reason to simulate M more closely Suppose M is being used as a transducer ie to compute a function 2 a 2 and one of Ms tapes the kth tape say is designated as the output tape which when M halts contains the output of the function being computed Our 1 tape M would then need to leave its tape contents and perhaps its head location identical to that of Ms output tape before halting I ll leave it as an exercise to add such an output preparation module to M Exercise 144 Modify the machine M above so that if M halts M halts with its tape contents and head location identical to Ms kth tape This completes the description of M 15 3172008 151 Nondeterministic Turing machines Nondeterministic TMs NTMs as opposed to DTMs analogous with NFAs transition function gives a set of possible actions Nondeterministic computation best viewed as a tree nodes con gurations root is start con guration Machine accepts if there is some computation path that leads to the accept state Theorem 151 For euery NTMN there is an equivalent DTM D 239e such that LD Proof idea D uses breadth rst search on N 7s tree why not depth rst search7 Three tapes for D tape 1 always contains the input and is never altered tape 2 maintains a copy of N s tape contents on some branch of its computation tree and tape 3 keeps track of D s location in N s tree speci ed by a sequence of numbers in 1 b where b is the maximum branching of N Tape 3 cycles through all sequences in length rst lexicographical order For each sequence7 the corresponding branch of N s computation branch is simulated using tape 2 from the beginning for as many steps are there are elements of the sequence We accept if we ever notice that N reaches an accepting con guration An NTM is a decider iff it halts on all branches on all inputs Konig s Lemma implies that the whole computation tree is nite for any input NTMs are equivalent to DTMs at deciding languages 15 2 Enumerators De ne enumerators A language is r L aka enumerator enumerates it L iff some 111 L1 Theorem 152 A language is Turing 39 l it is p Proof First the forward direction Suppose A Q 2 is a T recognizable language Let M be a TM recognizing A A Let E be an enumerator that runs as follows For all strings z in length rst lexicographical order H If x is not of the form w t where w E 2 and t E N then go on to the next m to Otherwise7 z w t for some w E 2 and t E N Run M on input w for t steps or until M halts7 whichever comes rst 03 If M accepts w within t steps7 then print w q Go on to the next m Note that E spends a nite amount of time with each string m so it manages to cycle through all possible strings We need to show that E prints a string w iff w E A E prints a string w only if it notices that M accepts w7 and thus w E LM A Conversely if w 6 A7 then M accepts w after some nite number of steps t Letting z mt7 we see that when E gets to the string x it will run M on w for t steps7 notice that M accepts w7 then print w This shows that E enumerates A7 and so A is computably enumerable For the reverse direction7 suppose that A is enumerated by an enumerator E Let M be a TM implementing the following algorithm On input w E 2 1 Run E inde nitely lf w is ever printed7 then accept77 Clearly7 M accepts exactly those strings that are printed by E7 and thus LM A Therefore7 A is T recognizable El Here s another way to look at T recognizability Theorem 153 A language A Q 2 2395 Turing recognizable l either A 0 or A is the range of a computable function Recall that the range of a function is the set of things that are actually output by the function on some input Proof gt Let A LM for some TM M If A Q we re done so assume A 7 Q and x an element mo 6 A our fall back string Let f be the function computed by the following algorithm On input z 1 If x is not of the form w t for some w E 2 and t E N then output mo and halt 2 Otherwise z ltwtgt Run M on input w for up to 25 steps 3 If M accepts w within 25 steps then output w and halt 4 Otherwise output mo and halt77 Clearly 1 either outputs 0 or some element w accepted by M Thus 1 only outputs strings in A To see that all strings in A are output by 1 let w E A be arbitrary Since A LM M accepts w after some nite number of steps 25 But 1 is de ned so that fltwt gt w for any 25 2 25 So w is in the range of f This concludes showing that A is the range of f lt Suppose that A is either empty or the range of a computable function 1 We want to show that A is T recognizable The empty set 0 is recognized by a TM de ned as follows On input w 1 Reject77 Now assume A is the range of computable 1 Let E be an enumerator that runs as follows For every string z 1 Compute y 2 Print y Clearly E enumerates the range of 1 which is A so A is computably enumerable and hence T recognizable D 16 3192008 161 The ChurchTuring Thesis Lots of different mathematical models of computation were developed in the rst half of the 20th centuryiwell before the advent of electronic computers There are TMs of various sorts Alan Turing 1936 the calculus Alonzo Church 1936 Post production systems Herbrand Godel Kleene systems Kleene s six schemata combinatory logic etc With electronic computers have come various reasonable general purpose programming languages that can also be described for mally as models of computation Fortran C Perl C Ruby ML Java Haskell etc as well as theoretical models that closely mimic the behavior of typical hardware the RAM model random access machine All these models are equivalent describing exactly the same class of algorithms because they all can simulate each other It was Turing who really discovered this showing that his Turing machines could simulate and be simulated by all the other models that existed at the time Before that it was not at all clear that these models were equivalent or which was the right model of computation Unlike the other models at the time which could be quite abstract Turing 42 machines had a clear down to earth physically intuitive semantics that made them a convincing model of computation The existence of a universal Turing machine also leant much credibility to the following principle ChurchTuring Thesis All these equivalent formal de nitions precisely capture the intu itive or even physical notion of an algorithm Further evidence lots of attempts to strengthen the TM model more tapes multidimensional tapes several heads etc don t provide any additional power ie they don t make things com putable that weren t before with regular TMs Similarly attempts to weaken TMs restricting head movements what can be written etc either lead to ridiculously and obviously weak models of computation or else give the same power as the original TMs The difference is never subtle One of my favorite examples Read only TMs with two auxillary blank tapes with end markers This is just as powerful as the original TM model Data for intermediate calculations is stored in the positions of the auxillary heads which must move out doubly exponentially far in the number of steps of the standard TM being simulated If you only have one auxillary tape then such a device is so weak that it cannot even recognize some simple context free languages These results date back to the early 1960s Each blank tape acts like a counter that holds a natural number corresponding to the head position A counter can be incremented decremented left alone and tested for zero These machines are also called two counter automata All computational models that are equivalent to Turing machines are said to be capable of universal computation Here are some more models of universal computation some rather exotic Boolean circuits directed acyclic graphs with nodes labeled with Boolean operators such as AND OR or NOT These are appealing because they can closely mimic actual hardware Issue a single Boolean circuits can only take inputs of some xed length for universal computation one must take a uniform family of circuits one for each input length there are various ways one can de ne uniform here Type 0 unrestricted grammars These form one of the levels of the Chomsky hierarchy Tag systems These describe processes by which a FIFO queue is modi ed in a simple way 0 John Conway s Game of Life This is a speci c two dimensional two state cellular automaton meant to crudely simulate the behavior of bacteria in a Petri dish Rule 110 This is a speci c very simple onedimensional two state cellular automaton conjectured by Stephen Wolfram and proved by Matthew Cook around the year 2000 to be universal brainfk pardon the bowdlerization This is an extremely simple programming language that has an extremely tiny interpreter It is universal but almost unreadable and very inef cient Emphasis switches from TM to algorithm Three levels of description formal TM implemen tation level informal TM and high level algorithmic Two current research papers of ours both mostly accessible 0 The complexity of nding SUBSEQA77 http www cse sc eduquotfennerpapersfindingsubseq pdf 43 o The complexity of learning SUBSEQA77 http www cse sc eduquotfennerpaperslearningsubseqpdf 162 Chapter 4 Decidable languages The acceptance problem for DFAsigiven a DFA B and a string w does B accept w77can be encoded as the following language ADFA ltBw l B is a DFA accepting w ADFA is decidable via TM M lmplementation details with multitape machine write description of B on separate work tape keep track of current state on another work tape Read the input w as B would read it ANFA the acceptance problem for NFAs is de ned analogously It is decidable via TM N using M as subroutine On input ltBw N rst converts B into an equivalent DFA C then runs M on C w The acceptance or matching problem for regular expressions AREX ltRw l w matches regexp R is decidable Convert B into an equivalent NFA B Thm 128 is e ective ie algorithmic or computable then run N on input ltB w The emptiness problem for DFAs EDFA l A is a DFA and LA 0 is decidable Search from start state of A for a nal state T On input A where A is a DFA 1 Mark the start state of A 2 Repeat until no new states get marked a Mark any state that has a transition coming into it from any state that is already marked 3 If no accept state is marked accept else reject77 The equivalence problem for DFAs EQDFA ltA B l A and B are DFAs and LA LB is decidable Construct DFA C recognizing the language LAALB Run T on input LA L is the symmetric di erence of L and L de ned as L 7 L U L 7 ENFAEREXEQNFAEQREX are de ned analogously and are all decidable But think about how to decide these more ef ciently than just converting everything to DFAs which can be expo nentially large compared with the original NFAs or regexps Regular gt decidable gt Turing recognizable We know the rst gt is strict What about the last one 163 An undecidable language The Halting Problem 42 The acceptance problem for TMs is ATM ltMwgt M is a TM that accepts string w Proposition 161 ATM is Turing recognizable Proof Recall the universal Turing machine U On input M w where M is a TM and w is a string 1 Simulate M on input w 2 If M ever enters its accept state accept if M ever enters its reject state reject77 Clearly by its de nition ATM LU and thus ATM is T recognizable D U loops on ltMwgt iff M loops on w so U does not decide ATM If U had some way of nding out that M would not halt on w then it could reject Theorem 162 ATM is undecidable Proof The proof uses the diagonalizatz39on method Georg Cantor 1873 the same method used to prove that there are uncountably many reals etc We ll skip over this mostly Assume for the purposes of contradiction that there is a TM H that is a decider for ATM That is for all TMs M and strings w M accepts w gt H accepts ltMwgt M does not accept w gt H rejects ltMwgt Let D be the following machine D On input where M is a TM 1 Run H on input ltM until it halts 2 If H accepts ltM then reject else accept77 Thus for every TM M o D accepts if M does not accept o D rejects ifM accepts Now suppose we run D on input Substituting D for M above we have 0 D accepts ltDgt if D does not accept D o D rejects ltDgt if D accepts Clearly this is impossible Therefore no such machine H exists and thus ATM is undecidable D The proof of Theorem 162 as well as being an example of diagonalization uses a paradox of future forcasting You cannot reliably fortell the future to someone who has the ability to change it D when run on input D is able to ask the fortune teller H Will I eventually accept That is D on input D asks H whether or not the computation D on input D will eventually accept H must commit to an answer in a nite amount of time whereafter D just does the opposite of what H predicts making H wrong for this computation at least Corollary 163 ATM is not Turing recognizable Proof We know that ATM is T recognizable lf ATM were also T recognizable then ATM would be decidable by Proposition 143 but this is not the case by Theorem 162 1 The halting problem is de ned as the language HALTTM Mw l M is a TM that halts on input string w 17 3242008 171 Reducibility Chapter 5 lnformally a problem A reduces to a problem B if you can easily solve A given a solution for B If A and B are computational problems then A reduces to B means that there is an easy way to transform a given instance of A into one or more instance of B so that given solutions to those instances of B one can easily solve the original instance of A A reduction from A to B says that in some sense A is no more dif cult to solve than B or equivalently that B is at least as dif cult as A In particular if A and B are languages and A reduces to B then if B is decidable then so is A and equivalently if A is undecidable then so is B Our most common method of showing a language to be undecidable is to reduce some previously known undecidable language to it There are many different kinds of reductions The most general kind that we will see is a Turing reduction A Turing reduction from language A to language B is an algorithm that decides A by using answers to questions about membership in B for free De nition 171 Let B be any language A Turing reduction to B is an algorithm that at any point may include a test of the form lfw E B then where w is some string prepared by the algorithm Furthermore assuming the tests are always answered truthfully the algorithm halts either accepts or rejects on all inputs A Turing reduction to B is also called a decision procedure that uses or queries oracle B We think of B as a black box or oracle that we can feed strings queries to and it will say yes or no according to whether or not the string is in B The de nition says nothing about whether B is decidable ie whether the black box can be replaced by an actual algorithmic decision procedure for B as a subroutine If R is a Turing reduction to B we de ne the language decided by R with oracle B as you d expect the set of all strings accepted by R We won t go into details here but a Turing reduction can be modeled formally by an oracle Turing machine OTM An OTM is a Turing machine equipped with an extra readwrite tapei its oracle query tapeiand three specially designated states q7 the query state ayes the yes 46 answer state and qm the no answer state Given some language B Q 2 the OTM computing on input string iv with oracle B acts just like a regular multitape TM with input w except that at any point during a computation the OTM may enter the state q7 with some string z E 2 sitting on the oracle query tape Then in one step the machine either enters state qyes if z E B or enters state qm if z B Nothing is written and the heads don t move in this step In this way the OTM can ask a membership question to the oracle and receive the answer in its state The computation of the OTM with oracle B may loop on some input in which case the OTM does not compute a Turing reduction to B Note that an OTM can be described as a nite object independent of any oracle it computes with but any computation of the OTM may vary depending on the oracle If M is an OTM and B is a language we may write MB for the machine M equipped with oracle B This leads to de nitions of OTMs analogous to regular TMs eg LMB is the language of all input strings accepted by MB MB is a decider ie Turing reduction to B iff it halts on all input strings etc De nition 172 Let A and B be languages We say that A Turing reduces or T reduces to B denoted A 1 B if there is a Turing reduction oracle Turing machine that decides A using oracle B We may also say that A is decidable in B or decidable relative to B in this case Let A B and C be any languages Here are some easy but important facts 0 A 1 A gT is re exive o If A 1 B and B is decidable then A is decidable o If A 1 B and A is undecidable then B is undecidable this follows from the previous statement by pure logic o If A 1 B and B 1 C then A 1 C gT is transitive This relativizes the previous item to oracle C replacing decidable77 with decidable in C77 Use T reducibility to show the undecidability of HALTTM ETM HELLO WORLD REG ULARTM EQTM The second and third require an algorithm to produce the description of a Turing machine More on that later 18 3262008 Another fact about Turing reducibility Easy Fact 181 A 1 A for any language A Proof Given A here s the Turing reduction On input w 1 If w E A then reject else accept77 El Let s apply this with A ATM Then m 1 ATM Recall that ATM is Turing recognizable but ATM is not Thus Turing reductions do not preserve Turing recognizability although they do preserve decidability We now introduce a more restricted reduction that preserves both decidability and Turing recognizability 181 Mapping reducibility De nition 182 Let A7 B Q 2 be languages We say that A is mapping reducible to B or that A is m reducible to B A gm B if there exists a computable function f 2 a 2 such that7 for all w E 2 w E A ltgt fw e B We also say in this case that f is a mapping reduction or m reduction from A to B7 and that f mapping reduces or m reduces A to B A mapping reduction 1 provides a more restrictive special case of a Turing reduction It only applies to decision problems encoded by languages7 where a given instance w of a decision problem A is transformed into a single instance fw of the decision problem B with the same answer Easy Fact 183 Let A and B be languages IfA gm B then A 1 B Proof Let f m reduce A to B Then the following oracle algorithm T reduces A to B On input w 1 Compute z fw 2 If x E B then accept else reject77 Since w E A iff z 6 B7 this correctly decides A with oracle B 1 Since m reducibility implies T reducibility7 it preserves decidability7 ie7 if A gm B and B is decidable7 then A is decidable The same is true for Turing recognizability unlike with T reductions Proposition 184 Let A and B be languages IfA gm B and B is Turing recognizable then A is Turing recognizable Proof Suppose that f m reduces A to B and that B LM for some TM M Let N On input w 1 Compute z fw 2 Simulate M on input z and do whatever M does77 Clearly7 for any input string u7 N accepts w iff M accepts fw iff fw E B iff w E A Thus A LN and so A is Turing recognizable El We ll use this fact in the contrapositive to show that various languages A are not Turing recognizable7 usually by showing that ATM gm A For if this is the case7 then A cannot be T recognizable otherwise7 ATM would be T recognizable7 which we know is not true Another consequence of Proposition 184 is that ATM n ATM This is because the right hand side is Turing recognizable7 but the left hand side is not Most of the Turing reductions we built to show the undecidability of various languages above can be turned into m reductions Proposition 185 ATM gm ETM Proof This works as before except that we output the machine R explicitly as the value of the function Fix the TM M0 On input w reject77 Clearly LM0 2 and so Mo 6 ErM7 or more to the point M0 ETM Let the function f be computed as follows 1 On input x 1 If x is not of the form M w where M is a TM and w is a string then output M0 and halt 2 Otherwise we have x M w where M is a TM and w is a string Extract M and w from x 3 Let R On input x a Run M on input w and do whatever M does77 4 Output 13 Note that R ignores its own input so if M accepts w then LR 2 and otherwise LR 0 We show that f m reduces ATM to ETM Evidently f is computable Let x be any string We need to show that x 6 ATM ltgt x 6 First suppose x is not of the form M w for some TM M and string w Then x ATM and x M0 ETM so that s ok Now suppose that x ltMw for some TM M and string w Let x R for TM R as above We have M w 6 ATM ltgt M accepts w ltgt LR 7 0 ltgt R 6 EM So in all cases x 6 ATM ltgt x 6 ETM so 1 m reduces ATM to ETM El Easy Fact 186 IfA gm B then X gm F Proof If f m reduces A to B then the same 1 m reduces Z to F Why For all x xEA ltgt x B zi A ltgt fx B x61 ltgt xe Applying this to the reduction we just did we see that ATM Sm ETM Em and it follows that ETM is not Turing recognizable 49 Exercise 187 Show that ETM is in fact Turing recognizable So far the only non T recognizable languages we ve seen are complements of T recognizable languages Now we ll see a language such that neither it nor its complement is Turing recognizable The equivalence problem for Turing machines is encoded by the language EQTM M N l M and N are TMs and LM LN We show rst that ETM gm EQTM Since ATM ltIn ETM we know that ETM is not Turing recognizable so m reducing ETM to EQTM will show that the latter is not T recognizable either Recall the TM M0 recognizing Q from above De ne M1 On input w accept77 Clearly LM1 2 For this m reduction we use the fact that a TM recognizes 0 just in case that it is equivalent to M0 Let f On input z 1 If x is not of the form for any TM M then output M0 M1 2 Otherwise z where M is a TM Output ltMM0gt77 Clearly f is computable For any TM M we have M 6 EM ltgt LM 0 ltgt LM LM0 ltgt ltMM0gt e EQTM ltgt fltMgt E EQTM The exceptional case where the input to 1 does not encode a TM is handled in Step 1 Thus 1 m reduces ETM to EQTM Now we show that m gm EQTM or equivalently ATM gm EQTM Like the previous reduc tion this one does not need much effort Recall the computable function 1 de ned in the proof of Proposition 185 For any input m it was the case that 1 output the encoding of some TM R such that mEATM gt LRE m ATM gt LR Thus z 6 ATM iff LR 2 in other words z 6 ATM iff R is equivalent to M1 Now let 9 On input m 1 Compute R 2 Output ltRM1gt Clearly g is computable and z 6 ATM iff gz E EQTM Thus ATM gm EQTM via 9 50 182 Linearly Bounded Automata A linearly bounded atomaton LEA is a kind of onetape Turing machine where the tape is nite for each input having just enough cells to contain the input string Otherwise the machine can read and write cells change state move the head and enter halting states just as with a regular TM except that now if the head tries to go off of either end of the tape it stays put instead Since the tape alphabet can be larger than the input alphabet but still constant size the machine can store a constant number of bits of information in each cell and thus its memory is limited to growing linearly with the input size Exercise 188 With a regular TM we saw that you can add an end marker to the beginning of the tape Show how an LBA can do the functional equivalent of adding two end markers to each side of the input Let ALBA ltMw l M is an LBA that accepts string w Proposition 189 ALBA 239s decidable Proof Let q la and g There are exactly qng possible distinct con gurations of M for a tape of length 71 Run M on input w for qng steps where n or until it halts If M has accepted then accept else reject This works because if M does not halt within qng steps then it must repeat a con guration and thus loop forever not accepting D 19 3312008 Let ELBA l M is an LBA and LM 0 Proposition 191 ELBA 239s undecidable In fact ELBA is not T recogm39zable Proof Mapping reduction from m using computational history method let 1 On input M w where M is a TM and w is an input string 1 Construct an LBA BMW that accepts an input string z iff z is the complete history of an accepting computation of M on input w ie 90 C102 Ck where the C are the successive confugurations of M on input w B On input z a B can nd Cl Ck when necessary using the delimiters b Check that 01 is the start con guration of M on input w that is 01 qow c Check that each CH1 legally follows from C in one step by the rules of M d Check that Ck is an accepting con guration that is Ck gammy 7 51 2 Output BMW77 Tape alphabet is Q U P U where P is the tape alphabet of M Assume these sets are disjoint D If you re still uncomfortable with algorithms that output other algorithms in the form of descriptions of TMs then it may help to know that all such constructions are just applications of the following general theorem which is also called the s m n Theorem for historical reasons Theorem 192 Parameter Theorem There is a computable function 3 2 a 2 such that for any TM M and string w sMwgt R where R is a TM which on any input string m behaues the same as M on input w Intuitive explanation Proof Application to m reduce ATM to ETM bar 20 422008 Midterm ll Chapters 345 21 472008 Two exercises that will be useful later on Exercise 211 Show that a language A is Turing recognizable iff there is a decidable D such that for all strings w w e A ltgt Hz wzgt e D A language that satis es the part after the iff77 is called 21 Thus the exercise is to show that being Turing recognizable is the same as being 21 lntuition lf w E A then there is some string x that acts as a proof or witness that w E A The proof is veri ed algorithmically by the decider for D If w A then there is no proof and the veri er can never be fooled into accepting Do the exercise Exercise 212 Show that if A is Turing recognizable then A gm ATM The converse of this is true easy so we have A is Turing recognizable iff A gm ATM So these exercises give us two more characterizations of Turing recognizability Do the exercise This is the easiest m reduction you ll see 211 Time Complexity Chapter 7 We haven t cared about ef cient use of resources so far We should care because there are decidable problems that cannot be decided ef ciently For such problems nding solutions for large inputs is possible in principle but not in practice because it wouldjust take too long Whereas computability categorizes problems by decidabilityundecidability computational complexity theory categorizes decidable problems by feasibilityinfeasibility It gives a ner classi cation within the realm of decidable languages Two standard measures of resources time and space there are others Time is the number of steps of a Turing machine before it halts space is the maximum rightward extent of the head during the computation Review big O and big 9 notation and de nitions We only care about time and space resources up to asymptotic equivalence big 9 Useful fact lfp N a N is given by a polynomial of degree d 2 0 then pn 90 Example 1 tape TM deciding 0 1 n 2 0 in 2n2 nZ steps Takes linear time on a 2 tape machine ls there a faster 1 tape algorithm Yes nlgn and this is asymptotically optimal for a 1 tape machine De nition 213 Let t N a N be a function and let M be a Turing machine that halts on all inputs We say that M has time complexity t or that M runs in time t if for every n E N tn is the maximum number of steps that M takes to halt on any input string of length n TlMEt is the class of all languages that are decidable in time Ot ie that have deciders running in time All measures of complexity are taken with respect to the length of the input and we will only consider worst case complexity We really only care about time complexity up to a polynomial De ne f Poly9 We say that a TM runs in polynomial time if its running time is bounded from above by some polynomial in the length of the input In this case the number of Turing machine tapes does not matter since a k tape machine running in time t can be simulated by a 1 tape machine running in time 0t2 provided t 2 n where n is the length of the input Functions that are not polynomially bounded include exponentially growing functions such as fn 2 212 The class P De nition 214 P is the class of all languages that are decidable in polynomial time ie P TlMEPolyn U TIMEnk kgt0 22 492008 We take P to capture the intuition of ef ciently decidable languages Examples of languages in P PATH eg BFS REL PRIME eg Euclidean Algorithm PRIMES not obvious only known since 2002 ADFA EDFA and ENFA both applications of PATH ANFA How Constructing the equivalent DFA like we did before make take too long exponential time but there is another way only construct the path taken by the DEA on the input string w There are languages that can be decided in exponential time but not polynomial time ie not in P Draw a Venn diagram of classes seen so far 221 The class NP P is the class of languages where membership can be decided efficiently polynomial time NP which stands for nondeterministic polynomial time is the class of languages where membership can be veri ed in polynomial time De nition 221 NP is the class of all languages A for which there is a polynomial p and Turing machine V the veri er such that for all input string w w E A ltgt 3mV accepts input wz and Vw halts in at most plwl steps If there exists such a string m then we call x a proof or witness that w E A The veri er V must run in time polynomial in lwl which is stronger than merely requiring that V just run in polynomial time in the length of its input This prevents V from being able to spend a long long time verifying a long long proof V only has time to view the rst many symbols of the proof string x at most so if there is any proof x that w E A there must exist a proof that is reasonably short Polylwl This gives a slightly alternate de nition of NP Proposition 222 A language A is in NP if and only if there is a polynomialp and a language D E P such that for all strings w w E A ltgt plwl amp wx E D Thus we can explicitly require the proof string to be reasonably short Notice how similar this is to the exercise that shows that T recognizability is the same as 21 Here we just have polynomial bounds of the length of the proof and the time taken to verify it Indeed NP is sometimes denoted 21 Examples CLIQUE COMPOSITES Discussion How about verifying nonmembership coNP Discussion Clearly P Q NP the veri er ignores the proof and just runs the decider ls it the case that P NP This is a celebrated and important open problem in mathematics and computer science 23 4142008 231 Polynomial reductions and NPcompleteness NP contains loads of problems of wide interest to many elds scheduling routing partitioning constraint satisfaction graph coloring etc We want to classify these problems with regard to feasibility We use a polynomially bounded version of the mapping reduction De nition 231 FP Polynomial mapping reduction Basics Re exive transitive If A g3 B then NP completeness An NP complete set K In the exercises the book denotes this set U 24 4162008 241 Boolean formulae and satis ability A Boolean formula is an expression made from Boolean variables m yz binary in x Boolean connectives A AND V OR and the unary pre x NOT Boolean variables can be assigned the values 0 FALSE or 1 TRUE and if some truth value ie TRUE or FALSE is assigned to each variable in a formula then the truth value of the formula is determined in the usual way For example let 4p be the formula LpzvyAEVszA Give some sample values for m y 2 When is 4p true A truth assignment of 4p is some setting of values for the variables in 4p and this will make 4p either TRUE or FALSE Computing the truth value of 4p given a truth assignment of its variables is an easy bottom up tree traversal which takes no more than quadratic time thus polynomial time A Boolean formula 4p is satis able if there is some truth assignment to the variables occuring in 4p that makes 4p true Is the formula 4p above satis able7 Such an assignment is called a satisfying assignment A natural interesting and fundamental computational decision problem in logic is given a Boolean formula is it satis able This is called the SATlSFlABlLlTY problem and as usual we can encode it as a language SAT 4p is a satis able Boolean formula Clearly SAT 6 NP Why If 4p is satis able then an easily checkable proof of this would be an actual satisfying assignment which you can check in polynomial time We will only worry about Boolean formulae that are in conjunctiue normal form CNF A formula 4p is in CNF iff it is the conjunction of clauses LpClACZAACk where each clause C is a disjunction of literals Ci 1 V 6132 V V Ziji where each literal is either a variable or the negation of a variable t z or t E for some variable m It is customary in computer science to write a negated variable x as E instead of x The formula above is in CNF The language CNF SAT is the restriction of SAT to CNF formulae CNF SAT 4p is a satis able CNF formula Today we ll prove the Cook Levin Theoremiarguably the most important theorem in complex ity theory Theorem 241 Cook Levin CNF SAT is NP complete Proof We already know that CNF SAT E NP just as SAT 6 NP It remains to show that CNF SAT is NP hard We ll do this directly Let B be any language in NP We show that B 31 CNF SAT Let V be some veri er for B such that Vwz runs in at most plwl steps p is some polynomial and w E B iff 3mV accepts w Given a string w we will to construct in polynomial time a Boolean formula W in CNF such that w E B ltgt W is satis able The map w H W will then be a ptime m reduction from B to CNF SAT which nishes the proof Basically the formula W says that Vw accepts for some string m The variables of W will encode an entire computation of V on some input The variables will make em if and only if they encode an accepting computation of V on input w z for some m Now the details Let V Q E P 6 go quwept qm39m V is a standard 1 tape TM Fix a string w E 2 and let w wl 10 where each w E 2 so 71 For technical convenience we will make some assumptions 0 for any string m w z is always encoded as the string wz where E E are two special symbols neither 39 nor occurs in w or in z 0 V never overwrites with another symbol 0 V never writes 39 anywhere else on the tape and 0 V never attempts to move left when scanning These assumptions do not place any undue hardship on V The entire computation of V on some input wm can be described entirely with a two dimensional grid a tableau The vertical axis represents the time step t 012 and the horizontal axis represents the tape contents cell 0 1 2 Since V halts within p pn steps we only need to make the tableau p 1 x p 1 So time runs from 0 to pn inclusive and the only tape cells that can ever be scanned in this time are cells 0 through Here are the variables of W They come in three types 0 sq for all 0 g t g p and all q E Q 3 1 means V is in state q at time t 0 ma for all 0 it p and all a E P Cell i contains symbol a at time t 0 71 for all 0 it p V s head is scanning cell i at time t W contains clauses ensuring that 1 V is in exactly one state at any time 2 Vs head is in exactly one place at any time 3 each cell has exactly one symbol at any time 4 the initial conditions are correct 5 V enters qampt at some point in time 6 the con guration at time t 1 is the legal successor to the con guration at time 257 for all 0 tltp We ll construct these clauses in order 1 to 03 q 5 For each 0 g t g 197 add the clause qEQ V is in at least one state at time t 7 and for each q7 r E Q with q 7 r add the clause g V W V is not simultaneously in state q and r at time t For each 0 g t g 197 add the clause 17 V 7H i0 V s head is in at least one position at time t 7 and for each 0 g i lt j g p add the clause W V W V s head is not simultaneously scanning cells i and j at time t V mt1it 161quot Cell i contains at least one symbol at time t 7 and for each 011 6 P with a 7 b7 add the clause For each 0 g at g 197 add the clause 90 V 901213 Cell i does not simultaneously contain symbols a and b at time t Add the following clauses 0 qugt0 V is in the start state at time O 7 o h0gt0 V s head is scanning cell 0 at time O 7 o m00 Cell 0 contains 39 at time O 7 o mwbho for each 1 g i g 71 Cells 1 through 71 contain w at time O 7 mn10 Cell 71 1 contains at time O 7 o Vaeltziui mime for all n 2 g i g p Cells 71 2 through p either contain blanks or symbols in 2 except or at time 07 0 WV 4119 for all n 2 g i lt p At time 07 starting at cell 71 27 no blank cell can be followed by a nonblank cell immediately to its right Add the clause F V Sqaaa ptt O t V enters qawept at some time 25 between 0 and p 57 6 We add two types of clauses clauses ensuring that an unscanned symbol remains unaltered in the next time step and ii clauses ensuring that the correct symbol is written the head moves properly and the state changes correctly based on the current state and the scanned symboliall according to the transition function of V For i for each time 0 g t lt p cell 0 g i g p and symbol a E P we add a clause that says At time t if the head is not scanning cell i and cell i contains a then cell i contains a at time 25 177 This can be schematized as hi A u H u17 1 where a is the if then conditional A standard rule of propositional logic says that P a Q is equivalent to F V Q for any propositions P and Q Thus 1 becomes hi A u V u17 which becomes using DeMorgan s Laws hi V V u1 This clause has the right syntactic form so we add it to W for each time 0 g t lt p cell Ogigp and symbol a E P For ii we add the following clauses for each state q E Q and symbol a E P Suppose 6qa rbd for some r E Q I E P and d 6 LR Then for each time 0 g t lt p and cell 0 g i g p we add the two clauses hi A u A Sq Srt1 hi A u A Sq H u1 If at time t the head is scanning cell i which contains symbol a and V s state is q then at time t 1 the ith cell contains 1 and the new state is r Using transformations similar to before we actually add the following equivalent clauses which have the right syntax E V myt V V 3rt17 hi V u V Sq V 95b1 It remains only to add clauses describing the head movement There are two cases olfdLthenforall0gtltpand0lti paddtheclause hi V u V V hi41 If at time t the head is scanning cell i gt 0 which contains symbol a and V s state is q then at time 25 1 the head is in position if 1 Notice that we do not need to worry about i 0 because we are assuming that V never tries to move left when scanning the symbol which is in cell 0 olfdRthenforall0gtltpand0 iltpaddtheclause 7H V 90w V V hi1t1 If at time t the head is scanning cell i lt p which contains symbol a and V s state is q then at time 25 1 the head is in position i 7 1 By our construction of it W is evidently satis able if and only if there is a string x such that V accepts ltwzgt wz 25 4212008 251 CLIQUE is NPcomplete Once we showed that ATM was undecidable showing other languages undecidable became easier because it only sufficed to reduce ATM to them Something similar is going on here with the Cook Levin Theorem regarding CNF SAT This theorem makes our job of showing other problems NP hard much easier since it suffices to reduce CNF SAT to them in polynomial time This technique of showing problems NP complete by reducing known NP complete problems to them is widely applicable and has proved hundreds of computational problems from various elds of science engineering and mathematics to be NP complete or at least NP hard and thus intractable unless P NP We ll illustrate this technique here with a single example Theorem 251 CLIQUE is NP complete Proof First CLIQUE E NP as we discussed earlier Next to establish that CLIQUE is NP hard we show that CNF SAT g3 CLIQUE Recall that a literal is either a Boolean variable or the negation of a Boolean variable We say that two literals are contradictory if one is a variable and the other is the negation of the same variable Note that two literals are contradictory iff they have opposite truth values in any truth assignment To ptime m reduce CNF SAT to CLIQUE we describe how to map in ptime any CNF Boolean formula 4p to a string G k where G is a graph and k E N such that 4p is satis able iff G has a clique of size k If the input string does not encode a CNF formulaisomething we can easily check in ptime by looking at its syntaxithen we map it to some trival string in CLIQUE Let 4p be any CNF formula Then LpClAACm where each clause C is a disjunction of literals We map 4p to C m where m is the number of clauses of 4p and G is the following graph 0 The vertices of G are all the literal occurrences in 4p If the same literal occurs several times in 4p then each occurrence counts as a separate vertex of G c We put an edge between every pair of vertices of G except vertices corresponding to literals occuring in the same clause and ii vertices corresponding to contradictory literals This completes the description of the reduction It remains to show that this construction is ptime and that 4p is satis able iff G has a clique of size m Given 4p we can clearly construct Gm in polynomial time there is really nothing more to say about this Now suppose rst that 4p is satis able Let a be a satisfying assignment of 4p For each of the m clauses Cl Cm choose some literal made true by 71 These in literals form a clique because they all occur in distinct clauses and no two can be constradictory since they are all true Thus G has a clique of size m Conversely suppose that G has a clique C Q VG of size m Notice rst that no two literals in C can be from the same clause since no two literals from the same clause are adjacent So all the vertices of C must be from different clauses of 4p and since there are exactly in clauses C much include exactly one literal from each clause Now since no two literals of C are contracdic tory because they are adjacent there is a truth assignment a that makes all literals in C true simultaneously But then a makes at least one literal true in each clause of 4p and thus a makes 4p true This shows that 4p is satis able This completes the proof 252 Space complexity Chapter 8 The space used by a TM M on some input is the maximum 3 such that Ms head scans cell 3 on at least one of its tapes at some point in the computation We can then de ne space complexity just as we de ned time complexity The space complexity of M is as a function of n E N the maximum space used by M on all inputs of length n For 3 N a N we de ne SPACEs to be the class of all languages decided by TMs with space complexity 05 Assuming sn 2 n the class SPACEs is the same whether we use single tape or multitape TMs because we can simulate a multitape TM with a singletape TM that uses no additional space although it uses a bigger tape alphabet Analogously with P we de ne the class polynomial space as PSPACE U SPACEnk SPACEPolgn kgt0 PSPACE contains all those decision problems that are decidable using a reasonably modest77 amount of memory Space complexity has some characteristics similar to time complexity However spacebounded machines can apparently do more than similarly timebounded machines can The intuitive reason for this is that limited space can be reused over and over again whereas limited time cannot Recall that a natural way to de ne the exponential time complexity class is EXP U TIME2 k TIME2P 7M kgt0 Here s a basic proposition relating time and space complexity classes Proposition 252 P Q NP Q PSPACE Q EXP It is known that P 7 EXP but none of the other containments above are known to be proper It is widely believed however that they are all proper We ve already seen that P Q NP To see that NP Q PSPACE just notice that given an NP style veri er a polynomial spacebounded machine can cycle through all possible proof strings and simulate the veri er on each one If the veri er is seen to reject a proof the pspace simulator erases the computation and tries the next proof This takes a long time exponential time but only polynomial space because it only needs to store the veri er s computation for one proof at a time To see that PSPACE Q EXP we use the same con guration counting technique that we used to show that ALBA is decidable A TM using space 3 must always be in one of only 209 many possible con gurations The constants hidden in the big O depend on the size of the tape alphabet the number of tapes and the number of states If the machine takes longer than this for some computation then it must repeat a con guration and hence run forever contradicting our general assumption that it is a decider Therefore a machine using space Polyn and halting on all inputs must run in at most 2730M time 253 Savitch s Theorem Probably not enough time for this 254 PSPACEcompleteness PSPACE hardness and PSPACE completeness for a language are de ned entirely analogously to the case of NP A language A is PSPACE hard under p m reductions if B 3 A for every B E PSPACE If a PSPACE hard language is itself in PSPACE then we say that is is PSPACE complete PSPACE has complete languages and we ll see one shortly Since NP Q PSPACE every PSPACE hard language is also NP hard Since this containment is most likely proper we d expect PSPACE complete languages to be harder than merely NP complete languages We ll describe a language now that bears some resemblance to to CNF SAT but it is PSPACE complete instead of NP complete Given a Boolean formula 4p not necessarily in CNF we can quantify any or all of its variables with either 3 there exists or V for all The former is called existential quanti cation and the latter is called universal quanti cation Let 4p be a Boolean formula and let u is some Boolean variable which may or may not occur in 4p Let p0 be the formula resulting from 4p by replacing all occurrences of v in 4p with the constant 0 FALSE Similarly let p1 be the formula resulting from 4p by replacing all occurrences of v in 4p with the constant 1 TRUE Thus 1 occurs neither in p0 nor in p1 although both of these may contain other Boolean variables The existentially quanti ed Boolean formula 3W7 is then equivalent to p0 V p1 It says in effect that there exists a truth value of U such that 4p Likewise the universally quanti ed Boolean formula WW is equivalent to p0 A p1 It says that for each truth value of u it is the case that Lp The truth values of these two quanti ed formulae depend in general on the other variables occurring in them We can add several quanti ers in a row quantifying over different variables For example let 4p be the quanti ed formula megwarm 2 A 25 VEVE A i v 2 61 has all its variables quanti ed over7 so its truth value does not depend on anything7 ie7 it is either true or false outright which A quanti ed Boolean formula with all its variables quanti ed is called a closed formula Closed formulas are either true or false per se Here7 then7 is our rst PSPACE complete language De nition 253 The language TQBF is de ned as TQBF 4p l 4p is a closed formula that is true TQBF stands for True Quanti ed Boolean Formulae Theorem 254 TQBF 239s PSPACE complete We ll accept this as given for now 255 Games A closed quanti ed Boolean formula can be thought of in terms of a game between two players7 Alice and Bob The quanti ers are read from left to right If a variable is existentially quanti ed eg7 Hz 7 then Alice gets to choose a truth value for that variable If the variable is universally quanti ed eg7 w7 then Bob gets to choose a truth value for that variable After the players have chosen truth values for all the variables7 the resulting truth assignment makes the remaining unquanti ed portion of the formula either true or false lf true7 Alice wins if false7 Bob wins Since the game is nite7 either Alice or Bob not both has a winning strategy The original quanti ed formula is true if and only if Alice has a winning strategy Because of this gamelike aspect to TQBF7 many PSPACE complete decision problems are about who has a winning strategy in some game Describe Generalized Geography GG lnstances are C s7 where G is a digraph and s E VG is the starting vertex 26 4232008 Proposition 261 GG 239s PSPACE complete Proof We need to show that GG E PSPACE and that GG is PSPACE hard For the former7 we give an algorithm deciding GG and verify that the algorithm can be implemented using a polynomial amount of space Probably the easiest way to do this is via a recursive algorithm If G is a directed graph and s E VG is a vertex of G7 then let Ns be the set of all vertices t of G adjacent to 3 via an edge 3 a if from s to t Also7 let G 7 s be the graph obtained from G by removing the vertex 3 and all edges to and from 3 Note that7 starting with the game con guration C1757 the next player moves by choosing some t 6 N5 if one exists7 and the game con guration then becomes G 7 s t 3 cannot be used again7 so we might as well remove it Here s the algorithm deciding GG On input G s where G is a digraph and s E VG 1 If NextllayerWinsG7 s then accept else reject That is7 accept iff Alice who is the next player can win the game 1577 62 NextPlayerWins is a Boolean valued function that returns TRUE for a game 13 iff the next player to move in the game which could be either Alice or Bob can win it ie has a winning strategy We de ne it recursively Function NextPlayerWinsG s Boolean 1 For every t 6 N5 do a If NOT NextPlayerWinsG 7 s t then return TRUE We ve found a move for the next player from which his or her opponent cannot guarantee a win ie can be forced to lose this is the rst move in a winning strategy for the next player 2 If we get here then return FALSE Every one of the next player s possible moves leads to a game winnable by his or her opponent so the next player has no winning strategy The algorithm is intuitively correct How much space does it use If we implement it on a multitape TM we can use one of the tapes to act as a control stack for the recursion There are a few other auxillary variables to keep track of but the space is dominated by the size of the control stack Suppose the input is 13 and n G Each stack frame only needs to contain some string 6quot s where G is some subgraph of G and s E VG Thus the size of each stack frame is at most 71 Since each recursive call is made on a graph with one fewer vertices the maximum depth of the recursion the maximum number of frames on the stack at any one time is bounded by lVGl 1 which is certainly at most 71 1 Thus the total space used is the max size of a stack frame times the max number of stack frames and this is 0n2 Polyn Thus the algorithm uses polynomial space which puts GG in PSPACE Another way to see it is to notice that the algorithm just traverses the game tree generated by 15 and it only needs to remember one polynomial length path at a time This next part is currently a sketch PSPACE hardness of GG is shown by a p m reduction from TQBF Given some quanti ed Boolean formula as input we can assume that the formula is of the form lt3z1gtltvz2gtltazsgt aw alternating quanti ers beginning and ending with 3 so 71 is odd where 4p is in ONE ie 4p is of the form 01A02AA0k where each clause C is a disjunction of literals We can do this by inserting new quanti cations into the string of quanti cations The new quanti cations use fresh variables that don t occur anywhere else and hence don t affect the truth value of 4p We do this purely for technical reasons so that in the TQBF game Alice and Bob alternate picking values for one Boolean variable apiece and Alice picks the rst and last values We can then translate this game directly into an instance of GG Draw the output graph G with start vertex 3 After the variables7 truth values have been chosen Bob picks an edge corresponding to one of the clauses C and then Alice responds by choosing an edge corresponding to some literal in 0 She can do this and then Bob can t move so he loses iff the literal is true El Theorem 262 TQBF 239s PSPACE complete Proof TQBF is in PSPACE via either a recursive algorithm as with GG or one that explicitly traverses the game tree of all possible truth assignments to the variables at each leaf checking whether the unquanti ed portion is true for that assignment Since this is our rst PSPACE hardness proof we need to give a p m reduction to TQBF from an arbitrary language A E PSPACE Some of the details of this proof are similar to that of the Cook Levin Theorem above so we will only sketch those parts when they arise concentrating on the features unique to the current proof We are given a language A E PSPACE decided by a TM M that uses at most pn space for inputs of length n where p is some polynomial By picking a larger polynomial p if necessary we can also assume that o M halts in at most 21M steps on any input of length n and c all con gurations reachable by M on inputs of length n can be described using exactly pn bits We show that A g3 TQBF Fix a string w let n lwl and let p Then M halts in at most p steps on input w To show the reduction we construct in polynomial time a quanti ed Boolean formula W that is true iff M accepts w For simplicity we ll make one more harmless assumption about M We assume that just before M accepts it erases the entire contents of its tape and leaves the head scanning the leftmost cell This implies that there is one unique accepting con guration cam qawept for M For any nonnegative integer t we use the two place predicate Reachtcl 02 to mean 01 and 02 are con gurations of M represented by binary strings of length p each and starting in con guration 01 M reaches con guration 62 after at most 2 steps77 We can assume that 01 and 02 are both binary strings of length p Notice that M accepts w just in case Reachpq0w cam is true where qow is the initial con g uration of M on input w That is M accepts w iff M can reach cam in at most 21 steps starting from qow We can now translate Reacht01 62 into a quanti ed Boolean formula recursively The formula will not be in quanti ed CNF to begin with but we can x that later Base Case lft 0 then Reach0cl 02 is true just in case M can go from 01 to 62 within 20 1 step This in turn is true iff either 01 02 M takes zero steps or 02 is a legal successor to 01 M takes one step To express 1 02 we need a conjuction of clauses that come in p pairs 01 V 02 A cl V 02 where cl and 02 are the ith bits of 01 and 02 respectively for all 1 g i g p The resulting formula is in CNF and is true iff the ith bits are equal for all 2 As in the proof of the Cook Levin Theorem we can express the condition that 62 is a successor to 01 as an unquanti ed Boolean CNF formula We omit the details So we translate Reach0cl 02 into the disjunction of these two formulae This is an unquan ti ed Boolean formula over 2p variables the rst p encoding 01 and the rest encoding 02 To get it into CNF we can use the fact that V distributes over A and take the conjunction of all possible disjunctions of a clause from one formula with a clause from the other This may increase the size of the formula quadratically but it is still polynomial size 64 Recursive Case Suppose t 2 1 Clearly M goes from 01 to 02 in at most 2 steps iff there is a con guration 0 such that M goes from 01 to c in at most 2 1 steps and from c to 02 in at most 2 1 steps So Reacht01 02 ltgt Hc Reacht1clc A Reacht1ccg 2 Here 30 is shorthand for a string ofp many existential quanti cations over Boolean vari ables 301302 3017 where the C are single bits Boolean variables and c 0102 01 Starting with Reachpq0w cam and repeatedly substituting the right hand side of 2 for the left hand side recursively we wind up with a quanti ed Boolean formula Unfortunately it is too large When we do the substitution given in 2 we decrease if by 1 but roughly double the size of the formula So in the end we get a formula of size roughly 21 which is exponentially large and thus cannot be generated in polynomial time To prevent exponential blow up in the formula size we really need to have only one recursive call to Reacht1 on the right hand side of 2 instead of two We can accomplish this by replacing the conjunction with universal quanti cation Reachtcl 32 ltgt HcchVC4 6364 6 61 c c 02 gt Reacht1cg C4 3 The term 03 C4 6 0113Ct3277 expands to 03 01 A C4 c V 03 0 A04 32 and we use the standard equivalence P a Q ltgt P V Q to remove the a It almost goes without saying that Cg and C4 are binary strings of length p Applying 3 recursively p times starting with Reachpq0w cam yields a polynomial size quan ti ed Boolean sentence ie a closed formula and it is easy to see that this expansion can be done in time polynomial in n qow and cage are strings not of variables but rather of Boolean constants It remains to get the sentence into the form we want namely a string of quanti ers followed by a CNF formula By standard rules of logic all the quanti ers can simply be moved to the left without changing the truth value of the sentence The resulting sentence is said to be in prenez form Getting a CNF formula after the quanti ers is an exercise for the reader Theory of Computation Lecture 13 Undecidable Languages Max Alekseyev University of South Carolina March 3 2009 Decidable vs Undecidable Languages EQDFA ltA7 B i A7 Bare DFAs and LA LB EQCFG ltG7 H i G7 Hare CFGs and LG LH We proved that EQDFA is decidable In contrast to EQDFA it is not clear how to prove that EQCFG is decidable Decidable vs Undecidable Languages EQDFA ltA7 B l A7 Bare DFAs and LA LB EQCFG ltG7 H l G7 Hare CFGs and LG LH We proved that EQDFA is decidable In contrast to EQDFA it is not clear how to prove that EQCFG is decidable In fact it is NOT decidable But it is still unclear how to prove that Our goal is to prove undecidability of another somewhat simpler language ATM ltM7 W l M is a TM and M accepts W Decidable vs Undecidable Languages ACFG ltG7 Wgt l G is a CFG that generates string W ATM ltM7 Wgt l M is a TM and M accepts W We proved that ACFG is decidable and that was used to prove that every context free language is decidable by simulating a TM for ACFG Q What would happen if we prove that ATM is decidable Decidable vs Undecidable Languages ACFG ltG7 Wgt l G is a CFG that generates string W ATM ltM7 Wgt l M is a TM and M accepts W We proved that ACFG is decidable and that was used to prove that every context free language is decidable by simulating a TM for ACFG Q What would happen if we prove that ATM is decidable If ATM were decidable the language of any TM machine would be decidable In particular recognizable languages would coincide with decidable languages which is very unrealisticl So it is natural to expect that ATM is NOT decidable Halting Problem It is easy to establish that ATM is recognizable for a given pair ltM7 Wgt we need simply to simulate M on the input W and accept or reject depending on whether M accepts or rejects Note that M may loop in which case our simulation will loop as well making it just a recognizer not a decider Halting Problem It is easy to establish that ATM is recognizable for a given pair ltM7 Wgt we need simply to simulate M on the input W and accept or reject depending on whether M accepts or rejects Note that M may loop in which case our simulation will loop as well making it just a recognizer not a decider If we were able to determine whether M would ever stop on a given input W a TM for ATM could reject given ltM7 Wgt as soon as it determined that M would loop on W In this case it would be a decider for ATM which accepts if M accepts and rejects if M rejects or loops Halting Problem It is easy to establish that ATM is recognizable for a given pair ltM7 Wgt we need simply to simulate M on the input W and accept or reject depending on whether M accepts or rejects Note that M may loop in which case our simulation will loop as well making it just a recognizer not a decider If we were able to determine whether M would ever stop on a given input W a TM for ATM could reject given ltM7 Wgt as soon as it determined that M would loop on W In this case it would be a decider for ATM which accepts if M accepts and rejects if M rejects or loops Therefore the crucial point is determination of whether M would ever stop on a given input W giving the name halting problem to ATM In these new terms our goal is to prove that the halting problem is undecidable Sets and their cardinalities It is easy to tell whether two given finite sets such as 5 7 23 and 3 b 6 have the same size just count up their elements and compare the counts But is there a way to compare sizes of two infinite sets Obviously counting elements won39t help as it would never end But can we determine that two sets have equal sizes without counting their elements Sets and their cardinalities It is easy to tell whether two given finite sets such as 5 7 23 and 3 b 6 have the same size just count up their elements and compare the counts But is there a way to compare sizes of two infinite sets Obviously counting elements won39t help as it would never end But can we determine that two sets have equal sizes without counting their elements The idea is to set up a mapping between the elements of two sets such that each element of one set is mapped to an element of the other and vice versa This idea works equally well for finite and infinite sets For example we can map elements of the two sets above as follows 5 lt gt a 7 lt gt b and 23 lt gt c implying that these sets are the same size One to one onto correspondence Let A7 B be two sets and f A a B be a function from A to B Definition f is called one to one injectvs if it maps different elements of A to different elements of B Definition f is called onto surjective if for every elements b E B there exists a E A such that fa b Definition f is called correspondence bijective if it is oneto one and onto Two set are of the same size if there exists a correspondence between them Examples The set E 2 4 6 of even positive integers and the set N 12 3 of natural numbers are the same size Q Why Examples The set E 2 4 6 of even positive integers and the set N 12 3 of natural numbers are the same size Q Why Define f NH 5 such that fn 2n for every n E N It is oneto one since for n 7 m we have 2n 7 2m It is onto since for k E E k2 is a natural number and fk2 k Hence f is a correspondence between E and N implying that they are the same size Examples The set E 2 4 6 of even positive integers and the set N 12 3 of natural numbers are the same size Q Why Define f NH 5 such that fn 2n for every n E N It is oneto one since for n 7 m we have 2n 7 2m It is onto since for k E E k2 is a natural number and fk2 k Hence f is a correspondence between E and N implying that they are the same size Definition A set is called countable if either it is finite or has the same size as Some properties gt the union of a finite number of finite sets is finite gt the union of a finite or infinite number of countable sets is countable gt the power set of a finite set is finite gt the power set of an infinite set is uncountable The last property is proved by an important technique called diagonalzation For the proof of countability of the positive rationals Q and uncountability of the reals R see Sipser pp175 178 Coutability of Languages and TMs Let X be an alphabet which is a finite set The set X of all strings over X can be viewed as 2UWiwe A lwlk kZO is infinite and countable In particular the set of all TMs is countable as they can be viewed as strings over some alphabet Coutability of Languages and TMs Let X be an alphabet which is a finite set The set X of all strings over X can be viewed as 2UWiwe A lwlk kZO is infinite and countable In particular the set of all TMs is countable as they can be viewed as strings over some alphabet The set of all languages over X is the power set of X and thus is uncountable Theorem Some languages are not Turing recognizable Halting Problem is Undecidable ATM M7 W l M is a TM and M accepts W ATM is not decidable Proof outline gt Assume that ATM is decidable and let H be a decider for it ie HM7 W accepts if M accepts W and rejects otherwise gt Define a new TM D which on input M runs H on input M7 and outputs opposite to what H outputs gt The result of running D on D is undefined gt if D accepts D then by the definition of D H rejects D7 implying by the definition of H that D does not accept D gt if D rejects D then by the definition of D H accepts D7 implying by the definition of H that D accepts D gt The contradiction disproves our assumption ie ATM is undecidable Tu ring U nrecognizable languages Theorem A language is decidable iffit is Turing recognizable and co Turing recognizable ie its complement is Turing recognizable Tu ring U nrecognizable languages Theorem A language is decidable iffit is Turing recognizable and co Turing recognizable ie its complement is Turing recognizable Corollary ATM is not Turing recognizable

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.