Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Slide 74Slide 75Slide 76Slide 77Slide 78Slide 79Slide 80Slide 81Slide 82Slide 83Slide 84Slide 85Slide 86Slide 87Slide 88Slide 89Slide 90Slide 91Slide 92Slide 93Slide 94Slide 95Slide 96Slide 97Slide 98Slide 9915-251Great Theoretical Ideas in Computer ScienceLecture 21 - Dan KilgallinTuring MachinesGoals•Describe the nature of computation•Mathematically formalize the behavior of a program running on a computer system•Compare the capabilities of different programming languagesTuring Machines•What can we do to make a DFA better?•Idea: Give it some memory!•How much memory?•Infinite!•What kind of memory? Sequential access (e.g. CD, hard drive) or RAM?•An infinite amount of RAM requires remembering really big numbers and needlessly complicates proofsTuring Machines: Definition•A Turing Machine consists ofoA DFA to store the machine state, called the controlleroAn array that is infinitely long in both directions, called the tapeoA pointer to some particular cell in the array, called the headOperation•The head begins at cell 0 on the tape•The DFA begins in some initial state•Symbols from some alphabet are written on a finite portion of the tape, beginning at cell 1Operation•At each step, the machine uses as input:oThe state of the controlleroThe symbol written on the cell which the head is at•Using this, the machine will:oTransition to some state in the DFA (possibly the same state)oWrite some symbol (possibly the same symbol) on the tapeoMove the head left or right one cellTwo Flavors!•The machine will stop computation if the DFA enters one of a pre-defined set of "halting" states•A "decision" machine will, if it reaches a halting state, output either "Yes" or "No" (i.e. there are "accepting" and "rejecting" halt states)•A "function" machine will, if it reaches a halting state, have some string of symbols written on the tape. This string of symbols is the output of the functionExample: Doubling a Number 1 0 1012345Notation: (old symbol, new symbol, direction to move)"epsilon" denotes empty cell, "H" denotes halting state(s)Example: Doubling a Number 1 0 1012345Example: Doubling a Number 1 0 1012345Example: Doubling a Number 1 0 1012345Example: Doubling a Number 1 0 1012345Example: Doubling a Number 1 0 1012345Example: Doubling a Number 1 0 1012345Example: Doubling a Number 1 0 012345Example: Doubling a Number 1 0 1012345Example: Doubling a Number 1 0 1012345Example: Doubling a Number 1 0 1012345Example: Doubling a Number 1 0 1012345Example: Doubling a Number 1 0 1012345Example: Doubling a Number 0 1012345Example: Doubling a Number 1 0 1012345Example: Doubling a Number 1 0 1012345Example: Doubling a Number 1 0 1012345Example: Doubling a Number 0 1 0 1012345TM vs DFA•Is a decision machine more powerful than a DFA?•Yes!•Claim: A decision machine can recognize the set {anbn | n >= 0}Example: anbnExample: anbn a a b b012345Example: anbn a a b b012345Example: anbn a b b012345Example: anbn a b b012345Example: anbn a b b012345Example: anbn a b b012345Example: anbn a b b012345Example: anbn a b 012345Example: anbn a b 012345Example: anbn a b 012345Example: anbn a b 012345Example: anbn b 012345Example: anbn b 012345Example: anbn b 012345Example: anbn 012345Example: anbn 012345Correctness•Every time we reach the bottom-right state, the number of "b"s deleted equals the number of "a"sCorrectness 012345Correctness•Every time we reach the bottom-right state, the number of "b"s deleted equals the number of "a"s•If there are more "a"s, it crashes right after deleting the last "b"Correctness a 012345No "a" transition!Correctness•Every time we reach the bottom-right state, the number of "b"s deleted equals the number of "a"s•If there are more "a"s, it crashes right after deleting the last "b"•If there are more "b"s, it crashes in the bottom-right state after scanning to the left of the "b"sCorrectness b 012345No epsilon transition!Correctness•Every time we reach the bottom-right state, the number of "b"s deleted equals the number of "a"s•If there are more "a"s, it crashes right after deleting the last "b"•If there are more "b"s, it crashes in the bottom-right state after scanning to the left of the "b"s•If NO "a"s, crashes immediatelyCorrectness b b b 012345No "b" transition!Correctness•Every time we reach the bottom-right state, the number of "b"s deleted equals the number of "a"s•If there are more "a"s, it crashes right after deleting the last "b"•If there are more "b"s, it crashes in the bottom-right state after scanning to the left of the "b"s•If NO "a"s, crashes immediately•If no "b"s, crashes after reading the "a"sCorrectness a a a 012345No epsilon transition!Definitions•A set is recursively enumerable if there is a decision machine which answers "yes" if and only if the input belongs to the set•A function f is computable or recursive if there is a function machine that, when given input x, produces output f(x)Interlude: What is an "algorithm"?•"A precise step-by-step plan for a computational procedure that begins with an input value and yields an output value in a finite number of steps."-Corbin, Leiserson, Rivest. "Introduction to Algorithms"•Turing machines can capture this notion precisely!Algorithms on a TM•Given a human-comprehensible goal, encode the input into some alphabet•Define the steps of the algorithm as a DFA•Put the input on a tape•Let the Turing Machine run•Translate the outputObjection•Why not just use a programming language, such as C?•As it turns out, writing a C program is just using a computer to build a Turing Machine for youAlgorithms on a TM•Given a human-comprehensible goal, encode the
View Full Document
Unlocking...