Slide 1Alan TuringA Thinking MachineSlide 4Turing Machine ComponentsTapeRead/Write HeadControllerSlide 9A Thinking MachineSlide 11Slide 12Slide 13Slide 14Slide 15Slide 16How Hard Can a Problem Be?Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23The Halting ProblemSlide 25Slide 26Loops in JavascriptSlide 28Infinite Loops in JavascriptSlide 30Testing a program for self-terminationSlide 32Slide 33Slide 34Proving the unsolvability of the halting programCopyright © 2012 Pearson Education, Inc. Chapter 12:Theory of ComputationComputer Science: An OverviewEleventh Editionby J. Glenn BrookshearCopyright © 2012 Pearson Education, Inc. Alan TuringAlan Turing was one of the founding fathers of CS.• His computer model –the Turing Machine– was inspiration/premonition of the electronic computer that came two decades later• He was instrumental in cracking the Nazi Enigma cryptosystem in WWII• Invented the “Turing Test” used in AI• Legacy: The Turing Award. Pre-eminent award in Theoretical CSCopyright © 2012 Pearson Education, Inc. 3A Thinking MachineFirst Goal of Turing’s Machine: A model that can compute anything that a human can compute. Before invention of electronic computers the term “computer” actually referred to a person who’s line of work is to calculate numerical quantities!Turing’s Thesis: Any “algorithm” can be carried out by one of his machinesCopyright © 2012 Pearson Education, Inc. 4A Thinking Machine•Imagine a super-organized, obsessive-compulsive human computer. •The computer wants to avoid mistakes so everything written down is completely specified one letter/number at a time. •The computer follows a finite set of rules which are referred to every time another symbol is written down. •Rules are such that at any given time, only one rule is active so no ambiguity can arise. •Each rule activates another rule depending on what letter/number is currently readCopyright © 2012 Pearson Education, Inc. Turing Machine Components0-5A Turing machine is made of three components: a tape, a controller and a read/write headCopyright © 2012 Pearson Education, Inc. Tape•Although modern computers use a random-access storage device with finite capacity, we assume that the Turing machine’s memory is infinite. –Think of infinite as meaning whenever we need more tape we add another reel of tape•The tape, at any one time, holds a sequence of characters from the set of characters accepted by the machine. 0-6Copyright © 2012 Pearson Education, Inc. Read/Write Head•The read/write head at any moment points to one symbol on the tape. We call this symbol the current symbol. •The read/write head reads and writes one symbol at a time from the tape.•After reading and writing, it moves to the left or to the right or stops.•Reading, writing and moving are all done under instructions from the controller.0-7Copyright © 2012 Pearson Education, Inc. Controller•The controller is the theoretical counterpart of the central processing unit (CPU) in modern computers. •Think of it as a machine that has a predetermined finite number of commands it can process states and moves from one state to another based on the input. 0-8Copyright © 2012 Pearson Education, Inc. 9A Thinking MachineSample Rules:If read 1, write 0, go right, repeat.If read 0, write 1, HALT!If read □, write 1, HALT!Let’s see how they are carried out on a piece of paper that contains the reverse binary representation of 47 (reading right to left):Copyright © 2012 Pearson Education, Inc. 10A Thinking MachineIf read 1, write 0, go right, repeat.If read 0, write 1, HALT!If read □, write 1, HALT!1 1 1 1 0 1Copyright © 2012 Pearson Education, Inc. 11A Thinking MachineIf read 1, write 0, go right, repeat.If read 0, write 1, HALT!If read □, write 1, HALT!0 1 1 1 0 1Copyright © 2012 Pearson Education, Inc. 12A Thinking MachineIf read 1, write 0, go right, repeat.If read 0, write 1, HALT!If read □, write 1, HALT!0 0 1 1 0 1Copyright © 2012 Pearson Education, Inc. 13A Thinking MachineIf read 1, write 0, go right, repeat.If read 0, write 1, HALT!If read □, write 1, HALT!0 0 0 1 0 1Copyright © 2012 Pearson Education, Inc. 14A Thinking MachineIf read 1, write 0, go right, repeat.If read 0, write 1, HALT!If read □, write 1, HALT!0 0 0 0 0 1Copyright © 2012 Pearson Education, Inc. 15A Thinking MachineIf read 1, write 0, go right, repeat.If read 0, write 1, HALT!If read □, write 1, HALT!0 0 0 0 1 1Copyright © 2012 Pearson Education, Inc. 16A Thinking MachineSo the successor’s output on 111101 was 000011 which is the reverse binary representation of 48.Copyright © 2012 Pearson Education, Inc. 23-17How Hard Can a Problem Be?•The Travelling Salesman Problem (TSP) is a problem in combinatorial optimization studied in operations research and theoretical computer science. •Given a list of cities and their distances from each other, the task is to find a shortest possible tour that visits each city exactly once.•The problem was first formulated as a mathematical problem in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. –Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved.Copyright © 2012 Pearson Education, Inc. 23-18How Hard Can a Problem Be?•The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. •In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments.Copyright © 2012 Pearson Education, Inc. How Hard Can a Problem Be?•An optimal TSP tour through Germany’s 15 largest cities. It is the shortest among 43,589,145,600 possible tours visiting each city exactly once.23-19http://valis.cs.uiuc.edu/~sariel/research/CG/applets/tsp/TspAlg.htmlCopyright © 2012 Pearson Education, Inc. 23-20How Hard Can a Problem Be?•The knapsack problem or rucksack problem is a problem in combinatorial optimization:– Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is