Slide 1Turing Machine: FSM + Infinite TapeTuring MachineAddingAdder TM (Start)Slide 6Slide 7Slide 8Slide 9Describing Finite State MachinesExample Turing MachineEnumerating Turing MachinesUniversal Turing MachineYes!Slide 15Church-Turing ThesisUniversal LanguageComplexity in Scheme-calculusWhat is Calculus?Real DefinitionLambda CalculusWhy?Evaluation RulesChargeDavid Evanshttp://www.cs.virginia.edu/evansCS150: Computer ScienceUniversity of VirginiaComputer ScienceLecture 37: Lecture 37: A Universal A Universal ComputerComputerPS8 returned at your project design review meetingsRemember to email your project descriptions before midnight tonight2Lecture 37: Universal Computing MachinesTuring Machine: FSM + Infinite Tape•Start: –FSM in Start State–Input on Infinite Tape–Tape head at start of input•Step:–Read current input symbol from tape–Follow transition rule from current state on input•Write symbol on tape•Move L or R one square•Update FSM state•Finish: Transition to halt state3Lecture 37: Universal Computing MachinesTuring Machine1Start2Input: #Write: #Move: # 1 0 1 1 0 1 1......1 0 1 1 0 1 1 1 #Input: 1Write: 0Move: Input: 1Write: 1Move: Input: 0Write: 0Move: 3Input: 0Write: #Move: 4Lecture 37: Universal Computing MachinesAdding•Input on tape: ...#nknk-1...n0+mlml-1...m0#.....–Number represented in binary•Output: ...#rdrd-1...r0#.....where r = n + mCan we implement addition with a TM?5Lecture 37: Universal Computing MachinesAdder TM (Start)1: look for +StartInput: +Write: +Move: L+, +, L2: look for digit1, 1, RX, X, L0, X, R1, X, R0, 0, R4: adding to 13: adding to 06Lecture 37: Universal Computing Machines1: look for +Start+, +, L2: look for digit1, 1, RX, X, L0, X, R1, X, R0, 0, R4: adding to 13: adding to 00, 0, R1, 1, R0, 0, R1, 1, R#, #, L5: look for digit#, #, L6: look for digit7Lecture 37: Universal Computing Machines2: look for digit1, X, R4: adding to 13: adding to 00, 0, R1, 1, R0, 0, R1, 1, R#, #, L5: look for digit#, #, L6: look for digitX, X, LX, X, L0, X, R7: 0+08: 0+11, X, R0, X, R1, X, R9: 1+18Lecture 37: Universal Computing Machines#, #, L5: look for digit#, #, L6: look for digitX, X, LX, X, L0, X, R7: 0+08: 0+11, X, R0, X, R1, X, R9: 1+121: return for next digits, carry 120: return for next digits, no carryX, X, R#, #, Rgo to end of answer digits, write 09Lecture 37: Universal Computing MachinesTuring Machinez z z z z z z z z z z z z z z zz z z zTuringMachine ::= < Alphabet, Tape, FSM >Alphabet ::= { Symbol* }Tape ::= < LeftSide, Current, RightSide >OneSquare ::= Symbol | #Current ::= OneSquareLeftSide ::= [ Square* ]RightSide ::= [ Square* ]Everything to left of LeftSide is #.Everything to right of RightSide is #.1StartHALT), X, L2: look for (#, 1, -), #, R(, #, L(, X, R#, 0, -Finite State Machine10Lecture 37: Universal Computing MachinesDescribing Finite State MachinesTuringMachine ::= < Alphabet, Tape, FSM >FSM ::= < States, TransitionRules, InitialState, HaltingStates >States ::= { StateName* }InitialState ::= StateName must be element of StatesHaltingStates ::= { StateName* } all must be elements of StatesTransitionRules ::= { TransitionRule* }TransitionRule ::= < StateName, ;; Current State OneSquare, ;; Current square StateName, ;; Next State OneSquare, ;; Write on tape Direction > ;; Move tapeDirection ::= L, R, #Transition Rule is a procedure:Inputs: StateName, OneSquareOutputs: StateName, OneSquare, Direction11Lecture 37: Universal Computing MachinesExample Turing MachineTuringMachine ::= < Alphabet, Tape, FSM >FSM ::= < States, TransitionRules, InitialState, HaltingStates >Alphabet ::= { (, ), X }States ::= { 1, 2, HALT }InitialState ::= 1HaltingStates ::= { HALT }TransitionRules ::= { < 1, ), 2, X, L >, < 1, #, HALT, 1, # >, < 1, ), #, R >, < 2, (, 1, X, R >, < 2, #, HALT, 0, # >, < 2, ), #, L >,}1StartHALT), X, L2: look for (), #, R (, #, L(, X, R#, 0, ##, 1, #12Lecture 37: Universal Computing MachinesEnumerating Turing Machines•Now that we’ve decided how to describe Turing Machines, we can number them•TM-5023582376 = balancing parens•TM-57239683 = even number of 1s•TM-3523796834721038296738259873 = Photomosaic Program•TM-3672349872381692309875823987609823712347823 = WindowsXPNot the real numbers – they would be much bigger!13Lecture 37: Universal Computing MachinesUniversal Turing MachineUniversalTuringMachineP Numberof TMIInput Tapealso, just a number!Output Tapefor runningTM-Pin tape ICan we make a Universal Turing Machine?14Lecture 37: Universal Computing MachinesYes!•People have designed Universal Turing Machines with–4 symbols, 7 states (Marvin Minsky)–4 symbols, 5 states –2 symbols, 22 states–18 symbols, 2 states–2 states, 5 symbols (Stephen Wolfram)•No one knows what the smallest possible UTM is15Lecture 37: Universal Computing MachinesManchester Illuminated Universal Turing Machine, #9 from http://www.verostko.com/manchester/manchester.html16Lecture 37: Universal Computing MachinesChurch-Turing Thesis•Any mechanical computation can be performed by a Turing Machine•There is a TM-n corresponding to every computable problem•We can any “normal” (classical mechanics) computer with a TM–If a problem is in polynomial time on a TM, it is in polynomial time on an iMac, Cray, Palm, etc.–But maybe not a quantum computer! (later class)17Lecture 37: Universal Computing MachinesUniversal Language•Is Scheme/Charme/Python as powerful as a Universal Turing Machine?•Is a Universal Turing Machine as powerful as Scheme/Charme/Python?Yes: show we can simulate a UTM with a Scheme programCan we simulate a Scheme interpreter with a TM?18Lecture 37: Universal Computing MachinesComplexity in Scheme•Special Forms–if, cond, define, etc.•Primitives–Numbers (infinitely many)–Booleans: #t, #f–Functions (+, -, and, or, etc.)•Evaluation Complexity–Environments (more than ½ of our eval code)Can we get rid of all this and still have a useful language?If we have lazy evaluation and don’t care about abstraction, we don’t need these.Hard to get rid of?19Lecture 37: Universal Computing Machines-calculusAlonzo Church, 1940(LISP was developed from -calculus, not the other way round.)term = variable | term term | (term) | variable . term20Lecture 37: Universal Computing MachinesWhat is Calculus?•In High School:d/dx xn = nxn-1 [Power Rule]d/dx (f + g) = d/dx f + d/dx g [Sum
View Full Document