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.
- 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.
The Antikythera mechanism: The clockwork computer, Economist, Sep 19th 2002.
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.