15-251Great Theoretical Ideas in Computer ScienceLecture 21 - Dan KilgallinTuring MachinesGoalsDescribe the nature of computationMathematically formalize the behavior of a program running on a computer systemCompare the capabilities of different programming languagesTuring MachinesWhat 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: DefinitionA Turing Machine consists ofA DFA to store the machine state, called the controllerAn array that is infinitely long in both directions, called the tapeA pointer to some particular cell in the array, called the headOperationThe head begins at cell 0 on the tapeThe DFA begins in some initial stateSymbols from some alphabet are written on a finite portion of the tape, beginning at cell 1OperationAt each step, the machine uses as input:The state of the controllerThe symbol written on the cell which the head is atUsing this, the machine will:Transition to some state in the DFA (possibly the same state)Write some symbol (possibly the same symbol) on the tapeMove 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" statesA "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 DFAIs 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 012345CorrectnessEvery time we reach the bottom-right state, the number of "b"s deleted equals the number of "a"sCorrectness 012345CorrectnessEvery time we reach the bottom-right state, the number of "b"s deleted equals the number of "a"sIf there are more "a"s, it crashes right after deleting the last "b"Correctness a 012345No "a" transition!CorrectnessEvery time we reach the bottom-right state, the number of "b"s deleted equals the number of "a"sIf 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!CorrectnessEvery time we reach the bottom-right state, the number of "b"s deleted equals the number of "a"sIf 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"sIf NO "a"s, crashes immediatelyCorrectness b b b 012345No "b" transition!CorrectnessEvery time we reach the bottom-right state, the number of "b"s deleted equals the number of "a"sIf 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"sIf NO "a"s, crashes immediatelyIf no "b"s, crashes after reading the "a"sCorrectness a a a 012345No epsilon transition!DefinitionsA set is recursively enumerable if there is a decision machine which answers "yes" if and only if the input belongs to the setA 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 TMGiven a human-comprehensible goal, encode the input into some alphabetDefine the steps of the algorithm as a DFAPut the input on a tapeLet the Turing Machine runTranslate the outputObjectionWhy 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 TMGiven a human-comprehensible goal, encode the input into some alphabetDefine the steps of the algorithm as a DFAPut the input on a tapeLet the Turing Machine runTranslate the outputAlgorithms in CGiven a human-comprehensible goal, encode the input into some alphabetDefine the steps of the algorithm as a DFAPut the input on a tapeLet the Turing Machine runTranslate the outputAlgorithms in CGiven a human-comprehensible goal, encode the input into binaryDefine the steps of the algorithm as a DFAPut the input on a tapeLet the Turing Machine runTranslate the outputAlgorithms in CGiven a human-comprehensible goal, encode the input into binaryDefine the steps of the algorithm as a sequence of processor instructionsPut the input on a tapeLet the Turing Machine runTranslate the outputAlgorithms in CGiven a human-comprehensible goal, encode the input into binaryDefine the steps of the algorithm as a sequence of processor instructionsPut the input in computer memoryLet the Turing Machine runTranslate the outputAlgorithms in CGiven a human-comprehensible goal, encode the input into binaryDefine the steps of the algorithm
View Full Document
Unlocking...