COMPSCI 172 Study Guide - Midterm Guide: Turing Machine, Rage Against The Machine
Document Summary
Cs 172: computability and complexity, spring 2010: a. seshia & o. etesami. Please turn off and put away electronic devices such as cell phones, laptops, etc. There are 4 questions worth a total of 100 points. The questions vary in dif culty, so if you get stuck on any question, it might help to leave it for a while and try another one. Answer each question in the space provided below the question. If you need more space, you can use the reverse side of that page. You can use without proof any result proved in class, in sipser"s book, or on homeworks, but clearly state the result you are using. Do not turn this page until the instructor tells you to do so! Problem 1: [true or false, with justi cation] (30 points) For each of the following four questions, state true or false.
