FRS 104
What Do Your DNA and Your iPod Have in Common?

---

February 4

Computers vs. robots. Turing machines. Universality. Church-Turing thesis

• Readings  
  • The Algorithm: Idiom of Modern Science (intro + the universal computer; pdf)
  • Moore's original paper
  • MIPS progression: table
  • The story of the ENIAC
  • Babbage's computing engine
  • Turing's life
  • ASCII code, pixels
  • The universal Turing machine
  • Turing's original paper
  • Alonzo Church

---

February 11

The digital nature of information. Duality: signifier vs. signified. Semiotics. Self-reference. Self-replication. Impossibility results: halting problem; squaring the circle; compass and rule construction; Galois theory

• Readings  
  • The Algorithm: Idiom of Modern Science: two sides of the same coin + say it ain't true
  • Basics of semiotics here, here, and here
  • Who's on first video and transcript
  • Magritte's ceci n'est pas une pipe
  • Linguistic self-reference
  • Self-referential "jokes"
  • Compass and ruler constructions: here and here.
  • Halting problem: here and here.
  • Self-reproducing machine: self-copier

---

February 18, 25

Genetics. Self-replication. DNA computing. Computer viruses

• Readings  
  • Genetics primer, and processes.
  • Computer viruses and worms
  • Human viruses here, here, and here
  • DNA computing

• Animations for DNA replication, DNA transcription, RNA translation and viruses

---

March 3, 10

The web. Small world phenomenon. Data mining

• Readings  
  • Vannevar bush's original article in html and pdf
  • History of the web in html and pdf
  • Wikipedia entry for the web
  • First announcement of WWW
  • Network models
  • The small-world phenomenon
  • Social networks here, here, here, here, here, and here
  • Schelling segregation model applet
  • Data mining

---

March 24

Tractability. P vs. NP. Computational complexity

• Readings  
  • The Algorithm: Idiom of Modern Science (the modern era)
  • Gödel's letter
  • Clay's challenge
  • Papadimitriou's essay
  • Kleinberg and Papadimitriou's essay

---

March 31, April 7

Cryptography. Zero-Knowledge. PCP

• Readings  
  • The Algorithm: Idiom of Modern Science: p=np and the computational art of persuasion
  • Historical ciphers
  • Overview of crypto
  • Historical ciphers
  • RSA algorithm
  • Wiki entry: steganography
  • Information hiding survey
  • Steganography overview
  • Introduction to zero-knowledge
  • Proof at a roll of the dice

---

April 14

Algorithms. Artificial intelligence. Games. Economics. Learning.

• Readings  
  • Google's PageRank
  • What is AI?
  • Computer and narratives
  • Consciousness here and here.
  • Turing on machine intelligence
  • Kirkpatrick's take on the Turing test
  • Searle's "Chinese room" refutation of strong AI
  • Drew McDermott on Deep Blue
  • Virtual worlds

---

April 21

Sociology of computing

• Readings  
  • Wikipedia here
  • Technology of cooperation
  • Open source
  • Why your broadband sucks

---

May 5

Student presentations