UVA CS 150 - Class 32- Computabilit y in Theory and Practice (34 pages)

Previewing pages 1, 2, 16, 17, 18, 33, 34 of 34 page document View the full content.
View Full Document

Class 32- Computabilit y in Theory and Practice



Previewing pages 1, 2, 16, 17, 18, 33, 34 of actual document.

View the full content.
View Full Document
View Full Document

Class 32- Computabilit y in Theory and Practice

100 views


Pages:
34
School:
University Of Virginia
Course:
Cs 150 - Computer Science
Computer Science Documents
Unformatted text preview:

Class 32 Computabilit y in Theory and Practice CS150 Computer Science University of Virginia Computer Science David Evans http www cs virginia edu evans Menu Lambda Calculus Review Computability in Theory and Practice Learning to Count CS150 Fall 2005 Lecture 32 Computability 2 Universal Computation z z z z z z z z z X L R L 2 look for 1 Start X R 1 HAL T 0 Finite State Machine z z z z z z z z z z Read Write Infinite Tape Mutable Lists Finite State Machine Numbers to keep track of state Processing Way of making decisions if Way to keep going To prove Lambda Calculus is as powerful as a UTM we must show we can make everything we need to simulate any TM CS150 Fall 2005 Lecture 32 Computability z 3 Don t search for T search for if T x y x xy x F x y y if pca pca CS150 Fall 2005 Lecture 32 Computability 4 Finding the Truth T x y x F x y y if p c a pca Is the if necessary 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 M CS150 Fall 2005 Lecture 32 Computability 5 and and or and x y if x y F or x y if x T y CS150 Fall 2005 Lecture 32 Computability 6 Lambda Calculus is a Universal Computer z z z z z z z z z z z z z z z z z z z z X L R L 2 look for 1 Start X R 1 HAL T 0 Finite State Machine CS150 Fall 2005 Lecture 32 Computability Read Write Infinite Tape Mutable Lists Finite State Machine Numbers to keep track of state Processing Way of making decisions if Way to keep going 7 Computability in Theory and Practice Intellectual Computability Discussion on TV Video CS150 Fall 2005 Lecture 32 Computability 8 Ali G Multiplication Problem Input a list of 2 numbers with up to d digits each Output the product of the 2 numbers Is it decidable Yes a straightforward algorithm solves it Is it tractable how much work Yes it using elementary multiplication techniques it is O d2 Can real computers solve it CS150 Fall 2005 Lecture 32 Computability 9 What about C int main void int alig 999999999 printf Value d n alig alig 99 printf Value d n alig alig 99 printf Value d n alig alig 99 printf Value d n Results from SunOS 5 8 alig Value 999999999 Value 215752093 alig Value 115379273 alig Value 1462353861 alig CS150 Fall 2005 Lecture 32 Computability 12 Ali 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 matter CS150 Fall 2005 Lecture 32 Computability 13 Lambda Calculus is a Universal Computer z z z z z z z z z z z z z z z z z z z z X L R L 2 look for 1 Start X R 1 HAL T 0 Finite State Machine CS150 Fall 2005 Lecture 32 Computability Read Write Infinite Tape Mutable Lists Finite State Machine Numbers to keep track of state Processing Way of making decisions if Way to keep going 14 What is 42 42 XLII forty two cuarenta y dos CS150 Fall 2005 Lecture 32 Computability 15 Meaning 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 CS150 Fall 2005 Lecture 32 Computability 16 Meaning of Numbers pred succ N N succ pred N N succ pred succ N succ N CS150 Fall 2005 Lecture 32 Computability 17 Meaning of Zero zero zero T zero succ zero F zero pred succ zero T CS150 Fall 2005 Lecture 32 Computability 18 Is this enough Can we define add with pred succ zero and zero add xy if zero x y add pred x succ y CS150 Fall 2005 Lecture 32 Computability 19 Can we define lambda terms that behave like zero zero pred and succ Hint what if we had cons car and cdr CS150 Fall 2005 Lecture 32 Computability 20 Numbers are Lists zero null pred cdr succ x cons F x CS150 Fall 2005 Lecture 32 Computability 21 Making 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 CS150 Fall 2005 Lecture 32 Computability 22 cons and car cons x y z zxy cons M N x y z zxy M N y z zMy N z zMN car p p T T x y x car cons M N car z zMN p p T z zMN z zMN T TMN x y x MN y M N M CS150 Fall 2005 Lecture 32 Computability 23 cdr too cons xyz zxy car p p T cdr p p F cdr cons M N cdr z zMN p p F z zMN z zMN F FMN N CS150 Fall 2005 Lecture 32 Computability 24 Null 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 T CS150 Fall 2005 Lecture 32 Computability 25 Null 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 F CS150 Fall 2005 Lecture 32 Computability 26 Counting 0 null 1 cons F 0 2 cons F 1 3 cons F 2 succ x cons F x pred x cdr x CS150 Fall 2005 Lecture 32 Computability 27 42 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 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 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 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 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 …


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Class 32- Computabilit y in Theory and Practice 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 Class 32- Computabilit y in Theory and Practice 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?