What Are Computers, Really?

Accepted Session
Short Form
Scheduled: Tuesday, June 23, 2015 from 2:30 – 3:15pm 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 the past ten years.