Interesting and informative sites
- Babbage's Analytical Engine - extensive info about this early computing device, including a
Java emulator of a (severely overclocked! :)) engine, as well as texts by and about Charles Babbage and Ada Lovelace, the first programmers.
- The Turing Archive - lots of info about Alan Turing and his work, as well as other history of computing articles.
- Lego Turing Machine - yup, a TM built out of
Lego bricks. Be glad I didn't give you such a project as a take-home final!
- BrainF*** - everyone's favorite programming language, which is not too far in spirit from a Turing
Machine.
- The Church-Turing thesis - article from the Stanford Encyclopedia of Philosophy explaining what
the thesis is and isn't trying to say.
- The Turing Award winners - a complete list.
- Gödel, Escher, Bach - a fun, accessible book dealing with the Incompleteness Theorem and
the Church-Turing thesis, among other things.
- Extensive FAQ on all aspects of Cellular Automata.
- The Wikipedia articles on cellular automata and the Game of Life
in particular.
- Another gentle introduction to the Game of Life.
- A site devoted to the Game of Life, with a fast applet and lots of patterns.
(source of the patterns demonstrated in class)
- Life32, a Game of Life program for Windows - the program used for the in-class demo.
- Website for the book "Computational Beauty of Nature", which talks about fractals,
L-systems, cellular automata, and other kinds of naturally occurring computation.
- Algorithmic botany - researchers using L-systems to produce simulations of plant life.
- Wikipedia article on quines, including numerous examples.
- Good, accessible detailed explanation of what quines are and how they work.
Books on reserve
In addition to the course text, you may find the following books useful. They are available on reserve in the
Engineering Library, Carpenter Hall. (The course textbook itself is also available there).
- J.E. Hopcroft, J.D. Ullman, Introduction to Automata Theory, Languages, and Computation
- M. Sipser, Introduction to the Theory of Computation
On writing good proofs
Here are my own guidelines for writing clear and easy-to-understand formal proofs in 381, and beyond.
And here are some further words of advice, adapted from Dexter Kozen.
The ability to deal with abstraction is the most important intellectual skill any computer scientist can have.
It requires the ability to think clearly, to formulate precise definitions, and to reason logically in
terms of those definitions. Do not worry if you have had only limited experience with this; you will
gain plenty of experience in this course. One of our chief purposes is to cultivate this skill.
Accordingly, we will hold you to a high standard of rigor in the presentation of your homework solutions.
When justifying an answer, you do not need to be overly verbose; just make sure your argument is logically
sound from start to finish and that you include enough information so that we can follow all the steps in
your reasoning. For instance, including step-by-step justifications such as "by the definition of ..." is
a very good idea. Such explanations are brief, but still demonstrate that your solution is based on a
solid understanding.
You should take as much care composing your solutions as you would composing an essay for an English
course. A common mistake is to write down a sequence of statements without making clear the chain of
thought connecting them. An isolated statement can be an assumption, a conclusion, a definition, or
a proof goal; it is often difficult to determine which was meant. Even if familiarity with the solution
enables us to infer your intended meaning, you will still lose points if your presentation is not
sufficiently clear.
Here are some tips to avoid these problems:
- Write in complete English sentences.
- Use abbreviations and symbols sparingly, and avoid mixing them with English text.
- Use arrows only for propositional implication.
- Define all nonstandard notation.
- Exploit the power of definition; ascribing a name to a concept or
labeling an equation makes it easy to refer to. However, do not make spurious definitions.
- Reread your solutions while asking yourself: Could a fellow student make sense of it?
Is the argument presented in the most concise and efficient way?
- Looking at your solution, talk through your proof - out loud - in a formal manner, as though you were
presenting it to an audience. Do you find yourself getting lost or muddled at a particular point? If so, chances
are something is not quite clear in your proof right there.
Students often ask whether "show" means the same thing as "prove". The answer is yes.
So do "demonstrate", "argue", and half a dozen other synonyms. Unless otherwise noted,
all these expressions mean "prove formally".