Saturday, January 05, 2013

What is Computer Science?

Every now and then, a non-technical friend--or stranger at a party--will ask me, "What is computer science?" As your typical antisocial computer scientist, I am often too tired to do justice to this question. From now on, I will carry around QR codes pointing to this post.

Computer science is the study of what machines can do for us. Among computer scientists there are theorists, applied logicians and mathematicians study what is even possible for a machine to compute. There are systems scientists who study how to get the power we want out of our machines. Then there are artificial intelligence researchers who help computers make unsupervised decisions--they are the ones responsible for the robots and the cool demos. Computer science researchers take the risk out of building systems; software engineers build the things we use.

At the core of computer science is a pile of logical foundations. People like to study how hard problems are: whether you can compute solutions in steps ("time") that are a polynomial function of size of the input, an exponential function, or something even worse. People talk about different classes of problems: for instance, P, the class of problems with polynomial-time algorithms, and NP, a class of problems for which polynomial-time algorithms are not known. It is not known whether P and NP are the same, but it would change everything if we discovered they were: all of our banking software is encrypted based on the assumption that P != NP (P not equal to NP). (A couple of years ago there was big news when somebody claimed to have proven P = NP.  Fortunately, it turned out to be a false alarm.) People across subfields talk about what is decidable: what it is possible to develop a terminating computational routine to do. This allows us to guarantee (haha!) that the software powering your space shuttle will not spontaneously freeze from getting stuck in an infinite loop.

Then there are the machines themselves. Incredible things. The invention of the transistor allowed for everything by making high (1) and low (0) signals, called bits, stable enough to build everything else on top. Computer hardware runs on bits combined into instructions and a set of logic gates (for instance: "and," "or," "not") for decoding these instructions. Instructions encode a unit of computation: for instance "add" or "store in memory" along with operands, either as constants or in as locations in memory. Memory just contains more of these bits (just 1's and 0's!). All a computer is doing, really, is reading instructions from code memory and reading to and writing from data memory. There are also details like interacting with a keyboard and a screen. One of the key ideas in systems is abstraction: building higher-level, simpler systems on top of existing ones to simplify reasoning. Programming languages shield the programmer from having to reason about bits and operating systems shield the programmer from reasoning about details like the interaction with the keyboard and in what order application processes should run. On top of all this we have the mobile app that let you read this post. Underneath, it's just bits.

And there is also the sexy artificial intelligence stuff. Back in the day, people thought they might create machine intelligence by modeling how the mind works. Now most of the routines powering robots (and spam filters and everything else) is based on statistical heuristics. Bayesian inference and fancier stuff. People who work on these kinds of things spend a lot of time thinking about how to get more accuracy out of their algorithms (for detecting faces, for predicting whether a message is spam, for planning the route a robot will take) and/or how to make these algorithms run faster. It is pretty amazing that all of the obscure stuff you might have learned in probability theory is the reason that your Facebook friend feed works.

As for me, I focus on programming languages. Programming languages protect people from having to reason about bits, or machine-level code, or sometimes even complex details of execution. Programming languages researchers range from logicians who try to make programs more correct and hackers who try to make people's lives easier. The specifics of this will be the subject of another blog post, as we seem to be reaching the limits of your attention span.

Oh, you were just trying to make polite conversation? Sorry. Maybe you can pass this along to a friend.


Philip Guo said...

nice :) i think all CS researchers need to write one of these posts for themselves ...

Anonymous said...

Yeah, seems like it should be standard. Good explanations by both of you...