CPSC 421/501: Skeletal notes of what will be covered in class.
THIS PLAN IS TENTATIVE AND WILL PROBABLY BE MODIFIED
September 7-26 or so: Acceptance/Halting Problem and other paradoxes.
List paradoxes in handout. Give example of making things precise.
We typically use languages to describe any yes/no 0/1 true/false question,
a subset of strings/words over an alphabet.
* Introduce Sigma, Simga^*, empty string, etc.
* Give examples of how to make "paradoxes" precise, when they lead to
a real paradox, when they don't
* Embark on making some of them precise.
* Make the halting problem precise.
Live/Dead Code:
* Explain why LiveCode (see handout) is acceptable.
* Explain why it is unclear if it is decidable or not.
* Given that LiveCode is not decidable (but acceptable), explain why
DeadCode must be unacceptable.
General Counting
* The set of strings over an alphabet is countable.
* The set of subsets of a countable set is not countable. Generally,
set of subsets of a set, S, cannot be put into 1-1 correspondence
with S. Proof: if f:S->P(S), let T={s s.t. f(s) does not contain s}.
Paradox!
Acceptance (L_yes)/Halting problem
* Remark: It is easy to see there are undecidable/unacceptable languages
via counting. This uses another "paradox".
* Decide versus accept.
* Let A_C = , M is a C program and M accepts (prints "yes" in a
finite number of steps) to w.
* Note A_C can be accepted, via simulation.
* Assume that H is a C program that always halts and decides A_C. Let
D take input , use H to decide if M accepts input and performs
the "opposite." What happens when D is run on ? Paradox!
* Assume L is acceptable but not decidable; then complement(L) is not
acceptable
----------------------------------------------------------------
Starting September 26 or so:
Turing Machines (TM's). Sipser defines them as a 7-tuple. Specifically,
(Q,Sigma,Gamma,delta,q_0,q_accept,q_reject) (and should add L,R, and
blank symbol), with delta : Q x Gamma -> Gamma.
Need to:
* Write some simple programs (e.g., PALINDROME, DIVISBLE_BY_3)
* Show that PALINDROME is linear on a 2-tape machine, but (claim that
and explain why) it is quadratic on a 1-tape machine
* Run any C, Java, etc. program; run any TM
* Explain TM encoding by integers and 5-tuples (for delta)
* Explain there exist universal TM's, universal C/Java/etc. programs
* Explain time and space and give some bounds on our programs
Note: time and space usually defined via k-tape Turing machines, which
are defined like 1-tape machines, except that delta : Q x Gamma^k ->
Q x Gamma^k x {L,R,S}^k
* Here we can define Non-deterministic TM's: delta : Q x Gamma ->
PowerSet( Q x Gamma x {L,R} ). Say that a machine accepts an input
if there is at least one legal accepting "path" or "set of configurations"
This definition appears in Chapter 3, although it could be delayed until
NP-completeness.
Unsolvable Problems:
* Review Acceptance Problem, Halting Problem, Dead Code, Counting argument
in TM context.
---------------------------------------------------------------
Starting Late October or so:
We are basically done with our coverage of Ch 3-5, and we have already
defined TIME and SPACE complexity. Take up Ch 7 and P vs. NP.
* Define P = languages acceptable in time polynomial in length of input.
* Note that there is a class of languages solvable by guessing and verifying
with forming a guess and verification taking polynomial time, yet
there are exponentially many guesses. This includes SAT, 3-SAT,
SUBSETSUM, VERTEX COVER, 3-COLOR, etc. Explain that these problems
are, in a sense, equivalent and are the hardest problem in a class.
* SUBSETSUM and 3SAT look totally different (at first). Yet if we can
solve SUBSETSUM time f(n), we can solve 3SAT in time order (f(n))^2.
* Formally define reduction of one langauge to another; note that this is
a stronger condition that being able to solve one problem with the
solution to another--reduction means you convert an instance of one
problem to an equivalent instance of another, and you cannot run
the solution to another repeatedly.
* Formally define NP.
* Cook-Levin Theorem: SAT and 3SAT are NP-Complete
* Give a few easy NP-Completeness proofs: 4SAT, PARTITION; leave the
harder reductions for the students and homework
--------------------------
Outline of Chapter 1,2,8 coverage:
What is a regular language? (Defined via DFA)
What isn't a regular language? (Use pumping lemma and Myhill-Nerode)
What is a context-free language? (Defined via CFGrammars)
What isn't a context-free language? (Use Pumping Lemma for CFL's)
What is in PSPACE? (Search through configuration spaces to show languages
are in PSPACE.)
More details:
DFA: (Q, Sigma, q_0, delta, F) (F=final or accepting states)
and delta: Q x Sigma -> Q .
Pumping Lemma for Regular Languages: If L is regular then there is a q
such that if w is in L and |w| > q then w=xyz with x y^n z in
L for all n, y is not empty, and |xy| < q.
Myhill Nerode: For any language L over Sigma and word w over Sigma let
AcceptedContinuations(L,w) = { x such that wx is in L }.
Let ACSets(L) be the number of distinct sets AccCon(L,w) ranging
over all w. Then if ACSets(L) is infinite, L is not recognized by
any DFA, and if ACSets(L) is finite then L is recognized by a DFA
of ACSets(L) states, and that is the smallest number of states
possible.
CFG: Terminals, non-terminals, production rules.
Pumping Lemma for CF Languages: If L is CF then there is a q
such that if w is in L and |w| > q then w=xyzuv with
x y^n z u^n v in L for all n, yu is not empty.
PSPACE: Polynomial space. Many natural problems have a configuration
space of size < 2^(poly(n)) with a natural way to "step" through
all configurations in polynomial(n) space, so can apply a divide
and conquer algorithm to see if the initial configuration is
connected to the goal configuration.