DOC PREVIEW
UVA CS 150 - A Universal Computer

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

UVA CS 150 - A Universal Computer

Documents in this Course
Objects

Objects

6 pages

Load more
Download A Universal Computer
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view A Universal Computer and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view A Universal Computer 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?