Class Note for CMPSCI 601 at UMass(9)
Class Note for CMPSCI 601 at UMass(9)
Popular in Course
Popular in Department
This 21 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 13 views.
Reviews for Class Note for CMPSCI 601 at UMass(9)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 02/06/15
CMPSCI 601 Recall From Last Time Lecture 8 Turing Machines M QE6s 6 QXE gt QUhgtltEgtlte gt Def A function f is recursive iff it is computed by a TM f may be total de ned for all inputs or partial Def A set S is recursive or Turing decidable iff its characteristic function X3 is a recursive function Recursive is the set of recursive sets Def A set S is recursively enumberable r e or Turing acceptable iff its partial characteristic function p3 is a recursive function re is the set of re sets Theorem Recursive re c0re CMPSCI 601 Palindromes Lecture 8 De nition 81 A string 11 E 2 is a palindrome iff it is the same as its reversal ie w 2 MB A Examples of palindromes 0 101 0 1 10100101 1 0 ABLE WAS I ERE I SAW ELBA 0 AMANAPLANACANALPANAMA Fact 82 T he set OfPALINDROMES over a xed alpha bet E is contextfree but not regular Proposition 83 The set ofPALINDROMES over a xed alphabet E is a recursive set Proof We must construct a TM that decides PALIN DROMES From here on we ll be describing TM s very informally Given the input EABLEELBALJ We remember the rst letter delete it move to the last letter and either delete it if it matches or return false if it doesn t We repeat this process on the undeleted part of the string and return true iff the string becomes empty by deleting its last letter A Fact 84 Time 00 is necessary and su icient for a one tape Turing machine to accept the set PALINDROMES Proof The procedure above used time 0n2 do you see this The lower bound is harder to prove and depends strongly on the fact that we are working with a onetape Turing machine One way to see the lower bound is to do problems 284 and 285 from P A 3 CMPSCI 601 MultiTape Turing Machines Lecture 8 De nition 85 A ktape Turing machine M Q E 6 8 Q nite set of states 8 E Q E nite set of symbols M2 x xi a Q u M gtlt lt2 gtlt em gtk A A multitape TM reads one cell on each tape the cell un der that tape s head on each time step Based on those cells contents and its state it writes into the current cell on each tape and moves up to one cell left or right on each tape Theorem 86 For any k any ktape TM may be simu lated by a onetape TM Proof See P or S for a detailed proof The idea is to store the k tapes on a single tape with the contents either in series or in parallel To simulate one step of the ktape machine the onetape machine must nd the contents of the current cells and then perform the proper actions on the part of its tape corresponding to each current cell A Proposition 87 PALINDROMES can be accepted in DTIME on a 2tape TM Proof that PALINDROMES e DTIMEM ABLEELBALJ Eu DABLEELBALJ IgtLJ CMPSCI601 DTIME and DSPACE Lecture 8 De nition 88 A set A g 2 is in DTIMEtn iff there exists a deterministic multitape TM M and a constant c such that LA 2 M E w E 2 1 MW 1 and 2 V11 6 2 halts within 01 steps Q Why 01 t steps Ifthe input is size n we nor mally want the running time bound to be Otn steps But for convenience with functions t where tn might be less than one we modify this to 01 steps the max 0fO1 and De nition 89 A set A Q 2 is in DSPACEsn iff there exists a deterministic multitape TM M and a constant c such that lA M and 2 V11 6 2 uses at most 01 worktape cells Note The input tape is readonly and not counted as space used Otherwise space bounds below n would rarely be useful But in the real world we often want to limit space and work with readonly input Consider for example a problem where the input is the entire WorldWide Web A Example We have just shown that PALINDROMES is in both DTIME and DSPACEM In fact we ll show a little later that PALINDROMES E DSPACE log CMPSCI601 FDTIME and FDSPACE Lecture 8 De nition 810 f 2 gt 2 is in FDTIMEtn iff there exists a deterministic multitape TM M and a constant c such that l f MieVw fw 2 V11 6 2 halts within 01 steps 3 3 111210 ie f is polynomially bounded A The last condition is a technical one as functions that re turn enormously bigger strings are convenient to rule out Note that if f is itself no as is usual for practically feasible algorithms the last condition follows automati cally De nition 811 f 2 gt 2 is in FDSPACE8n iff there exists a deterministic multitape TM M and a constant c such that l f MieVw fw 2 V11 6 2 uses at most 01 worktape cells 3 3 111210 ie f is polynomially bounded Recall that the input tape is readonly and that the output tape is writeonly and that neither is counted against the space bound A Examples The function Plus is in F DTIMEM and FDSPACE1 As you ll prove on the revised HW2 the function Times is in FDTIMEn2 and for extra credit F DSPACE log n CMPSCI 601 L P and PSPACE Lecture 8 We are now ready to de ne three important complexity classes L DSPACE log n i P E DTIMEn0lt1gt i l DTIMEM 00 PSPACE DSPACEn0lt1gt 39ul DSPACEW Theorem 812 P is also the set of languages decidable in no time on a onetape TM Proof P clearly contains all these languages For the other direction we look more closely at the simulation of a ktape TM by a onetape TM Simulating one step of the former requires two passes over the entire tape of the latter which can be done in Osn Otn time So Ot2n time on the onetape TM suf ces to simulate Otn time on the ktape TM A 10 Theorem 813 For any functions tn 2 n 300 2 log n we have DTIMEtn g DSPACEtn DSPACEsn g DTIME208n Proof The rst statement is obvious To prove the second statement let M be a DSPACE TM letw E 2 and letn M has k tapes and when it runs on w it uses at most 08n worktape cells During this computation M thus has at most n l 087 I lt 216801 possible con gurations Thus after 26130 steps M must be in an in nite loop So either it halts before using that many steps or it never halts at all And for it not to halt is a contradiction as M is supposed to halt on all inputs A Corollary 814 L g P g PSPACE ll CMPSCI 601 PALINDROMES E L Lecture 8 EA EELBALJ Eu DA EELSBALJ IgtlELJ8 DA EELSBALJ IgtZELJ7 DA EELBALJ Igt3ELJ6 DA EELBALJ Igt4ELJ5 EA EELEBALJEEIELJ The machine must keep track of and manipulate two point ers into the input Since each of these pointers holds a number from 1 through n where n is the length of the in put the worktape space used for each pointer is Olog n cells and the total space is Olog 12 CMPSCI 601 DTIME versus RAMTIME Lecture 8 RAM Random Access Machine Memory F r0 r1 r2 r3 r4 n K program counter r0 accumulator Instruction Operand Semantics READ jlljlj Torrjlnjlj STORE j Tj 73 I my 2 TO ADD 3 th j Torrorjlmlj SUB jlljlj T03T0 7quotj17quotrjlj HALF r0 2 LroQj JUMP j 1e j JPOS j if m gt 0 then 1e j JZERO j if m 0 then 1e 2 j HALT 1c 2 0 This is a reasonable model of an actual assemblylanguage program an extreme version of a RISC l3 Theorem 815 DTIMEtn Q RAMTIMEtn Q DTIMEtn3 Proof The rst inclusion is obvious For the other we must simulate the RAM with a TM First we memorize the program in the TM s nite control Store all registers on one tape gt11o101101o10111o K T0 T5 T11 Store workspace for calculations on second tape gt100lOlllJ Is A Use the third tape for moving over sections of the rst tape IgtOlOllOlOlOlllOlJ 14 Each register contains at most n tn bits because our instructions allow us to at most double the largest number each time The total number of tape cells used is at most MW WU 0tn2 Each step takes at most 0 steps to simulate A What if we added a MULT instruction to our RAM Then we could square the largest number each time generating numbers of 200W bits in time These numbers can t be processed in polynomial time by a TM But real computers have a xed word size rather than registers that can hold arbitrary integers To model this the algorithms books use a logcost RAM as their basic model so that touching a register with a number that is 1 bits costs you 01 time instead of O 1 The distinction between ordinary unitcost and logcost RAMs is only important when dealing with very large numbers 15 CMPSCI 601 Nondeterministic TM Lecture 8 A nondeterrninistic Turing Machine may choose one of two possible moves on each step Here is an example guesstm S g q 0 1 1 g7LJ7 IQ71 J7 8707 gt 18717 gt Igt s1gt gt comment 9 or q guess 0 or 1 the rest 0 Write down an arbitrary string 9 E 0 1 the guess 0 Proceed With the rest of the computation using 9 if desired 0 As with an NFA we accept the input iff there exists a computation path leading to acceptance With this machine this is true iff there exists some guess string that leads to acceptance 16 1 971 J7 IQ71 J7 8707 gt 18717 gt Igt sIgt gt comment 9 orq guess 0 orl the rest 8 Eu 8 Igt1J g IgtLJ S IgtOLJ g IgtOLJ 81gt01LJ gIgtOlLJ 31gt011LJ glgt011LJ 81gt0110 1LJ qIgt0110 1LJ 17 De nition 816 The set accepted by a NTM N N E w E 2 1 some run of N halts with output 1 We de ne the time taken by N on w E N to be the number of steps in the shortest computation of N that accepts A 9 n AM ooooooooooooot ooooooooo tn 18 CMPSCI 601 NTIME and NP Lecture 8 NTIME E probs accepted by NTMs in time Otn NP E NTIMEn0lt1gt E ONTIMEW39 i l Theorem 817 For any function DTIMEtn g NTIMEtn g DSPACEtn Proof The rst inclusion is obvious For the second note that in space Otn we can simulate all computa tions of length Otn so we will nd the shortest ac cepting one if it exists A Recall DSPACEtn g DTIME20lttltngtgt Corollary 818 L C P g NP g PSPACE l9 So we can simulate NTM s by DTM s at the cost of an exponential increase in the running time It may be pos sible to improve this simulation though no essentially better one is known If the cost could be reduced to poly nomial we would have that P NP There is probably such a quantitative difference between the power of NTM s and DTM s But note that qualita tively there is no difference If A is the language of some NTM N it must also be re because there is a DTM that searches through all computations of N on 11 rst of one step then of two steps and so on If 11 E A D will eventually nd an accepting computation If not it will search forever What about an NTMbased de nition of recursive or Turingdecidable sets This is less clear because NTM s don t decide they just have a range of possible actions But one can de ne a function computed by an NTM in a reasonable way and this leads to the same classes of partial recursive functions total recursive functions and recursive sets 20 mm Arlthmetlc H1erarchy W c0re Recursive 139 e re complete Primitive Recursive EXPTIME PSPACE c0NP PolynomialTime Hierarchy complete c0NP NP NP 1 c0NP NP complete quottruly feasiblequot NC NC2 logCFL SAC NSPACE log n 3 DSPACE log n Regular LogarithmicTime Hierarchy 21