Universality and Computability2Fundamental QuestionsQ. What is a general-purpose computer?Q. Are there limits on the power of digital computers?Q. Are there limits on the power of machines we can build?Pioneering work in the 1930s.•Princeton == center of universe.•Automata, languages, computability, universality, complexity, logic.David Hilbert Kurt GödelAlan Turing Alonzo Church John von Neumann7.4 Turing MachinesAlan Turing (1912-1954)4Turing MachineDesiderata. Simple model of computation that is "as powerful" as conventional computers.Intuition. Simulate how humans calculate.Ex. Addition.0 0 0 00 0 0 10 0 0 02 3 4 50 0 + 30 0 0 01 4 1 50 0 0 00 0 06 0 09 0 00 0 00 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 05Last lecture: DFATape.•Stores input.•One arbitrarily long strip, divided into cells.•Finite alphabet of symbols.Tape head.•Points to one cell of tape.•Reads a symbol from active cell.•Moves right one cell at a time.tape headtape1 1 1 0 1 1 0 1 1 0 …… 06This lecture: Turing machineTape.•Stores input, output, and intermediate results.•One arbitrarily long strip, divided into cells.•Finite alphabet of symbols.Tape head.•Points to one cell of tape.•Reads a symbol from active cell.•Writes a symbol to active cell.•Moves left or right one cell at a time.tape headtapetape headtape# 1 1 0 0 + 1 0 1 1 # ……7Last lecture: Deterministic Finite State Automaton (DFA)Simple machine with N states.•Begin in start state.•Read first input symbol.•Move to new state, depending on current state and input symbol. •Repeat until last input symbol read.•Accept input string if last state is labeled Y.YNNb b a a a b b b a a b b a b bb b a a b b a b bInputDFA 8This lecture: Turing MachineSimple machine with N states.•Begin in start state.•Read first input symbol.•Move to new state and write new symbol on tape, depending on current state and input symbol.•Move tape head left if state is labeled L, right if state is labeled R. •Repeat until entering a state labelled H.•Accept input string state is labeled Y, reject if Nb b a a b b a b b# # 1 0 1 1 1 0 1Input1 : 0HL# : 10 : 11 : 0DFAif in this state and tape head is 1: · write a 0 · stay in this state · move tape head left9TM Exampleb b a a b b a b b# # 1 0 1 1 1 0 0Input1 : 0HL# : 10 : 11 : 0DFAif in this state and tape head is 0: · write a 1 · go to other state · haltSimple machine with N states.•Begin in start state.•Read first input symbol.•Move to new state and write new symbol on tape, depending on current state and input symbol.•Move tape head left if state is labeled L, right if state is labeled R. •Repeat until entering a state labeled H.•Accept input string state is labeled Y, reject if N10TM Exampleb b a a b b a b b# # 1 0 1 1 1 1 0Output1 : 0HL# : 10 : 11 : 0DFASimple machine with N states.•Begin in start state.•Read first input symbol.•Move to new state and write new symbol on tape, depending on current state and input symbol.•Move tape head left if state is labeled L, right if state is labeled R. •Repeat until entering a state labeled H.•Accept input string state is labeled Y, reject if N11TM Exampleb b a a b b a b b# # 1 0 1 1 1 1 0Output1 : 0HL# : 10 : 11 : 0DFAb b a a b b a b b# # 1 0 1 1 1 0 1InputSimple machine with N states.•Begin in start state.•Read first input symbol.•Move to new state and write new symbol on tape, depending on current state and input symbol.•Move tape head left if state is labeled L, right if state is labeled R. •Repeat until entering a state labeled H.•Accept input string state is labeled Y, reject if N12Turing Machine: Initialization and TerminationInitialization. Set input on some portion of tape; set tape head.Termination. Stop if enter yes, no, or halt state.Output. Contents of tape.Note: infinite loop possibletape head# 1 0 1 0 + 1 1 1 1 # ……tape13TM Example 1: Binary Increment# 1 0 1 1 # …1 : 0…HL# : 10 : 11 : 014TM Example 2: Binary Counter# # # # # # …1 : 0…RL0 : 11 : 0# : ## : 115TM Example 3: Binary Decrement# 1 1 0 0 # …0 : 1HL0 : 11 : 0…16TM Example 3: Binary Decrement# 0 0 0 0 # …0 : 1HL0 : 11 : 0…Q. What happens if we try to decrement 0 ?17TM Example 4: Binary Adder# 1 0 1 0 + 1 1 1 1 # …find right end of yadd one to xsubtract one from y find plus sign1 : 00 : 1…x yhaltclean up1 : #RLLLRH# : 10 : 10 : 11 : 0+ : +1 : 0# : ## : #+ : #1 : #Ex. Use simulator to understand how this TM works.7.5 Universality19Universal Machines and TechnologiesiPodiMacPrinterDell PCXboxTivoTuring machine TOYJava languageMS ExcelPython languageBlackberryQuantum computer DNA computerDiebold voting machine20Program and DataData. Sequence of symbols (interpreted one way).Program. Sequence of symbols (interpreted another way).Ex 1. A compiler is a program that takes a program in one languageas input and outputs a program in another language.Javamachine languagepublic class HelloWorld{ public static void main(String[] args) { System.out.println("Hello, World"); }}is DATA to a compilerYour program21Data. Sequence of symbols (interpreted one way).Program. Sequence of symbols (interpreted another way).Ex 2. A simulator is a program that takes a program for one machineas input and simulates the operation of that program.% more adder.tur vertices2 R0 L1 L3 L4 R5 Hedges0 0 0 10 1 1 00 4 + #1 3 + +2 0 # #3 2 # 13 2 0 13 3 1 04 4 1 #4 5 # #tape[1] 0 1 0 + 1 1 1 1Program and Data# 1 0 1 0 + 1 1 1 1 # ……is a PROGRAM!Data forsimulator22Universal Turing MachineTuring machine M. Given input tape x, Turing machine M outputs M(x).TM intuition. Software program that solves one particular problem.MxM(x)… # 0 1 1 # …data x23Universal Turing MachineTuring machine M. Given input tape x, Turing machine M outputs M(x).Universal Turing machine U. Given input tape with x and M,universal Turing machine U outputs M(x).TM intuition. Software program that solves one particular problem.UTM intuition. Hardware platform that can implement any algorithm.UMxM(x)MxM(x)… # 0 1 1 # …… # 0 1 1 # 1 0 1 1 # …data x data x program M24Universal Turing MachineConsequences. Your laptop (a UTM) can do any computational task.•Java programming. •Pictures, music, movies, games.•Email, browsing, downloading files, telephony.•Word-processing, finance, scientific computing.•…even tasks not yet contemplatedwhen laptop was purchasedWenger Giant Swiss Army Knife25Universal