Slide 1MenuUniversal ComputationDon’t search for T, search for ifFinding the Truthand and or?Lambda Calculus is a Universal Computer?Computability in Theory and Practice (Intellectual Computability Discussion on TV Video)Ali G Multiplication ProblemSlide 10Slide 11What about C++?Ali G was Right!Slide 14What is 42?Meaning of NumbersSlide 17Meaning of ZeroIs this enough?Can we define lambda terms that behave like zero, zero?, pred and succ?Numbers are Lists...Making Pairscons and carcdr too!Null and null?Slide 26CountingSlide 28ArithmeticLambda Calculus is a Universal ComputerWay to Keep GoingSlide 32Universal ComputerChargeDavid Evanshttp://www.cs.virginia.edu/evansCS150: Computer ScienceUniversity of VirginiaComputer ScienceClass 32:Computability in Theory and Practice2CS150 Fall 2005: Lecture 32: ComputabilityMenu•Lambda Calculus Review•Computability in Theory and Practice•Learning to Count3CS150 Fall 2005: Lecture 32: ComputabilityUniversal Computationz z z z z z z z z z z z z z z zz z z z1StartHALT), X, L2: look for (#, 1, -), #, R(, #, L(, X, R#, 0, -Finite State MachineRead/Write Infinite TapeMutable ListsFinite State MachineNumbers to keep track of stateProcessingWay of making decisions (if)Way to keep goingTo prove Lambda Calculus is as powerful as a UTM, we must show we can make everything we need to simulate any TM.4CS150 Fall 2005: Lecture 32: ComputabilityDon’t search for T, search for ifT  x (y. x)  xy. xF  x ( y. y))if  pca . pca5CS150 Fall 2005: Lecture 32: ComputabilityFinding the TruthT  x . (y. x)F  x . (y. y)if  p . (c . (a . pca))) if T M N ((pca . pca) (xy. x)) M N (ca . (x.(y. x)) ca)) M N  (x.(y. x)) M N (y. M )) N  MIs the if necessary?6CS150 Fall 2005: Lecture 32: Computabilityand and or?and  x (y. if x y F))or  x (y. if x T y))7CS150 Fall 2005: Lecture 32: ComputabilityLambda Calculus is a Universal Computer?z z z z z z z z z z z z z z z zz z z z1StartHALT), X, L2: look for (#, 1, -), #, R(, #, L(, X, R#, 0, -Finite State Machine• Read/Write Infinite Tape? Mutable Lists• Finite State Machine? Numbers to keep track of state• ProcessingWay of making decisions (if)? Way to keep going8CS150 Fall 2005: Lecture 32: ComputabilityComputability in Theory and Practice(Intellectual Computability Discussion on TV Video)9CS150 Fall 2005: Lecture 32: ComputabilityAli G Multiplication Problem•Input: a list of 2 numbers with up to d digits each•Output: the product of the 2 numbersIs it decidable?Yes – a straightforward algorithmsolves it.Is it tractable? (how much work?)Yes – it using elementary multiplication techniques it is O(d2)Can real computers solve it?12CS150 Fall 2005: Lecture 32: ComputabilityWhat about C++?int main (void){ int alig = 999999999; printf ("Value: %d\n", alig); alig = alig * 99; printf ("Value: %d\n", alig); alig = alig * 99; printf ("Value: %d\n", alig); alig = alig * 99; printf ("Value: %d\n", alig);}Value: 999999999Value: 215752093Value: -115379273Value: 1462353861Results from SunOS 5.8:13CS150 Fall 2005: Lecture 32: ComputabilityAli G was Right!•Theory assumes ideal computers:–Unlimited, perfect memory–Unlimited (finite) time•Real computers have:–Limited memory, time, power outages, flaky programming languages, etc.–There are many decidable problems we cannot solve with real computer: the numbers do matter14CS150 Fall 2005: Lecture 32: ComputabilityLambda Calculus is a Universal Computer?z z z z z z z z z z z z z z z zz z z z1StartHALT), X, L2: look for (#, 1, -), #, R(, #, L(, X, R#, 0, -Finite State Machine• Read/Write Infinite Tape? Mutable Lists• Finite State Machine? Numbers to keep track of state• ProcessingWay of making decisions (if)? Way to keep going15CS150 Fall 2005: Lecture 32: ComputabilityWhat is 42?42forty-twoXLIIcuarenta y dos16CS150 Fall 2005: Lecture 32: ComputabilityMeaning of Numbers•“42-ness” is something who’s successor is “43-ness”•“42-ness” is something who’s predecessor is “41-ness”•“Zero” is special. It has a successor “one-ness”, but no predecessor.17CS150 Fall 2005: Lecture 32: ComputabilityMeaning of Numberspred (succ N)  Nsucc (pred N)  Nsucc (pred (succ N))  succ N18CS150 Fall 2005: Lecture 32: ComputabilityMeaning of Zerozero? zero  T zero? (succ zero)  F zero? (pred (succ zero))  T19CS150 Fall 2005: Lecture 32: ComputabilityIs this enough?•Can we define add with pred, succ, zero? and zero?add  xy.if (zero? x) y (add (pred x) (succ y))20CS150 Fall 2005: Lecture 32: ComputabilityCan we define lambda terms that behave likezero, zero?, pred and succ?Hint: what if we had cons, car and cdr?21CS150 Fall 2005: Lecture 32: ComputabilityNumbers are Lists...zero?  null?pred  cdr succ   x . cons F x22CS150 Fall 2005: Lecture 32: ComputabilityMaking Pairs(define (make-pair x y) (lambda (selector) (if selector x y))) (define (car-of-pair p) (p #t)) (define (cdr-of-pair p) (p #f))23CS150 Fall 2005: Lecture 32: Computabilitycons and carcons  x.y.z.zxy cons M N = (x.y.z.zxy) M N   (y. z.zMy) N   z.zMN car  p.p Tcar (cons M N)  car (z.zMN)  (p.p T) (z.zMN)   (z.zMN) T   TMN   (x .  y. x) MN   (y. M)N   MT  x . y. x24CS150 Fall 2005: Lecture 32: Computabilitycdr too!cons  xyz.zxy car  p.p Tcdr  p.p Fcdr cons M Ncdr z.zMN = (p.p F) z.zMN   (z.zMN) F   FMN   N25CS150 Fall 2005: Lecture 32: ComputabilityNull and null?null  x.T null?  x.(x y.z.F)null? null  x.(x y.z.F) (x. T)   (x. T)(y.z.F)   T26CS150 Fall 2005: Lecture 32: ComputabilityNull and null?null  x.T null?  x.(x y.z.F)null? (cons M N)  x.(x y.z.F) z.zMN   (z.z MN)(y.z.F)   (y.z.F) MN   F27CS150 Fall 2005: Lecture 32: ComputabilityCounting0  null1  cons F 02  cons F 13  cons F 2...succ  x.cons F xpred  x.cdr x28CS150 Fall 2005: Lecture 32: Computability42 = xy.(z.z xy) xy. y xy.(z.z xy) xy. y xy.(z.z xy) xy. y xy.(z.z xy) xy. y xy.(z.z xy) xy. y xy.(z.z xy) xy. y xy.(z.z xy) xy. y