CS 381 - Introduction to Theory of Computing, Summer 2004

Links of interest

Here are some links to sites you may find interesting:

  • A Turing machine built from Lego bricks can be found here. Do check it out!
  • An informative and detailed site about quines (self-printing programs).
  • Another good quine site.
  • A detailed Wikipedia article on Brainf***, one of the esoteric languages mentioned in class.
  • An article about the Church-Turing thesis from the Stanford Encyclopedia of Philosophy
  • For the curious about the early (and not-so-early) history of computing and computers, the virtual museum of computing can be a good starting place. There seem to be quite a few broken links, but much interesting information can be found there nevertheless.
  • On quantum computing: Wikipedia article and a fairly nontechnical introduction (see the Wikipedia article for many more links).

    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).

  • H. Garey, D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness
  • J.E. Hopcroft, J.D. Ullman, Introduction to Automata Theory, Languages, and Computation
  • H. Lewis, C. Papadimitriou, Elements of the Theory of Computation
  • M. Sipser, Introduction to the Theory of Computation

    A note about proofs

    (Courtesy of and 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".