Slide 1MenuMegabytes vs. MegatonsSlide 4If Nuclear Weapons followed Moore’s Law...Actual Nuclear WeaponsSlide 7Slide 8Running out of IdeasPost Production SystemsProduction SystemsThe MIU SystemMIU System ExampleSurvey SummaryVery Diverse ClassSurvey Responses ContinuedLanguagesWhat is a language?Linguist’s DefinitionLanguages and Formal SystemsWhat are languages made of?Does English have these?Slide 23Slide 24Backus Naur FormBNF ExampleSlide 27Most Essential SchemeChargeDavid Evanshttp://www.cs.virginia.edu/evansCS150: Computer ScienceUniversity of VirginiaComputer ScienceLecture 2: Formal SystemsandLanguagesMU!2Lecture 2: LanguageMenu•Nuclear Weapons•Questions from Lecture 1 Notes•Survey Summary•Formal Systems–MIU-system•Languages–English–Scheme3Lecture 2: LanguageMegabytes vs. Megatons•Computing: 30,000,000 times increase in power since 1969•Nuclear weapons?4Lecture 2: LanguageTsar Bomba 50 Megaton explosion, island in Arctic Sea, 19615Lecture 2: LanguageIf Nuclear Weapons followed Moore’s Law...•30M * 50 Megatons = 1.5 Teratons•1 Megaton TNT = 4.184 * 1015 Joules•1.5 Teratons TNT = 6.3 * 1021 Joules•Energy from Sun to Earth = 4 x 1018 Joules/ Year •One bomb today ~ all the energy to reach the Earth from the Sun since 400 AD6Lecture 2: LanguageActual Nuclear WeaponsHiroshima (12kt), Nagasaki (20kt)First H-Bomb (10Mt)Tsar Bomba (largest ever)B83 (1.2Mt), largestin currently active arsenal7Lecture 2: LanguageIf it takes 60 seconds to compute a photomosaic for Problem Set 1 today on a typical PC, estimate how long it will take CS150 students in 2010 to compute the same photomosaic? How long will it take in 2013? > (/ (* (- 2010 2007) 12) 18)2> (/ 60 (* 2 2))15> (/ (* (- 2013 2007) 12) 18)4> (/ 60 (* 2 2 2 2))15/4> (exact->inexact (/ 60 (* 2 2 2 2)))3.75Difference in years * 12 = number of monthsNumber of months / 18 = number of doublings according to Moore’s Law60 seconds today, 2 doublings by 201015 seconds in 201060 seconds today, 4 doublings by 20133.75 seconds in 2013Reality check: Moore’s “law” is just an “observation”. We’ll see one reason later today why it won’t continue forever.8Lecture 2: LanguageAre there any non-recursive natural languages? What would happen to a society that spoke one? Not for humans at least. They would run out of original things to say.Chimps and Dolphins are able to learn non-recursive “languages” (some linguists argue they are not really “languages”), but only humans can learn recursive languages.9Lecture 2: LanguageRunning out of Ideas“Its all been said before.”Eventually true for a non-recursive language.Never true for a recursive language. There is always something original left to say!10Lecture 2: LanguagePost Production Systems11Lecture 2: LanguageProduction Systems•Set of symbols–Primitives•Set of rules for manipulating symbols–Hofstadter: Rules of Production, Rules of Inference–Also: Rules of Combination12Lecture 2: LanguageThe MIU System•Symbols: M, I, U•Rules of Production: –Rule I: If you have a string ending in I, you can add a U at the end.–Rule II: Suppose you have Mx. Then you may add Mxx to your collection.–Rule III: If III occurs in one of the strings in your collection you may make a new string with U in place of III.–Rule IV: If UU occurs inside one of your strings, you can drop it.13Lecture 2: LanguageMIU System ExampleStart with MUI, produce MIURules of Production:Rule I: If you have a string ending in I, you can add a U at the end.Rule II: Suppose you have Mx. Then you may add Mxx to your collection.Rule III: If III occurs in one of the strings in your collection you may make a new string with U in place of III.Rule IV: If UU occurs inside one of your strings, you can drop it.14Lecture 2: LanguageSurvey Summary•53 Responses–63 are registered•Problem Set Partners–If you selected “Yes” for the question about wanting to be assigned a partner for PS1, you should have received an email from me telling you who your partner is–For PS2 everyone will be assigned a partner–For others, some you will choose, others you may be assigned15Lecture 2: LanguageVery Diverse Class•Years: 12 First, 15 Second, 18 Third, 7 Fourth+•Majors: –19 Computer Science–11 Undecided–7 Cognitive Science–3 Economics, Math–2 Psychology–1 Anthropology, Architecture, Commerce, Foreign Affairs, Media Studies, Music, Philosophy, Systems Engineering16Lecture 2: LanguageSurvey Responses Continued•Previous programming: 19 None, 32 Some•Food: 28 Bodos, 11 Krispy Kreme, 10 pizza, 1 Korean Food, 1 Outback, 1 Paccino’s, 1 Arch’s, 1 Dunkin Donuts•Topic: 18 Google Maps, 16 Facebook, 5 Second Life, 5 JavaSee course website (by Monday) for my responses to questions and survey summary17Lecture 2: LanguageLanguages18Lecture 2: LanguageWhat is a language?Webster:A systematic means of communicating ideas or feelings by the use of conventionalized signs, sounds, gestures, or marks having understood meanings.19Lecture 2: LanguageLinguist’s DefinitionA description of pairs (S, M), where S stands for sound, or any kind of surface forms, and M stands for meaning. A theory of language must specify the properties of S and M, and how they are related.(Charles Yang)20Lecture 2: LanguageLanguages and Formal SystemsWhat is the difference between a formal system and a language?With a language, the surface forms have meaning.Caveat: computer scientists often use language to mean just a set of surface forms.21Lecture 2: LanguageWhat are languages made of?•Primitives (almost all languages have these)–The simplest surface forms with meaning•Means of Combination (all languages have these)–Like Rules of Production for Formal Systems–Ways to make new surface forms from ones you already have•Means of Abstraction (all powerful languages have these)–Ways to use simple surface forms to represent complicated ones22Lecture 2: LanguageDoes English have these?•Primitives–Words (?)•e.g., “antifloccipoccinihilipilification” – not a primitive–Morphemes – smallest units of meaning•e.g., anti- (“opposite”)•Means of combination–e.g., Sentence ::= Subject Verb Object–Precise rules, but not the ones you learned in grammar schoolEnding a sentence with a preposition is something up with which we will not put. Winston Churchill23Lecture 2: LanguageDoes English have these?•Means of abstraction–Pronouns: she, he, it, they, which,