1CS 172: Computability and ComplexityIntroduction and Course OverviewSanjit A. SeshiaEECS, UC BerkeleyAcknowledgments: L.von Ahn, L. Blum, M. Blum, R. JhalaS. A. Seshia 2A ProblemSuppose A ⊆⊆⊆⊆ {1, 2, …, 2n}TRUE or FALSE: There are always two numbers in A such that one divides the otherwith |A| = n+1(work out the answer with proof)2S. A. Seshia 3What we’ll do today• Introduction to course staff and students• Motivation• Course logistics• Basics of proof and finite automata• A quick survey at the end of class• Pick up– course information handout– survey formS. A. Seshia 4About MeB.Tech., Computer Sc. & Engg., IIT BombayM.S. & Ph.D., Computer Science, Carnegie Mellon University, PittsburghAssistant Professor, EECS, UC BerkeleyOffice: 566 Cory3S. A. Seshia 5My ResearchTheory Practice+Example: Fast satisfiability (SAT) solving used to build a better virus/worm detectorComputational Logic, AlgorithmsCAD for VLSI, Computer Security, Embedded Systems, DependabilityS. A. Seshia 6Class Introductions• Introduction to Omid Etesami (your GSI)• and the rest of you…4S. A. Seshia 7A 3-Question Course• Automata Theory:What are the mathematical models of computation?• Computability Theory:What problems can(not) computers solve?• Complexity Theory:What makes some problems computationally hard and others easy?S. A. Seshia 8More SuccinctlyThis course is about models of computationand the limits of computation5S. A. Seshia 9More SuccinctlyThis course is about models of computationand the limits of computationWHY SHOULD WE CARE?S. A. Seshia 10Motivation for this Course• Relevant for practical applications• Foundation for theoretical work • It’s fun!6S. A. Seshia 11S. A. Seshia 12Model: Free Body DiagramWhy build a model?7S. A. Seshia 13Model: Free Body DiagramAnalyzing a model helps us build reliable bridges, in a cost-effective & timely wayWhy not do the same for computers?S. A. Seshia 14Programs and Pushdown Automata• Sequential (single-threaded) programs can be mathematically modeled as “pushdown automata”– E.g., Microsoft’s Static Driver Verifier searches for bugs in device driver code after creating a pushdown automaton model of the program8S. A. Seshia 15Programs and Pushdown Automata• Variants of pushdown automata are even used in modeling structure of RNA!– This course is not just about computers, it’s about computation!S. A. Seshia 16Analyzing correctness of computers is hard!Limits of computation9S. A. Seshia 17Theoretically Useful• Mathematical models of computation give us systematic ways to think about computers – Independent of how they are implemented– So the results long outlast the specific machines (anybody remember VAX machines? 486-based PCs running Windows 95?)S. A. Seshia 18Course Logistics• The course webpage is the definitive source of informationwww.eecs.berkeley.edu/~sseshia/172/We’ll also use bSpace• 1 required textbook• 3 other references• All 4 under reserve in Engineering library10S. A. Seshia 19Grading & Policies• 10 homeworks: 30% weightage• 2 mid-terms: 20% each• 1 final: 30%• Homeworks assigned approx. weekly, due in class/drop-box– First homework out next Monday– No late homeworks– Must list collaborators and references• Important! See webpage for course policiesS. A. Seshia 20Back to the ProblemSuppose A ⊆⊆⊆⊆ {1, 2, …, 2n}TRUE or FALSE: There are always two numbers in A such that one divides the otherwith |A| = n+1TRUE11S. A. Seshia 21Got Proof?• Hint #1: the Pigeonhole PrincipleIf you put 4 pigeons in 3 holes, at least one hole will contain > 1 pigeon• Hint #2:Every integer a can be written as a = 2km, where m is an odd number S. A. Seshia 22Suppose A ⊆⊆⊆⊆ {1, 2, …, 2n}Write every number in A as a = 2km, where m is an odd number between 1 and 2n-1How many odd numbers in {1, …, 2n-1}?nSince |A| = n+1, there must be two numbers in A with the same odd part (pigeonhole)with |A| = n+1Say a1and a2have the same odd part m.Then a1= 2im and a2= 2jm, so one must divide the other12S. A. Seshia 23This class will emphasize PROOFSA good proof should be:Easy to understandCorrectS. A. Seshia 243-Level Proofs• Recommendation: Organize your proofs into 3 levels:1. A one-phrase HINT– E.g., “proof by contradiction”, “the pigeonhole principle”, etc.2. A brief one-paragraph PROOF SKETCH3. The complete proofThis will help you with the proof and also to get partial credit for your approach, even if you get some details wrong13S. A. Seshia 25Double Standards?• During lectures, my proofs might only have the first two levels– There’s a lot to cover in each class– I have to keep you awake– I KNOW that my proofs are correct ☺S. A. Seshia 26More on Proofs & Background• Read Sipser, Chapter 014S. A. Seshia 27Introduction toFinite Automata(Finite State Machines)S. A. Seshia 2800,1001110111 111111The machine accepts a string if the process ends in a double circle15S. A. Seshia 2900,100111start state q0transitionsaccept/final states, Fstates, QTerminologyS. A. Seshia 30Q is the set of statesΣ is the alphabetδδδδ : Q ×××× Σ → Q is the transition functionq0∈∈∈∈ Q is the start stateF ⊆⊆⊆⊆ Q is the set of accept statesA finite automaton is a 5-tuple M = (Q, Σ, δδδδ, q0, F)L(M) = the language of machine M= set of all strings machine M accepts16S. A. Seshia 3100,100111q3q0q1q2M = (Q, Σ, δδδδ, q0, F)What are 1. Q 2. F3. Σ4. δδδδS. A. Seshia 32Applications of Finite Automata• String matching• Modeling sequential digital circuits• Embedded controllers in your car• …17S. A. Seshia 33Next Steps• Read Sipser 1.1 in preparation for next