Scrum Software Dev Research
Scrum Software Dev Research CS 39000
Popular in Course
Popular in ComputerScienence
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
This 39 page Class Notes was uploaded by Nick Rowe on Saturday September 19, 2015. The Class Notes belongs to CS 39000 at Purdue University taught by Staff in Fall. Since its upload, it has received 45 views. For similar materials see /class/208084/cs-39000-purdue-university in ComputerScienence at Purdue University.
Reviews for Scrum Software Dev Research
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: 09/19/15
Lecture 2 Power of Concurrency In this lecture we address two major ques ons Can we do things with concurrency and parallel platforms that we could not do with conventional serial programs What is the basic difficulty associated with writing concurrent programs 083900 Concurrency and Parallelism Execution Platforms Concurrent programs execute on Conventional Serial Platforms Key motivation here is service time fairness preventing livelocks Parallel Hardware Multicore processors coprocessors symmetric multiprocessors clusters Key motivation here is speed Distributed Platforms Services P2P environments Key motivation here is the need to integrate physically distributed resources 083900 Concurrency and Parallelism Digression Parallel Hardware Needed 083900 Concurrency and Parallelism Power of Concurrency Can a concurrent programhardware do things that a serial programhardware cannot do We answer this formally by demonstrating the equivalence between a singletape and ntape Turing machine 083900 Concurrency and Parallelism Turing Machines Serve as the basis for evaluating the computability of a problem Turing machines provide a formal model that can compute everything a traditional computer can and vice versa We can use this formal model to reason about the computability of a given problem 083900 Concurrency and Parallelism Turing Machines Example Devise an algorithm to determine if an arbitrary polynomial has integral roots Can ShOW that there cannot be an algorithm for the above problem 083900 Concurrency and Parallelism Turing Machines A machine consisting of a tape of infinite length and a readwrite head which can move left and right across the tape 083900 Concurrency and Parallelism Turing Machines Tape initially contains an input string followed by blanks When started a Turing Machine executes a series of discrete transitions as determined by its transition function and by the initial characters on the tape 083900 Concurrency and Parallelism Turing Machines Transitions depend on current state and character under tape head Transitions lead to a new state write a new character on the tape and move the tape head one position left or right The machine stops on a transition to a special HALT state accept or reject The machine may never reach this state 083900 Concurrency and Parallelism Turing Machines O a9aR means TM reads the symbol a it replaces it with a and moves head to right This TM when reading an a will move right one square stays in the same start state When it scans a b it will change this symbol to an a and go into the other state accept state 083900 Concurrency and Parallelism Turing Machines A TM that tests for memberships in the language A ww w belongs to O1 A language that has two identical strings w separated by a hash mark Idea Zigzag across tape crossing off matching symbols 083900 Concurrency and Parallelism Turing Machines Tape head starts over leftmost symbol Record symbol in control and overwrite X Scan right reject if blank encountered before When encountered move right one space If symbols don t match reject 083900 Concurrency and Parallelism Turing Machines Overwrite X Scan left past to X Move one space right Record symbol and overwrite X When encountered move right one space If symbols don t match reject 083900 Concurrency and Parallelism Turing Machines Finally scan left If a or b encountered reject When blank encountered accept 083900 Concurrency and Parallelism Turing Machines Formal Definition ATuring Machine is a 7tuple QZT q0qaccept qreject where Q is a finite set of states 2 is a finite set of symbols called the alphabet T is the tape alphabet where belongs to T and 29 T E Q x T 9 Q x T x LR is the transition function q0 6 Q is the start state qaccept Q Q is the accept state 9 Q is the reject state where qaccept at qreject CIreject 083900 Concurrency and Parallelism Turing Machines Formal Definition g 3 Q X T 9 Q X T X LR is the transition function Cla rbL means in state q where head reads tape symbol a the machine overwrites a with b enters state r and moves the head left 083900 Concurrency and Parallelism Turing Machines Formal Definition M QZT q0qaccept qreject computes as follows Input ww1w2wn is on leftmost n tape squares Rest of tape is blank Head is on leftmost square of tape 083900 Concurrency and Parallelism Turing Machines Formal Definition M Q Z T gtqotqaccept CIaccept When computation starts M Proceeds according to transition function E If M tries to move head beyond lefthandend of tape it doesn t move Computation continues until qaccept or qaccelot is reached Otherwise M runs forever 083900 Concurrency and Parallelism Turing Machines Formal Definition uarbv yields upacv if nb pcL uarbv yields uacpv if nb pcR Special cases rbv yields pcv if nb pCL wr is the same as wr 083900 Concurrency and Parallelism Turing Machines Formal Definition TM M accepts input w if a sequence of configurations C1CZCk exist C1 is start configuration of M on w Each Ci yields Ci1 Ck is an accepting configuration The collection of strings that M accepts is the language of M denoted by LM 083900 Concurrency and Parallelism Turing Machines Formal Definition Definition A language is recursively enumerable if some TM accepts it On an input to a TM we may accept reject loop run for ever Not very practical never know if TM will halt 083900 Concurrency and Parallelism Turing Machines Formal Definition Definition A TM decides a language if it always halts in an accept or reject state Such a TM is called a decider Definition A language is decidable if someTM decides it Some textbooks use recursive instead of decidable Therefore every decidable language is enumerable but not the reverse 083900 Concurrency and Parallelism Turing Machines Formal Definition Here is a decidable language Laibick ixj k ljk gt O Because there exist a TM that decides it How 083900 Concurrency and Parallelism Turing Machines Formal Definition What is not decidable D p p is a polynomial with an integral root Determine whether the set D is decidable Can t do it We can show that D is Turingrecognizable 083900 Concurrency and Parallelism Turing Machines Formal Definition Consider Hilbert s problem only for variable X D1 p p is a polynomial over x with integral roots TMD1 Evaluate p with x set successively to the values 0 1 1 2 3 3 3 if at any point the polynomial evaluates to O accept lief Egllthas an integral root this TM will eventually In If D1 has no integral root this TM will run forever This TM is a recognizer not a decider 083900 Concurrency and Parallelism Undecidable Problems Given a CproPram or a pro ram in any pro ramming anguage real y that prints he 0 world IS there another program that can test if a program given as input prints hello world 083900 Concurrency and Parallelism Undecidable Problems This is tougher than it may sound at first glance For some programs It IS easy to etermlne If Itprnts hello world Here IS perhaps the Simplest include stdioh void main printf hello worldn 083900 Concurrency and Parallelism Undecidable Problems It would be fairly easy to write a program to test to see if another program consisting solely of printf statements will output hello world But what we want is a program that can take any arbitrary program and determine if it prints hello world This is much more difficult 083900 Concurrency and Parallelism Undecidable Problems include ltstdiohgt mainta char a returnOltttlt3main7913amain871main860a1a 1tltmaint1a3main9427taampampt2lt13 main21quots d dnquot916tlt0tlt72maint quotn39 wwcdnrrdewwqnlnnn qnk39r 39d393wK w39K39e39dq39l q d39Kkq reKKw39reKKnl39qn39w39nl39n39drw39 i nlnn39 rw39r ncnl39l39Krw39 iKnl39wqn39wk nw39 iwkKKnlw39lw i nl39 q ldrn39nlwbde39c nl39rw3939nc39nw39kd39e rdqw nr39l39 rl39n39 39 39lquot tlt50aputchar31amain65a1maina3939ta1 Olttmain22quotsquota3939llmain0main61a quotekdc ibK39qwnr3lnuwlocaOm vpbksfxntdCeghiryquota1 083900 Concurrency and Parallelism Undecidable Problems pinkycspurdueedu 326 aout On the first day of Christmas my true love gave to me a partridge in a pear tree On the second day of Christmas my true love gave to me two turtle doves and a partridge in a pear tree 083900 Concurrency and Parallelism Undecidable Problems Problem Create a program that determines if any arbitrary program prints hello world We can show there is no program to solve that problem ie it is undecidable Suppose that there were such a program H the hello worldtesterquot H takes as input a program P and an input file for that program and tells whether P with input I prints hello world and outputs yes if it does no if it does not 083900 Concurrency and Parallelism Undecidable Problems H Helloworld tester 083900 Concurrency and Parallelism Undecidable Problems Next we modify H to a new program H1 that acts like H but when H prints no H1 prints hello world To do this we need to find where no is printed and instead output hello world instead yes H1 Helloworld tester hello world 083900 Concurrency and Parallelism Undecidable Problems Next modify H1 to H2 The program H2 takdels only one input P2 instead of both P an To do this the new input P2 must include the data input I and the program P The program P and data input I are all stored in a buffer in program H2 H2 then simulates H1 but whenever H1 reads input H2 feeds the input from the buffered copy H2 can maintain two index pointers into the buffered data to know what current data and code should be read next 083900 Concurrency and Parallelism Undecidable Problems However H2 cannot exist If it did what would H2H2 do That is we give H2 as input to itself If H2 on the left outputs yes then H2 given H2 as input will print hello world But we just supposed that the first output H2 makes is yes and not hello world 5 The situation is paradoxical and we conclude that H2 cannot exist and this problem is undecidable 083900 Concurrency and Parallelism Multitape Turing Machines A multitape Turing machine is like an ordinary TM but it has several tapes instead of one tape Initially the input starts on tape 1 and the other tapes are blank The transition function is changed to allow for reading writing and moving the heads on all the tapes simultaneously This means we could read on multiples tape and move in different directions on each tape as well as write a different symbol on each tape all in one move 083900 Concurrency and Parallelism Multitape Turing Machines Theorem A multitape TM is equivalent In power to an ordinary TM Recall that two TM s are equwalent If they recognize the same language We can show how to convert a multitape TM M to a Single tape TM 8 083900 Concurrency and Parallelism Multitape Turing Machines S ay that M has k tapes Create the TM 8 to simulate having k tapes by InterleaVIng the Information on each of the k tapes on Its smgle ape Use a new symbol as a delimiter to separate the contents of each tape 8 must also keep track of the location on each of the simulated heads 083900 Concurrency and Parallelism NonDeterministic Turing Machines Theorem Can be shown that these are identical to single tape turlng machines as we 083900 Concurrency and Parallelism
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'