This course is arguably the most interesting in the Computer Science core
curriculum. During this Semester, you will learn the accurate meanings of
a number of terms that you have probably heard. In some cases, you will
have to unlearn what you previously believed! For example, you will learn
the following concepts:
Automaton. The plural of "automaton" is "automata." [Greek]
Language. (You may have thought you knew this one!)
Grammar. (You probably thought you knew this one, too!)
Universal Turing Machine. A machine that can do anything that any
machine in this or any other universe could possibly do. But, rather
NP-complete. Almost everyone in computer science has heard this
term, but few can give a precise definition.
There are problems that are undecidable. There are
propositions that are true but for which there is no proof. I don't mean
no one has found a proof yet, I mean that no proof can exist at all!
There are problems, such as the halting problem, which cannot be solved
by any algorithm. No future genius with a finite intellect will ever
find one, not in this (or any other) universe, ever, and I will prove
that to you.
Computable and Uncomputable Functions.
There are functions which cannot be computed by
any machine that could ever be built.
P = NP? The most famous open question in all of computer
science. What does this mean? What does it mean in practical terms?
Detailed description of the CYK algorithm.
tests from prior semesters are available.