MIT OpenCourseWarehttp://ocw.mit.edu For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. 6.004 Computation Structures Spring 2009 L12 -Models of Computation 1 6.004 – Spring 20093/17/09Programmability from silicon to bits 011010011011100100100011100011the Big Ideas ofComputer Science modified 3/16/09 16:15 L12 -Models of Computation 2 6.004 – Spring 20093/17/096.004 Roadmap Sequential logic: FSMs+4+C*4ASEL01Data Memory RDWDAdrR/WWDSEL012WARc <25:21>01XPPCSELPCJT+4InstructionMemoryADRb: <15:11>Ra <20:16>RA2SELRc <25:21>+RegisterFileRA1RA2RD1RD2BSEL01C: <15:0>C: <15:0>sign-extendedZALUABJTWAWDWEC: <15:0> << 2sign-extendedALUFNControl LogicZASELBSELPCSELRA2SELWDSELALUFNWr+401Wr01234XAdrILLOPWASELWASELIRQWERFWERF00CPU Architecture: interpreter for coded programs Programmability: Models •Interpretation; Programs; Languages; Translation •Beta implementation •Pipelined Beta •Software conventions •Memory architectures Fets & voltages Logic gates Combinational logic circuits L12 -Models of Computation 3 6.004 – Spring 20093/17/09FSMs as Programmable Machines ROM-based FSM sketch: Given i, s, and o, we need a ROM organized as: 2i+s words x (o+s) bitsis0...010...000...0010110011o2i+ssN+1osNiinputsoutputs2(o+s)2i+s(some may be equivalent) An FSM’s behavior is completely determined by its ROM contents. So how many possible i-input, o-output, FSMs with s-state bits exist? L12 -Models of Computation 4 6.004 – Spring 20093/17/09Big Idea #1: FSM Enumeration GOAL: List all possible FSMs in some canonical order. • INFINITE list, but • Every FSM has an entry and an associated index. 0...010...000...0010110011sN+1osNiinputsoutputs28FSMs264Every possible FSM can be associated with a number. We can discuss the ith FSM What if s=2,i=o=1?? L12 -Models of Computation 5 6.004 – Spring 20093/17/09Some Perennial Favorites... FSM837modulo 3 counter FSM10774-bit counter FSM1537lock for 6.004 Lab FSM89143Steve’s digital watch FSM22698469884Intel Pentium CPU – rev 1 FSM784362783Intel Pentium CPU – rev 2 FSM72698436563783Intel Pentium II CPU Reality: The integer indexes of actual FSMs are muchbigger than the examples above. They must include enough information to constitute a complete description of each device’s unique structure. L12 -Models of Computation 6 6.004 – Spring 20093/17/09Models of Computation The roots of computer science stem from the study of many alternative mathematical “models” of computation, and study of the classes of computations they could represent. An elusive goal was to find an “ultimate” model, capable of representing all practical computations... We’ve got FSMs ... what else do we need? •switches •gates •combinational logic •memories •FSMsAre FSMs the ultimate digital computing device? L12 -Models of Computation 7 6.004 – Spring 20093/17/09FSM Limitations Despite their usefulness and flexibility, there exist common problems that cannot be computed by FSMs. For instance: Paren Checker “(()())”OKParen Checker “(())())”NixWell-formed Parentheses Checker: Given any string of coded left & right parens, outputs 1 if it is balanced, else 0. Simple, easy to describe. Is this device equivalent to one of our enumerated FSMs??? PROBLEM: Requires ARBITRARILY many states, depending on input. Must "COUNT" unmatched LEFT parens. An FSM can only keep track of a finite number of unmatched parens: for every FSM, we can find a string it can’t check. NO!L12 -Models of Computation 8 6.004 – Spring 20093/17/09Big Idea #2: Turing Machines Alan Turing was one of a group of researchers studying alternative models of computation. He proposed a conceptual model consisting of an FSM combined with an infinite digital tape that could be read and written at each step.Turing’s model (like others of the time) solves the "FINITE" problem of FSMs.S11110000100000000S20,(1,R) 0,(1,L) 1,Halt1,(1,L)L12 -Models of Computation 9 6.004 – Spring 20093/17/09A Turing machine Example Turing Machine Specification • Doubly-infinite tape • Discrete symbol positions • Finite alphabet – say {0, 1} • Control FSM INPUTS: Current symbol OUTPUTS:write 0/1 move Left/Right • Initial Starting State {S0} • Halt State {Halt} A Turing machine, like an FSM, can be specified with a truth table. The following Turing Machine implements a unary (base 1) incrementer. Current State InputWrite Tape Move Tape NextState S0S1S0S110101110RLLRS0S1S1HALT 00001101101OK, but how about real computations... like fact(n)? L12 -Models of Computation 10 6.004 – Spring 20093/17/09Turing Machine Tapes as Integers Canonical names for bounded tape configurations: That’s just Turing Machine 347 operating on tape 51 0001111000b0b1b2b4b6b8b10b3b5b7......FSM347Encoding: starting at current position, build a binary integer taking successively higher-order bits from right and left sides. If nonzero region is bounded, eventually all 1’s will be incorporated into the resulting integer representation. L12 -Models of Computation 11 6.004 – Spring 20093/17/09TMs as Integer Functions Turing Machine Ti operating on Tape x, where x = …b8b7b6b5b4b3b2b1b0I wonder if a TM can compute EVERY integer function... y = Ti[x]x: input tape configuration y: output tape configuration Meanwhile,Turing’s buddies Were busy too… L12 -Models of Computation 12 6.004 – Spring 20093/17/09Alternative models of computation Turing Machines [Turing] FSM i011000100Turing Lambda calculus [Church, Curry, Rosser...] x.y.xxy(lambda(x)(lambda(y)(x (x y)))) Church Recursive Functions [Kleene] (define (fact n) (... (fact (-n 1)) ...) Kleene Production Systems [Post, Markov] IF pulse=0 THEN patient=dead Post L12 -Models of Computation 13 6.004 – Spring 20093/17/09The 1st Computer Industry Shakeout Here’s a TM that computes SQUARE ROOT! 0001111000FSMhow am I going to beat that?L12 -Models of Computation 14 6.004 – Spring 20093/17/09And the battles raged Here’s a Lambda Expression that does the same thing... ... and here’s one that computes the nth root for ANY n!((x) .....)((x n) .....)maybe if I gave away a microwave oven with every Turing Machine... RESULT: an N-way TIE! CONTEST: Which model computes more functions? L12 -Models of Computation 15 6.004 – Spring 20093/17/09Big Idea #3: Computability FACT: Each model studied is capable of computing exactly the same set of integer functions! Proof Technique: Constructions that translate between models BIG IDEA: Computability, independent of computation scheme chosen Church's Thesis: Every discrete function computable by ANY realizable machine is computable by some Turing machine. unproved, but universally accepted... L12 -Models of Computation 16 6.004 – Spring 20093/17/09Computable Functions Representation Tricks: •Multi-argument functions? to compute fk(x,y), use =nteger whose even bits come from x, and whose oddbits come from y; whencefK(x, y) = TK[] •Data types: Can encode characters, strings, floats, ... as integers. •Alphabet size: use groups of N bits for 2N symbols f(x)computable <=> for some k, all x: f(x) = TK[x] fK(x)Equivalently: f(x) computable on Cray, Pentium, in C, Scheme, Java, ... L12 -Models of Computation 17 6.004 – Spring 20093/17/09Enumeration of Computable functions fm(n)37234283103311112fifi(0)fi(1)fi(n)fi(2)......f0f1f2fm..................................................................Conceptual table of ALL Turing Machine behaviors...VERTICAL AXIS: Enumeration of TM’s (computable functions) HORIZONTAL AXIS: Enumeration of input tapes. ENTRY AT (n, m): Result of applying mth TM to argument n INTEGER k: TM halts, leaving k on tape. : TM never halts. aren’t all well-defined integer functions computable? NO! there are simply too many integer functions to fit in our enumeration! L12 -Models of Computation 18 6.004 – Spring 20093/17/09THEOREM: fH is different from every function in our enumeration of computable functions; hence it cannot be computed by any Turing Machine. Uncomputable Functions Unfortunately, not every well-defined integer function is computable. The most famous such function is the so-called Halting function, fH(k, j), defined by: fH(k, j) = 1 if Tk[j] halts; 0 otherwise. fH(k, j) determines whether the kth TM halts when given a tape containing j. PROOF TECHNIQUE: “Diagonalization” (after Cantor, Gödel)•If fH is computable, it is equivalent to some TM (say, TH).•Using TH as a component, we can construct another TM whose behavior differs from every entry in our enumeration and hence must not be computable. •Hence fH cannot be computable. L12 -Models of Computation 19 6.004 – Spring 20093/17/09Why fH is uncomputable If fH is computable, it is equivalent to some TM (say, TH):THkj1 iff Tk[j] halts, else 0 Then TN (N for “Nasty”), which must be computable if TH is: TNTH?10LOOP HALT TN[x]:LOOPS if Tx[x] halts; HALTS if Tx[x] loops Finally, consider giving N as an argument to TN:TN[N]:LOOPS if TN[N] halts; HALTS if TN[N] loops TN can’t be computable, hence TH can’t either! xL12 -Models of Computation 20 6.004 – Spring 20093/17/09Footnote: Diagonalization (clever proof technique used by Cantor, Gödel, Turing)fm(n)37234283103311112fifi(0)fi(1)fi(n)fi(2)......f0f1f2fm..................................................................If TH exists, we can use it to construct TN. Hence TN is computable if TH is. (informally we argue by Church’s Thesis; but we can show the actual TNconstruction, if pressed) Why TN can’t be computable: TN differs from every computable function for at least one argument – along the diagonal of our table.Hence TN can’t be among the entries in our table! Hence no such TH can be constructed, even in theory. Computable Functions: A TINY SUBSET of all Integer functions! L12 -Models of Computation 21 6.004 – Spring 20093/17/09Doom. MP3s. Windows. Payroll accounting. Blue screen crashes. 6.004. GP Computers Brief History of Mathematics (6.004 view) “yeah? then I’m the Pope” -Russell Math = Bunk??? “This statement can’t be proved” -Godel { consistency, completeness }… … take your pick “OK, here’s the program” -Hilbert Search for “perfect” logic: consistent, complete “Some things just don’t compute…” -Turing computability {I’ts all { sets }} bliss“All you need, In theory…” -Turing universality “Let’s build this baby…” -von Neumann von Neumann architecture L12 -Models of Computation 22 6.004 – Spring 20093/17/09meanwhile... Turing machines Galore! FSM011000100Multiplication FSM011000100Sorting FSM011000100Factorization FSM011000100Primality Test Is there an alternative to Infinitely many, ad-hoc Turing Machines? “special-purpose” Turing Machines.... L12 -Models of Computation 23 6.004 – Spring 20093/17/09The Universal Function OK, so there are uncomputable functions – infinitely many of them, in fact. Here’s an interesting candidate to explore: the Universal function, U, defined by SURPRISE! U is computable by a Turing Machine: TUkjTk[j] In fact, there are infinitely many such machines. Each is capable of performing any computation that can be performed by any TM!it sure would be neat to have a single, general-purpose machine... U(k, j) = Tk[j] Could this be computable??? L12 -Models of Computation 24 6.004 – Spring 20093/17/09Big Idea #4: Universality TUkjTk[j] What’s going on here? k encodes a “program” – a description of some arbitrary machine. j encodes the input data to be used. TUinterprets the program, emulating its processing of the data! Turing Universality: The Universal Turing Machine is the paradigm for modern general-purpose computers! (cf: earlier special-purpose computers) •Basic threshold test: Is your machine Turing Universal? If so, it can emulate every other Turing machine! •Remarkably low threshold: UTMs with handfuls of states exist. •Every modern computer is a UTM (given enough memory) •To show your machine is Universal: demonstrate that it can emulate some known UTM. KEY IDEA: Interpretation.Manipulate coded representations of computing machines, rather than the machines themselves. L12 -Models of Computation 25 6.004 – Spring 20093/17/09Coded Algorithms: Key to CS data vs hardware Algorithms as data: enables COMPILERS: analyze, optimize, transform behavior SOFTWARE ENGINEERING: Composition, iteration, abstraction of coded behavior F(x) = g(h(x), p((q(x))) TCOMPILER-X-to-Y[PX] = PY, such that TX[PX, z] = TY[PY, z] LANGUAGE DESIGN: Separate specification from implementation •C, Java, JSIM, Linux, ... all run on X86, PPC, Sun, ... •Parallel development paths: •Language/Software design •Interpreter/Hardware design L12 -Models of Computation 26 6.004 – Spring 20093/17/09Summary Formal models (computability, Turing Machines, Universality) provide the basis for modern computer science: •Fundamental limits (what can’t be done, even given plenty of memory and time) •Fundamental equivalence of computation models •Representation of algorithms as data, rather than machinery •Programs, Software, Interpreters, Compilers, ... They leave many practical dimensions to deal with: •Costs: Memory size, Time Performance •ProgrammabilityNext step: Design of a practical interpreter!