Class Note for CMPSCI 601 at UMass(19)
Class Note for CMPSCI 601 at UMass(19)
Popular in Course
Popular in Department
This 18 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(19)
Report this Material
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: 02/06/15
CMPSCI 601 Recall From Last Time Lecture 5 Turing Machines M QE6s 6 QXE gt QUhgtltEgtlte gt Def Function f is recursive iff it is computed by a TM f may be total or partial Def A set S is recursive iff its characteristic function X5 is a recursive function Recursive is the set of recursive sets A set S is recursively enumberable re iff its partial characteristic function p 5 is a recursive function re is the set of re sets Th Recursive re c0re CMPSCI 601 Palindromes Lecture 5 De nition 51 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 52 T he set OfPALINDROMES over a xed alpha bet E is contextfree but not regular Proposition 53 The set ofPALINDROMES over a xed alphabet E is a recursive set Proof ABLEELBALJ A Fact 54 Time 0n2 is necessary and su icient for a one tape Turing machine to accept the set PALINDROMES Proof Time 0n2 su ices One way to see this is to do problems 284 285 from P A CMPSCI 601 MuliTape Turing Machines Lecture 5 De nition 55 A ktape Turing machine M Q E 6 8 Q nite set of states 8 E Q E nite set of symbols 6Q X we gt Q u W x 2 x 957 k Proposition 56 PALINDROMES can be accepted in DTIME on a 2tape TM Proof that PALINDROMES e DTIMEM ABLEELBALJ Eu DABLEELBALJ IgtLJ CMPSCI601 DTIME and DSPACE Lecture 5 De nition 57 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 De nition 58 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 A Example PALINDROMES e DTIMEM DSPACEM In fact PALINDROMES E DSPACElog CMPSCI601 FDTIME and FDSPACE Lecture 5 De nition 59 f 2 gt 2 is in FDTIMEtn iff there exists a deterministic multitape TM M and a constant c such that 1 f MM 2 V11 6 2 halts within 01 steps 3 3 1112100 ie f is polynomially bounded A De nition 510 f 2 gt 2 is in FDSPACE8n iff there exists a deterministic multitape TM M and a constant c such that 1f MM 2 V11 6 2 uses at most 01 worktape cells 3 3 1112100 ie f is polynomially bounded Input tape is readonly Output tape is writeonly Neither is counted as space used A Example Plus 6 FDTIMEn Times 6 FDTIMEn2 8 CMPSCI 601 L P and PSPACE Lecture 5 L E DSPACE10gn P E DTIMEn0lt1gt E CCJOIDTIMEW39 PSPACE 2 DSPACEn0lt1gt 2 OGIDSPACEW Theorem 511 For any functions tn 2 n 300 2 log n we have DTIMEtn Q DSPACEtn DSPACE8n Q DTIME20SH Proof Let M be a DSPACEsn TM letw E 2 letn M has k tapes and uses at most 08n worktape cells M has at most IQ n 090 2k 1216300 lt 2H4 possible con gurations Thus after 21M steps M must be in an in nite loop A Corollary 512 L g P g PSPACE 10 CMPSCI601 PALINDROMES E L LectureS EABLEELBALJ EILJ Using Olog n workspace we can keep track of and ma nipulate two pointers into the input 11 CMPSCI 601 DTIME versus RAMTIME Lecture 5 RAM Random Access Machine Memory F r0 r1 r2 r3 r4 n K program counter r0 accumulator Instruction Operand Semantics READ jltjlj Torrjlnjlj STORE j Tj 73 I my 2 TO ADD 3 th j Torrorjlmlj SUB lejlj 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 12 Theorem 513 DTIMEtn Q RAMTIMEtn Q DTIMEtn3 Proof Memorize program in nite control Store all registers on one tape Igt110101101010111O 7 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 IgtO10110101011101J T0 T5 T11 Each register contains at most n tn bits The total number of tape cells used is at most MW WU 0tn2 Each step takes at most 0 steps to simulate A 13 CMPSCI 601 Nondeterministic TM Lecture 5 Nondeterrninistic Turing Machines choose one of two possible moves each step guesstm S g q 0 1 1 g7LJ7 iQ7LJ7 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 Accept iff there exists some guess that leads to accep tance 14 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 15 De nition 514 The set accepted by a NTM N N E w E 2 1 some run of N halts with output 1 The time taken by N on w E N is the number of steps in the shortest computation of N that accepts A 9 n AU ooooooooooooowooooooooo tn 16 CMPSCI 601 NTIME and NP Lecture 5 NTIMEtn E probs accepted by NTMs in time Otn NP E NTIMEn0lt1gt E 39EJOINTIMEW Theorem 515 For any function DTIMEtn g NTIMEtn g DSPACEtn Recall DSPACEtn g DTIME20lttltngtgt Corollary 516 L C P g NP g PSPACE Corollary 517 The de nition of Recursive and re are unchanged if we use n0ndeierminisiic instead of deter ministic Turing machines 17 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 18
Are you sure you want to buy this material for
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'