What Are Computers, Really?

Short Form
Scheduled: Tuesday, June 24, 2014 from 3:45 – 4:30pm in B204


We'll take a whirlwind tour of the theory behind what computers do. We'll start with counting on our fingers and end with an explanation of why there are some problems where the laws of physics say "no, a computer can never do this". No mathematical background necessary.


Starting with the notion of size of sets and an informal definition of computation, we’ll move on quickly to describe the difference between classical and constructive mathematics and why this is such a huge philosophic point of contention. Then, we’ll move on to describe the kinds of things that make sense in classical mathematics that, by the laws of physics itself, can’t be done by a computer. We’ll tie this into real life examples like the imprecision of floating point arithmetic and the reason why there’s no program that can tell you if you have infinite loops and no type system that can mark all correct programs as well-typed.

Speaking experience

I've taught courses in physics, math, and programming for almost ten years.