Computers and Computation

Topic: Computers and Computation

Instructor: Prof. Jason Hartline
Monday: history, evolution, genetics, societies, the brain, digital computers.
Wednesday: theory of computation, universality, duality, Turing machines, halting problem.

Discussion Questions:

  • What is the difference between a universal computer and a non-universal computer? Give examples of each. Are you a universal computer? Is your smartphone a universal computer? Is your wristwatch a universal computer?
  • If you are a computer and your smartphone is a universal computer, how come your smartphone cannot simulate you?
  • Are there limits to what computer can compute?
  • What is the relationship between computer programs, computer simulations, and universal computation?
  • What is duality and what does it mean to run a computer program with another computer program as its input?
  • What is a computer? (Is a wristwatch a computer? Is a school of fish a computer? Is your smart (or dumb) phone a computer? Are you a computer?)
  • What is computation? (Is keeping time a computation? Is avoiding being eaten by sharks a computation? Is looking up a number in your address book a computation? Is reading and understanding this question a computation?)
  • What is not computation? What is not a computer?
  • What are other academic fields where computation may play a central role?
  • What is ‘computational thinking’?

Readings and Media:


Could your iPod be holding the greatest mystery in modern science, Bernard ChazelleMath Horizons, April 2006.
Scooping the Loop Snooper: a proof that the halting problem is undecidable, Geoffrey K. PullumMathematics Magazine, October 2000.



What is Computation?, Ian Horswill, XRDS, March 2012.
Computational Thinking, Jeannette Wing, CACM, March 2006.
skim: The Many Facets of Natural Computing, Kari and Rozenberg, CACM, October 2008.
optional: Why Johnny Can’t Steam: How video copyright went insane, James Grimmelmann, Ars Technica, October 2012.

XKCD: A Bunch of Rocks