Class 1: Course intro, alphabet/language intro


Reading
Sections 1.1, 1.2, 1.3 of Theory of Computing, A Gentle Introduction.

Homework
Printout the homework and answer the questions on that paper.

Course admin
Choose section leader, pass out course policy and departmental honor policy.
Note: Class lecture notes and homework will, generally, be available after class, not before!

What is "theory of computing"?

Languages, alphabets, strings

Further importance of languages
Most fundamental computing problems can be phrased as the following kind of problem: Given a description of a language L, decide whether a given string w is in the language L. These problems are decision problems, which means they have yes or no answers. Often the decision problem version of a question is a bit easier than the original, but they're related.

For example, suppose your original problem is "Compute (3 + (2*x)) + x*4 given x". As a decision problem this , might become "Given a string x:y, where x and y are strings of digits, decide if x:y is in the language of strings for which the numbers encoded by x and y satisfy y = (3 + (2*x)) + x*4".

By restricting our attention to decision problems like this, our computational models can become much simpler, so at some points we'll just talk about decision problems. True, the decision problem is often easier that the original problem, but this is OK. What we'll show at the end of the semester, is that there's a straightforward decision problem of the type described above that can't be solved by any computer or computer program. No matter how clever you are writing your program or building your machine, there will always be some input strings that foil your program. Either it will give wrong answers, or it will run forever, never giving any answer at all!


Christopher W Brown
Last modified: Wed Aug 19 11:00:04 EDT 2009