I Pledge My Honor That I Will Never Forget You, CS 181
Formal Languages and Automata Theory is over, friends! This was my favorite and most difficult class this quarter. My only regret is missing the first two lectures while I was in Russia. Professor Sahai was awesome. I think he only teaches this class Winter quarter because it's the "advanced offering". (I'm not really sure I got my causality correct here. It could be that Winter quarter is advanced because it's the quarter Professor Sahai teaches is.)
Class description from Professor's syllabus:
This course deals with some of the most fundamental philosophical questions surrounding computers. Is there such a thing as a "generic" computer? How powerful are computers? Are there fundamental limitations on what computers can do? It turns out that these questions are also very important philosophical questions about mathematics. For instance, are there theorems that are true but cannot be proven? What is the nature of infinity? In this cause, we will embark on a systematic mathematical study of computation and try to get some answers to these and other questions.
Ahh. I get goosebumps. We used the Sipser textbook Theory of Computation. It is, hands down, the best CS book I have ever laid my eyes on. I usually don't even bother buying CS textbooks. This one was like bedtime reading. If you are interested in computers and their limitations you could probably just read the book and teach yourself. It's that awesome.
Over the course of 10 weeks we were assigned 6 homeworks and I am pretty sure I cried while stuck on a problem from each one of those. I don't know why it bothers me so much.
I just skated over to campus to turn in my take-home final exam. That, also, did not get done without tears. I got stuck on 1b. (1b!!) It was worth 10 points out of 175 and I could not get it. I still am not sure my solution is correct, but after spending literally 4.5 hours straight on a 10 point problem I felt pretty hopeless, like I didn't learn anything. Mind you, I was only supposed to spend 10 hours on the exam. By the time I finished 1b (25/175), I was already 6 hours into it. (I took longer than 10 hours to do the whole thing. I'm sorry, Professor Sahai.)
I typed one problem because my hand was tired from re-writing the solutions from my drafts. Just for the sake of having a picture I'm going to put up my solution.
The last lecture, Wednesday March 10th, was optional. Professor talked about a topic of his choice and it happened to be Gödel's Incompleteness Theorem. We proved it using Turing Machines. It was so simple, yet the implications of the theory are mind-blowing.
My favorite quotes from this class:
"You're going to love this class" - JT after attending lecture for me while I was in Penza.
"What's a fudge factor" - An (asian) student from the class
"Let's call this machine SHT." - Professor
"We're going to be battling infinity here." - Professor
Professor enacting a conversation:
A: "You can only be in this club if you cannot be in this club."
B: "Can you tell me who is in this club?"
A: "Of course, not! What does that even mean?"
And last, but most certainly not least,
"I will never give up on soundness." - Professor Sahai
I'm a big fan of this blog entry. So succinct. Bravo.
ReplyDeleteJT: "In literature that is called a catch-22."
ReplyDeleteO: "Everyone in literature is retarded."
I heard perfectly seriously phrases, such as "You're going to push, push, pop" and "for this you would use a PDA."
I'm sad that you won't be so excited to tell me about the things you are learning; all the mini-lessons about languages, epsilon transitions, accepting states, DFAs, NFAs, PDAs, pushing and popping stacks, pumping lemmas, context-free languages, turing machines, tapes, and the halting problem.
It really seemed like way more than six assignments over the course of the quarter; perhaps your counter began at -2?