CS60: Theory of Computation, Spring 1999

This week's schedule.

Hand-outs

• Syllabus
• Ray Ontko's solutions to selected problems in Lewis/Papadimitriou
  • Chapter 1.1
  • Chapter 1.2
  • Chapter 1.3
  • Chapter 1.4
  • Chapter 1.5
  • Chapter 1.6
  • Chapter 1.7
  • Chapter 1.8
  • Chapter 2.1
  • Chapter 3.4
• Why Publish Homework Solutions?
• Examinations
  • Examination 1
• Programming Project Assignments
  • Programming Project 1
  • Programming Project 2

Links

• Converting a DFA to a Regular Expression

Other Texts

• Kelly, Dean, Automata and Formal Languages: An Introduction (Prentice-Hall, 1995).

Halting Problem (links contributed by Chris Hardie)

• The Halting Problem, by David Matuszek. Straightforward slides; useful diagram at the bottom of the second slide; sections on implications for programming & AI.
• G12FCO -- Formal Computation, Lecture 17, by A. N. Walker. Halting info at bottom, ugly background.
• The Halting Problem Recap by Eric Torng. Series of slides that explain halting by using actual code.
• Comp 210: Lecture 40, compiled by Matthias Felleisen and Joe Warren. Examples in Scheme.
• ECECS 543 Lecture Notes 4-1-97, by Yizong Cheng. Not that useful, what the heck.

Open Source

• Eric S. Raymond Speaks at Earlham
• The Cathedral and the Bazaar, by Eric S. Raymond
• Homesteading the Noosphere, by Eric S. Raymond
• Setting Up Shop: The Business of Open Source Software, by Frank Hecker

Copyright © 1999, Ray Ontko (rayo@ontko.com).
If you're curious about why I copyright, see Peter Suber's Why Copyright Web Documents?.