#### 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:

**Wednesday**

- 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?

**Friday**

- 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:

**Wednesday:**

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.

**Friday:**

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.