CSC280/480, Spring 2018: Computer Models and Limitations
Instructor:
Prof. Lane A. Hemaspaandra.
Grad TA:
Andrew ReadMcFarland.
Workshop (though called Recitations in CDCS) Leaders:
Shir Maimon
and
Brandon Willet.
UG TAs (they also are the Tutorial Leaders):
Jackson Abascal,
Michaela Houk,
Joel Kottas,
Andrew Peck, and
Colin Pronovost.
Tutorial Times:
Here.
The Course Catalog Description:
This course studies
fundamental computer models and their computational
limitations. Finitestate machines and pumping lemmas, the
contextfree languages, Turing machines, decidable and
Turingrecognizable languages, undecidability.
Textbook:
Introduction to the Theory of Computation, Michael Sipser,
third edition, 2013.
Be careful
not to accidentally get the first or second edition.
Note that we will be using
the (standard, USAversion)
third edition, not the "international" (third) edition;
in the international edition apparently
some problem numbering differs, so if you use the international
third edition (which you might get if you
buy a used one, so be careful), you
may
do the wrong problems
(and so may end up with 20percent grades on some of the
tutorials as you will not have attempted the
right problems).
(And no, I don't work for the publisher;
all my books are published by Springer.)
The ISBN of the US edition (the international edition
has slightly different ISBNs) is listed by the publisher as:
ISBN10: 113318779X and ISBN13: 9781133187790.
On the other hand,
the right book is also on reserve in the library,
though you will be using
it very, very often (you may find it
comforting to sleep with it under your pillow!).
Prerequisites (very important): CSC173 and MTH 150.
Course Information Document/Syllabus:
course information document/syllabus (most current version, V. 2.2.5,
last revised 2018/4/10/1141pm).
Slides:
Here (version
of 2018/1/14/532pm plus some updates, the most recent
done 2018/4/03/1135pm)
are the slides up to and including Chapter 5.
Here is the slide set (consisting
of slides 1 and 61 through 85 of the slide set for CSC 286/486)
that we'll use for our
introduction to P and NP.
Reading Assignments, starting with the date/time the reading is DUE:
 Due 2018/1/22/1201am:
Read the Course Information Document/Syllabus.

Due 2018/1/24/1201am:
Read SIP (i.e., our Sipser textbook)
from page xi through the middle of page xiii (that is,
read, in the 3rd edition, within the "Preface to the First Edition,"
the sections called "To the Student" and "To the Educator"),
and read SIP Chapter 0,
and read SIP Chapter 1.1.

Due 2018/1/26/1159pm: Read SIP Chapter 1.2. (I mention in passing
that many of the assignedafteraWednesdayclassand also many
assignedafteraMondayclassreadings may be helpful on exercise
sets... often on the set that is due the Monday or Tuesday right
after the
week in which the readings are posted to our web site.

Due 2018/2/2/1159PM: Read SIP Chapter 1.4. This reading covers for
example what we went over in class (the part that came after
finishing the Problems handout) on 1/31.

Due 2018/2/6/1159PM (note: suggested time to START this
reading is right after the 2/5 class's lecture, since this material,
which is SIP's treatment of what Read will lecture about on 2/5, is
important on
two of the problems on the 2/7 sheet of inclass problems):
Read SIP Chapter 1.3.
 Due: [the two parts each specify their due date/time]. Note: The
information/topics/material/techniques/directions/flavor/etc. of
Part 1 of this reading is in scope as to questions related to that
appearing on Midterm I as to Chapter 2; in contrast, the material in
Part 2 of this reading will not be asked about on Midterm I.
PART 1 (due 2018/2/20/1159PM):
Read SIP from the start of Chapter 2 through
the end of Section 2.3, except not the proofidea
and proof of Theorem 2.34
and also, if you wish, you can
skip until Part 2's later due date the readings
mentioned in Part 2.
PART 2 (due 2018/23/1159PM):
The subsection of 2.1 titled Ambiguity; from
right AFTER the statement of Theorem 2.9 through
the end of Section 2.1;
the subsection of 2.2 titled Equivalence with ContextFree Grammars;
the proof on our slides of the pumping lemma for CFLs (that is, I
suggest you do not read the book's different proof but that you do
read the proof sketched on our slides).

Due 2018/3/6/1159PM (and assigned on 2018/3/1/916PM):
Read
SIP from the start of Chapter 3 through the end of Section 3.1.

Due 2018/3/18/1150PM: Read SIP, Section 3.2.
Also (and the Terminology
subpart of this basically, except for a brief comment, wasn't
at all covered in class, but is interesting and may help you with
later SIP readings and in putting things in context as to
the notion of an algorithm)
read SIP Section 3.3.

Due 2018/3/20/1159PM: Read SIP, from the start of Chapter 4 to the end
of Section 4.1.

Due 2018/3/27/1159PM: Read SIP, Section 4.2.

Due 2018/3/30/1159PM (two parts; you will want to start this reading
only after, but right after, the 3/28 class, that same
evening, esp. as regards item (b) since that is something you will
be putting up on the board on 4/2):
(a) Read SIP, From the start of page 215 up to 10 lines from
the end of page 220.
(b) Read the document 180402exampleproblemsandtemplateandexample.pdf
that can be found below under other important links.
(Reminder: And with your
WSgroupmates, do at the least the problem there that your
group is assigned (and will put up on the board at the start of
the 4/2 class)... and
ideally, work on all of those nice problems.)

Due 2018/4/5/1159PM (note: the due date doesn't really
apply to (b) as that is optional reading):
(a)
This is very important: Unless you are
thoroughly, utterly, totally comfortable with and
great at proving things undecidable, reread very carefully
from the start of Section 5.1 to 10 lines from the end of page 220;
again,
it is extremely important that you understand how to prove
things undecidable via our template/contradiction method.
(b) [optional reading] Midterm 2 will not test you on
this reading... but if you do want to do the Sipser reading
that roughly corresponds with today's (4/4's) lecture,
fyi, that is SIP Section 5.3. However, the part (a) of this
reading assignment is vastly, vastly more important to you
at this point, as to where to best put your time (unless of course
you already are a wizard of proving undecidability via the
template/contradiction method and have no need to do the (a)part
reading).

Due 2017/4/10/1159PM (important
note: the suggested time to start/do this reading
is *right after our 4/9 class*):
Read in SIP from three lines from the end of page
284 to the end of the proof of Theorem 7.14, and from the start of
Section 7.3 to five lines from the end of page 295. WARNING: That
second batch of reading gives a quite lovely but
notstandardlyusedastheprimarydefinition definition of NP, and
then as Corollary 7.22 proves that it gives the same class as the
standard definition (which is the definition covered in the 4/9 class).
(More typical, and what we have done in this course
via the slides, is to define NP the standard way, namely as
nondeterministic polynomial time; however, the same class of
languages is indeed captured by the notion that Sipser uses as
the primary definition, and in fact that
appears on slide 7 of our P/NP slides.)
 Due 2017/4/13/1159PM
(suggested time to start this reading: the evening of 4/11): (As always, but it is more important for this
material than for most, please review the slides we covered this week,
namely, the separate P/NP slide set on our main web site, up through
and one beyond the final one of the slides we covered in class, namely,
read through and including slide 21 of that 26slide set!) Read in
SIP from 4 lines from the end of page 295 through the end of the proof
of Theorem 7.36. (Note that, assuming we take it as settled that 3SAT
is NPcomplete, as it indeed is, Theorem 7.32 establishes that CLIQUE
is NPhard, and since CLIQUE is also in NP, we have that CLIQUE is
NPcomplete.) To get a sense of the nature of some other NPcomplete
problems, skim Section 7.5although I won't test you on this
reading, you should at least read the definitions of the four
additional NPcomplete problems discussed in this section (and if you
really are a theory fan, you might want to skim or even read the
proofs of their NPcompleteness).
Exercise Sets, starting with the set number and then
at which tutorial session you will
hand in parts A and B of the given set (all exercise and
problem numbers are from SIP unless otherwise stated):
 Exercise Set 1, 1/221/23 (which means that "parts A and B" must as usual be handed in
at the start of *your* assigned 1/22 and 1/23 tutorial; except Set 1 is a
very special case at there ARE no parts A and B to Set 1 as there are no
questions on Set 1, and so your grade will be 100 if you are there on time
(see the syllabus for how that is defined) and 0 if you are not; if you
don't have an assigned tutorial and thus don't show up you'll still get a
0, so do be at the 1/17 class to get assigned to a tutorial):
This meeting
will be to meet your tutorial leader; and to chat with that leader about
your background (you MUST have already passed CSC 173 and MTH 150 or the
MTH170sequence150substitutemodule); and to with luck get from your
tutorial leader advice on how to do well in this course; and perhaps to
chat with the leader about what the course is about.
 Exercise Set 2, 1/291/30 (which means
that "parts A and B" must as usual be
handed in at the start of *your* assigned 1/29 and 1/30 tutorial; the numbering of this on your handins
for the SIP ones is pretty clear, as per the syllabus, but as I on the parts A and B added, as I sometimes will,
and extra problem, probably the best thing to do is hand in the problems in the right order, and for the added problem,
just start you answer with "Problem: similarly to ....", that is, write the problem there on your handin so it is clear what you are solving):
Part A: Exercises 1.4a; 1.5c; 1.6ab; 1.7ce;
similarly to example 1.38, give a formal description as a 5tuple of the NFA in Example 1.68a.
Part B: Exercises 1.4e, 1.5d, 1.6cd, 1.7b;
similarly to example 1.38, give a formal description as a 5tuple of the NFA in Exercise 1.16a.
Part C: [Reminder: Part C problems are often hard, or may use tools
that you have not seen, so don't be upset if you can't solve some of
them.]
This is actually an atypical Part C. This week's Part C (and
it has a wildly hard bit of what one might
unofficially consider a "Part D" at its end!) is a mix of easy
and hard problems; you can find it as the 1/29+1/31 problem
document below in
the Other Important Links section. They are a Part C so you do not have to turn them
in. HOWEVER, each group should before the start of the 1/29 class
(do their best to) solve and put
onto paper (computertypesetting is fine on this, or you can
do it by hand) in a size and format such that you can
when called on can put that piece of paper
under the room's document camera (as you saw on
Day 1, it basically projects from paper to the screens, and
that makes for instant changeovers between groups) and project it (so
perhaps use landscape mode and quite large fonts... judge for
yourself what will be best readable, or experiment
in the room... my guess is that for example 12pt would be
way too small when projected)
its solutions to the two problems assigned to it from
the document below that contains the exercises for the week of
2018/1/29.
So at your 1/24 and 1/25 WSs, you'll need to arrange for
all of you, or far more likely some subteam of your group, to be on
point on solving each of the two assigned to your group
and bringing in those solutions to the 1/29 class.
(And
Wednesday 1/31, bring in again those solutions, if any, that we did not
have time to go over
on
Monday). So perhaps
1/3 of your group might do the first of your two problems,
and 2/3 of
your group might do the second of your two problems (less easy
problems). One problem has TWO groups on point, and they (or subteams
from them) certainly may work on the problem together (but not
electronically, of course; just in person as per the course rules);
should create just one joint solution, please, on paper, that you will
show via the document cam as you present it.
So 1/29 and 1/31 will be spent having representatives of
the groups present their groups' solutions, via the document camera
in the room.
By the way, in the
unlikely even that
at your 1/241/25 WS you have time left over after doing Part A well,
then it is legal for your WS as a group to tackle your two problems as a group.
Also, of course each of you may look at or as a challenge work on the
problems assigned to OTHER groupsalthough the group each is assigned to
will be the one to put it up on the document
camera and project it and present it.
 Exercise Set 3, 2/52/6 (which means
that "parts A and B" must as usual be
handed in at the start of *your* assigned 2/5 or 2/6 tutorial;
you'll as be working in groups on Part A in your 1/31 or 2/1 WSs)
This exercise set is
available here
(updated version of 1/31/1051am), as
a pdf.
(Note added 1/31: Also, do be aware that each group has
a problemin one hard case shared by twoto come up with
an answer with before, and to present via projecting
your answer via the doc cam at, the 2/7 class.
You can find your problem in the 2/7 problems sheet that
is under Other Important Links below.)
 Exercise Set 4, 2/122/13 (which means
that "parts A and B" must as usual be
handed in at the start of *your* assigned 2/12 or 2/13 tutorial;
you'll as be working in groups on Part A in your 2/7 or 2/8 WSs)
Part A:
Exercises 1.19a, 1.21a, 1.28a, and 1.29ac (don't do
them by looking at the answers in SIP), and Problem 1.71b.
Part B:
Exercises 1.19b, 1.21b, and 1.28b; and this:
Prove that (the spaces I've put are not part of the language but
are just to make it easier to read for you; oh... and I'm
using pseudolatexish notation) {0^m 1^n 0^{m+n}  m \geq 1
and n \geq 1} is not regular (note: 00010000 for example is in that set, but
none of 010, 11000000, 0110 or (keep the \geq 1's in mind!)
the empty string are in that set.)
Part C: No part C, but if you'd like something challenging,
try to do the final problem on the 2/7 Problems sheet **without looking
at the hint I gave for that on that sheet**.
 Exercise Set 5, 2/192/20 (which means
that "parts A and B" must as usual be
handed in at the start of *your* assigned 2/19 or 2/20 tutorial;
you'll as be working in groups on Part A in your 2/14 or 2/15 WSs)
Those tutorials and WSs will mostly be a time for you to
with your tutorial/WS leader take stock, and work on anything you
are having problems on. So I've made this set somewhat light
(well, except for the final Part A problem), especially
regarding the Part B.
Part A:
Problems 1.41, 1.46ab, and 1.53, and, from Exercise Set 3, the
one problem in its Part C.
Part B:
Problems 1.42 (note the star on the Sigmathat is
why this is not the same question as 1.41), 1.46c, and 1.49ab.
Part C: None, but if you want a challenge and you are interested in
the comment I made in class on 1/31 that there exist nonregular sets
that have the pumping property (the "pumping" behavior spoken of in
the pumping lemma), I suggest you to create such a set (let us say
over a threeletter alphabet). After you do that, you might then want
to look at Problem 1.54 of SIP, which presents such a language.
 Exercise Set 6, 2/262/27 (which means
that "parts A and B" must as usual be
handed in at the start of *your* assigned 2/26 or 2/27 tutorial;
you'll be working in groups on Part A in your 2/21 or 2/22 WSs)
If you have time left at your WS after doing the Part A, I suggest
you
work on your group's problem(s)
from the Problem Sheet for the 2/26 class, and if you still have time,
work on the other problems from that sheet, or
work extra examples
on anything that you are having troubles on (e.g., the pumping lemmas,
or fractions of languages, or etc.).
Part A:
Problem 2.4ad;
give a CFG for {0^i1^j0^k1^n  each of i, j, k, and n belong
to {1,2,3,...} and i+j = k+n} (note: this is similar to
but not identical to problem 4 from the 2/26
problem sheet);
Problem 2.30b.
Part B:
Problems 2.4e and 2.9 (just the giving the grammar part, not the ambiguity questions);
give a CFG for {0^i1^j0^k1^n  each of i, j, k, and n belong
to {1,2,3,...} and 2(i+j) = k+n};
Problem 2.30a.
Part C: None (but I do suggest
you work on Problem 1 from the for2/26 problems sheet).
 [NOTE: There will NOT be an
exercise set due 3/53/6, as Midterm I is 3/5, in Lower Strong.]
 Exercise Set 7, 3/193/20 (which means
that "Parts A and B"though this week part A is emptymust
as usual be
handed in at the start of *your* assigned 3/19 or 3/20 tutorial;
you'll NOT have a Part A as there will be no workshops
on 3/73/8 due to it being Midterm I week; note
that you'll thus have to do Part C, which is
groupbased, in pairs of WS groups, WITHOUT having
a WS at which to do it, so you'll want to arrange
for your groups to meet)
Part A: none as there is no WS associated with this exercise set.
Part B: Exercises/Problem 3.1b, 3.2a, 3.5, 3.6.
Part C: Here are three problems, one a starred problem from SIP
and two others hard problems from the slides. Each of the
problems is assigned to TWO WS groups; please work jointly
to ensure that your pair of groups has a joint answer written
up and ready to project on the doc cam AT THE
3/21 CLASS SESSION, which will be devoted to
seeing the three solutions as presented by the groups.
I encourage each of you, and your WSmates, to work on not just
your problem but the other problems too; these are fun, fun
problems that each take an insightin some cases, a
rather thrilling, not so obvious one.
Problem C.1 (to be done by the two late Thursday WSs
as a joint team): SIP 3.19.
Problem C.2 (to be done by the late Wednesday WS
and the early Thursday WS as a joint team): The
problem called "A Fun, Hard Challenge" on
the Chapter 3, Part 2 slides, ideally also including
solving the "Superchallenge" on that same slide.
Problem C.3 (to be done by the two early Wednesday WSs
as a joint team): The
problem called "Another (Your Lucky Day!) Fun, Hard Challenge" on
the Chapter 3, Part 2 slides, ideally including both
finding a relatively clear and nondisturbing solution for the first
part (the "no three") case, and then finding a different
but also relatively clear (though slightly though
subtly disturbing;
side comment: do you see what is disturbing about it?)
solution for the second part (the "no two" case). (No, don't
ask for a definition of "disturbing," but we'll cover what
is under the hood here in class that day, if there is
time, after your present
your solutions, unless your solutions already covered it.
 Exercise Set 8, 3/263/27 (which means
that "parts A and B" must as usual be
handed in at the start of *your* assigned 3/26 or 3/27 tutorial;
you'll be working in groups on Part A in your 3/21 or 3/22 WSs)
Part A:
Exercises/Problems 4.1ae; 4.2; 4.5; 4.10. (You do NOT have
to write up and hand in the following problems, but if you
happen to have time at your WS after doing the above
problems and addressing any questions, then please
do Problem 4.20.)
Part B:
Exercises/Problems 4.1bcdf; 4.3.
Part C: None (but Problem 4.20, which is sort of embedded as a
possible one to do at your WS, is a pretty problem; far more lovely
still, though we likely won't cover this in this coursethough
it often is given as a homework problem in 286/486 and in a week
or two you actually will know enough to solve this as long as you
are struck by the right and by the way notsoobvious insight as to how
to approach itis that if you
remove the "co" from this problem, it becomes impossible to solve as
the claim switches to not even being truethus revealing a striking
behavioral asymmetry between the Turingrecognizable sets and the
coTuringrecognizable sets).
 Exercise Set 9, 4/14/2 (which means
that "parts A and B" must as usual be
handed in at the start of *your* assigned 4/1 or 4/2 tutorial;
you'll be working in groups on Part A in your 3/28 or 3/29 WSs)
IMPORTANT NOTE: Regarding your tutorial on 4/1 or 4/2, anyone who
doesn't stay at least until 22 minutes into the tutorial will
get a 0% grade on the tutorial. You may not leave earlier (at least,
not if you want to get any credit). So if you come in with correct
answers, you and your tutorial leader should be spending the time
jointly helping the other person at the tutorial if that person is
having trouble, or on you working additional problems, or etc.
That in fact was the plan regarding all tutorials; that you'd come in,
have most things right, and use the time to better understand those
things you had problems on, and then (insofar as the 30 minutes allowed)
work new (though often similar) problems to make sure you can, live in person,
demonstrate the kinds of skills that the set was about. This is particularly
important now, as we're in the part of the course regarding undecidability,
which is hard, and easy to fail to understand well; but solving problems
at the tutorial will help you have a better chance to understand it well
(or at least to realize that, if this is the case, that you are lost and
need to and should use Read's office hours to get additional help).
Part A: Exercises/Problems 5.1, 5.10.
For all undecidability
proofs here, make *sure* to use the flavor of the undecidability
template that is posted (with the 4/2 problems pdf, in
the other important info section) on our web site.
Part B:
Exercises/Problems
5.9, 5.12, 5.14.
For all undecidability
proofs here, make *sure* to use the flavor of the undecidability
template that is posted (with the 4/2 problems pdf) on our web site.
Part C: None. But if you finish the Part A problems and there is
still time left at your workshop, please work on (using our
templatethat is posted with the 4/2 problems pdffor
undecidability proofs) on additional undecidability problems (your
workshop leader will likely bring some in). Probably the first extra
one you will want to work on at your WS is the one problem (from the
pdf sheet posted in our Other Important Links/etc. section) assigned
to your group to present via the document cam at the 4/2 class
session! Of course, I encourage each of you to work not just on the
one problem assigned to your group, but on all five problems; doing
that will be a huge, huge help in getting better at the skill that is
the most central skill of this half of the term... and one that thus
might well play a very important role in Midterm II.)
If you have time left after that, you might wish to at WS work
on 5.11; but first, try to get a good solution, using the template's
approach (insofar as it can be made to work, see the caveat within
the 4/2 problems handout page), to the problem your group has been
assigned for the 4/2 class.
 Exercise Set 10, 4/94/10 (which means
that "parts A and B" must as usual be
handed in at the start of *your* assigned 4/9 or 4/10 tutorial;
you'll be working in groups on Part A in your 4/4 or 4/5 WSs)
IMPORTANT NOTE: Regarding your tutorial on 4/9 or 4/10, anyone who
doesn't stay at least until 22 minutes into the tutorial will
get a 0% grade on the tutorial. You may not leave earlier (at least,
not if you want to get any credit). So if you come in with correct
answers, you and your tutorial leader should be spending the time
jointly helping the other person at the tutorial if that person is
having trouble, or on you working additional problems, or etc.
That in fact was the plan regarding all tutorials; that you'd come in,
have most things right, and use the time to better understand those
things you had problems on, and then (insofar as the 30 minutes allowed)
work new (though often similar) problems to make sure you can, live in person,
demonstrate the kinds of skills that the set was about. This is particularly
important now, as we're in the part of the course regarding undecidability,
which is hard, and easy to fail to understand well; but solving problems
at the tutorial will help you have a better chance to understand it well
(or at least to realize that, if this is the case, that you are lost and
need to and should use Read's office hours to get additional help).
Part A:
For all undecidability
proofs here, make *sure* to use the flavor of the undecidability
template that is posted (with the 4/2 problems pdf, in
the other important info section) on our web site,
always keying on the set A_{TM}, as that template does.
This week's Part A you do NOT have to write up. Rather, I've asked
the WS leaders to spend the entire WS working on proving things
undecidable, via the template approach. So the WS leaders will make
up and bring in some problems, and ideally will give you about 10 minutes
to work on solving a problem, and will have someone present a
solution, and also people can ask about other solutions. And then
the same thing will happen with a second problem. And so on, until
there is not enough time to do another problem. It is very easy to
think you know how prove things undecidable just because when others
put up answers you feel that the answers make sense... but that is
actually not sufficient to ensure that YOU can on your own prove
things undecidable; so please plunge in and work, yourself
(NOT in groups of size more than 1) on each of the problems the WS leader
puts up; on Midterm 2, you will be working as a group of size 1, so you
need to be ready to solve things yourself. If you find after the WS
that you were not able to solve things, then keep in mind that you
(a) can additionally attend some OTHER WS, and (b) get thee to an office hour!
Part B:
NOTE 1: For all undecidability
proofs here, make *sure* to use the flavor of the undecidability
template that is posted (with the 4/2 problems pdf) on our web site,
always keying on the set A_{TM}, as that template does.
NOTE 2: Since some people will be writing two Part B problems for
turnin, and some will be writing up five Part B problems,
some tutorials will have people who have done different problemsbut
everyone will have worked on problems 2 and 4, and even those who do
not have to turn in problems 1/3/5
(i) Everyone must do problems 2 and 4 from the handout we went
over on 4/2. (Be careful; problem 4 is not easy.)
(ii) Those in the two WS groups WedearlyS and Thursearly must in
addition do problems 1, 3, and 5 from that same handout (and those in
the other four groups are of course free to also do those 3 problems,
for practice and to improve your skills at this central technique, though
if I were you I would not turn them in as a flaw on one of them could
drop you from a 100% to a 20%; but though you do not have to turn them
in, you certainly can write them up, and bring them in, though keeping
them separate, so that you can ask questions about any of those three
that you have problems with, if you tackle them).
Part C: None. But if you are a undecidability proof superwhiz,
and have no problems or worries or questions on that, then here is a
quick pair of problems for you to work on (that are not undecidability
proofs... well, in fact, there are, sort of, depending on what one
has previously established, but let us not focus on that issue here).
We perhaps won't go over these in class, except if there is time and
someone asks me (do!!), I'll verbally present answers to them.
For the rest of this problem, let us take it (this is not our standard
approach) that we defined all TMs to all have as their input alphabet
precisely {0,1}. Oh... for these Part C problems, you should probably NOT
focus on our use our template... but rather, should
plunge in and do what these problems are asking you to do.
Let INF = { <M>  L(M) is infinite}.
Let SIGMASTAR = { <M>  L(M) = {0,1}^*}. (The ^ is a superscript notation.)
The formalization of oracle is a bit of a pain, but basically view
them as magic unitcost subroutines for a set. (In reality, we need to
make special oracle tape, and special states to pass back the answers,
but don't worry about such details on this particular problem.)
(C.1) Give a Turing machine that, given access to an oracle
for INF, decides SIGMASTAR. (That is, given the access to the oracle,
which is allows to make questions to, on each input x it accepts if x
is in SIGMASTAR and it rejects if x is not in SIGMASTAR.)
(C.2) Give a Turing machine that, given access to an oracle
for SIGMASTAR, decides INF.
Note: In the lingo, you what you are showing
if you do both parts is that SIGMASTAR and INF are equivalent
with respect to recursive Turing reductions. You might find
some techniques (aka tricks) or twists or equivalences we've seen already
useful in nicely proving C.1 and C.2.
 Exercise Set 11, 4/164/17 (which means
that "parts A and B" must as usual be
handed in at the start of *your* assigned 4/16 or 4/17 tutorial;
you'll be working in groups on Part A in your 4/11 or 4/12 WSs)
IMPORTANT NOTE: Regarding your tutorial on 4/16 or 4/17, anyone who
doesn't stay at least until 22 minutes into the tutorial will
get a 0% grade on the tutorial. You may not leave earlier (at least,
not if you want to get any credit). So if you come in with correct
answers, you and your tutorial leader should be spending the time
jointly helping the other person at the tutorial if that person is
having trouble, or on you working additional problems, or etc.
As I mentioned also regarding the previous set,
that in fact was the plan regarding all tutorials; that you'd come in,
have most things right, and use the time to better understand those
things you had problems on, and then (insofar as the 30 minutes allowed)
work new (though often similar) problems to make sure you can, live in person,
demonstrate the kinds of skills that the set was about. This is particularly
important now, as we're in the part of the course regarding undecidability,
which is hard, and easy to fail to understand well; but solving problems
at the tutorial will help you have a better chance to understand it well
(or at least to realize that, if this is the case, that you are lost and
need to and should use Read's office hours to get additional help).
Part A:
For all undecidability
proofs here, make *sure* to (unless doing so is
impossible) use the flavor of the undecidability
template that is posted (with the 4/2 problems pdf, in
the other important info section) on our web site,
always keying on the set A_{TM}, as that template does.
This week's Part A you do NOT have to write up and hand in, except
you do regarding item (i) of part A (and of course
all of Part B). So, item (i) is: Prove the theorem
that is stated on the 21st page of our P/NP
slides, namely, prove that the set
{f  (each variable appearing in f appears the same number of
times) AND f \in SAT} is NPcomplete.
(As noted on that slide, both x and
x̄ (that is supposed to come out as x with a bar over it,
at least if your browser supports this) are viewed as
instances of the variable x, and so the formula
(x OR x̄ OR x̄) AND
ȳ
has the variable x appearing three times and the variable
y appearing one time.)
And item (ii), which you do not have to write up or turn in,
is the following.
I've asked
the WS leaders to again
spend (this time, almost) the entire WS working on proving things
undecidable, via the template approach. So the WS leaders for
example may make
up and bring in some problems, and ideally will give you about 10 minutes
to work on solving a problem, and will have someone present a
solution, and also people can ask about other solutions. And then
the same thing will happen with a second problem. And so on, until
there is not enough time to do another problem. It is very easy to
think you know how prove things undecidable just because when others
put up answers you feel that the answers make sense... but that is
actually not sufficient to ensure that YOU can on your own prove
things undecidable; so please plunge in and work, yourself
(NOT in groups of size more than 1) on each of the problems the WS leader
puts up; on Midterm 2, you will be working as a group of size 1, so you
need to be ready to solve things yourself. If you find after the WS
that you were not able to solve things, then keep in mind that you
(a) can additionally attend some OTHER WS, and (b) get thee to an office hour
(there are not too many left)!
Part B:
NOTE 1: For all undecidability
proofs here, make *sure* to use the flavor of the undecidability
template that is posted (with the 4/2 problems pdf) on our web site,
always keying on the set A_{TM}, as that template does.
Prove each of the following problems undecidable, by our template method.
For these problems, you should pretend that we defined things so that
all TMs have the input alphabet being precisely \Sigma = {0,1}.
(i) { < M1, M2, M3 >  (L(M1) = L(M2)) OR (L(M2) \neq L(M3)) }.
(ii) { < M1 >  L(M1) is cofinite}, i.e.,
{ < M1 >  \Sigma^*  L(M1) is finite}.
(Warning: "cofinite" is not synonymous with "infinite."
For example, the set of all even length strings is infinite but
is not cofinite.)
(Note: I am using ^ to denote superscripting.)
(iii) { < M1 >  L(M1) is coinfinite}, i.e.,
{ < M1 >  \Sigma^*  L(M1) is infinite}.
(Warning: "coinfinite" is not synonymous with "finite.")
(Note: I am using ^ to denote superscripting.)
(iv) The same as the problem on slide 21 of our P/NP slideset,
except with "the same number of times" changed to instead say
"a number of times that is congruent to 1, mod 5." So it would be
ok for a variable to appear 1 or 6 or 11 or 16 or etc. times, but
having a variable appear exactly 7 times would preclude membership
in the (thus modified) set. (Note: The "count.... purpose" comment on
slide 21 still applies to the current variant.)
Part C: None.
Other
Important
Links/Info/Resources:

Problems for the 1/29 and 1/31
Classes; see the Part C of Exercise Set 2 above for more info on
what to DO regarding these!.

Problems for the 2/7 Class.

Problems for the 2/14 Class.
And
here
are
the
doc cam solution sheets that Read projected while going over those on
2/14, except with two added ones to sketch the proofs of the 3c
and 3d, which he didn't have a chance to go over in class on 2/14).

Problems for the 2/26 Class.
 Information on the Scope of Midterm I (and
info on location, notes, etc.): The scope of Midterm I as
to Chapter 2 is somewhat implicitly given in the entry in the list
of Readings above, regarding the Chapter 2 readings. The scope of
Midterm I (and also some more general advice of
good things to review while studying for the midterm),
as to the areas/topics the slides call Chapters 1, 0, and 1, is given
the BB Announcement that in BB is dated "Friday, February 9, 2018
4:12:02 PM EST" and is titled "[CORRECTED] LOWER STRONG... some
important things related to the midterms and also attendance" EXCEPT
let me add to the exclusion list (that from that posting
already contains the "all but 1000" problem) the "Extra Problem"
from Exercise Set 3. Also, to remember that both our midterms
are NOT in our classroom, but are in Lower Strong Auditorium.
So Midterm I is March 5 at 325PM in Lower Strong.
Also, be aware that though the Syllabus lets you bring into
the midterm a **HANDWRITTEN** and PREPARED BY YOURSELF
one 8.5x11 2sided sheet (or two 8.5x11 1sided such sheets) of cram notes,
if we catch you using a nonhandwritten such sheet, that will be
submitted as a case to the Academic Honesty Board (and the sheet will be
confiscated); your sheet MUST be handwritten and prepared by yourself.

Your seat
assignments for Midterm I and for Midterm II, both of which will
be in Lower Strong Auditorium at 325PM440PM (respectively on
Monday 3/5 and Wednesday 4/18).

Midterm I solution sketches are
here.

Notes on Recursive Presentations of Classes (i.e., notes on the
two (or three, depending on how one counts the problem(s) on
the final slide) challenge problems from the end
of the Chapter 3, Part 2 slides). (Those are two of
the three problems
that will be covered in our 3/21 class, and I'll
make public this pdf probably during the first minute of
the class, so that it will be available for you to read
any time after class.)

Problems
for the 4/2 class, and a very helpful template (regarding the task
"prove a problem undecidable by contradiction"),
and a worked example of using that template.
(WARNING: For the reason
mentioned in the "WARNING" at the start of this document, you
probably should NOT read this document until after the 3/28 class session,
aside from, if you have a 3/28 WS, being aware that the template exists
and bringing it in to your WS.
And all of you will want to read, as soon as possible after
the 3/28 class (so probably the evening of 3/28
at latest), this problemcollection/template/etc.,
since these are the problems for which you and
your WS groupmates will put your assigned one's answer
up on the board before/at the start of the 4/2 class session, and
you may well solve them at your 3/273/28 WS!)
 Information on the Scope of Midterm II (and
info on location, notes, etc.):
The scope of Midterm II as
to TMs/decidability/undecidability includes all the material
we covered in class, readings, exercise sets,
the 4/2 pdf (including the templatebringing in the template,
handwritten,
as part of your allowed cram sheet would be VERY wise) and even
the "notes on recursive presentation of classes" (but if there are
any Midterm II questions or points
on the latter, they are unlikely to be anywhere near as numerous
as will be the questions or points regarding proving things undecidable),
or slides;
and of course the questions
may be new questions or issues that connect to or draw on any of those
things.
Note/modification added 2018/4/9: In order to let you better focus
on the template/contradiction method of proving things undecidable,
the material on the eight slides of "Chapter 5, Parts 2/3"
will *not* be in scope on Midterm 2.
As to our P and NP unit, the scope of what might be asked about it
on Midterm II is the material on the following slides (and of
course there
might be on Midterm II questions/issues that are not on those slides but that
connect to or draw on the slides' material) from our handdrawn slideset
that we used for that unit (by the slide numbers here, i mean
the page location within that 26page, not numberedonthepage pdf):
slides 35, 6 (top 2 lines),
8 (just the fact that coNP = {L  \overline{C} \in NP}), 9 (top half
of the page), 1011, 1421. (Note that I above am being very specific
regarding what is in scope as to the P/NP unit. I am doing so as I want
you to be able to have lots of time to spend mastering
how to prove things undecidable, since at least as of when
I am writing this2018/4/7many people are severely struggling to get on
top of proving things undecidable; if that applies to you, do not wait,
but rather do the various things I have suggested in class and via
a BB posting, such as for example using the office hours.)
Midterm 2 is
NOT in our classroom, but is in Lower Strong Auditorium, on Wednesday, April
18,
from 325PM440PM.
As per the syllabus, you may use only black or blue ink (or if you really,
really feel the need to use pencil, then black pencil).
Also, be aware that though the Syllabus lets you bring into
the midterm a **HANDWRITTEN** and PREPARED BY YOURSELF
one 8.5x11 2sided sheet (or two 8.5x11 1sided such sheets) of cram notes,
if we catch you using a nonhandwritten such sheet, that will be
submitted as a case to the Academic Honesty Board (and the sheet will be
confiscated); your sheet MUST be handwritten and prepared by yourself.
Also, as was the case at Midterm I, seating is preassigned (the seating
assignments are posted on this web page, under Other Important Links).

In case you'd like to have them (they are me doing in pen right at
the doc cam some undecidability proofs, via the template/contradiction
method),
*though with no promises made about them (see page 1 of the scan)*, here
is
a scan of
the doc cam sheets from the 4/16 325pm class session and
my 4/16 450pm605pm review session.

Academic Honesty.

The Center for Excellence
in Teaching and Learning (CETL) provides a wide range of services including Disability Support/Resources.

The DBLP Computer Science Bibliography.

RSI Information.
Some of My Favorite Bits of Science Wisdom:

After solving a challenging problem, I solve it again from scratch,
retracing only the *insight* of the earlier solution. I repeat this
until the solution is as clear and direct as I can hope for. Then I
look for a general rule for attacking similar problems, that *would*
have led me to approach the given problem in the most efficient way
the first time.  Robert Floyd

In computer science, elegance is not a dispensable luxury, but a
matter of life and death.  Edsger Dijkstra

Imagination is more important than knowledge.  Albert Einstein

They are ill discoverers that think there is no land, when they can see
nothing but sea.  Francis Bacon
Other Odds and Ends (Mostly Quotations):

I don't believe it. Prove it, and I still won't believe it.
Life, the Universe and Everything

It was mentioned on CNN that the new prime number discovered
recently is four times bigger then the previous record.

Sooner or later society will realize that certain kinds of hard work
are in fact admirable even though they are more fun than just about
anything else.  Donald E. Knuth

Getting tenure doesn't really change anything.
However, not getting tenure changes everything.

My late friend Stan Ulam used to remark that his life was sharply
divided into two halves. In the first half, he was always the
youngest person in the group; in the second half, he was always the
oldest. There was no transitional period.
 GianCarlo Rota, "Indiscrete Thoughts"

Fools ignore complexity. Pragmatists suffer it. Some
can avoid it. Geniuses remove it.
 Alan Perlis, Epigrams in Programming

More Quotes from Dijkstra:
* None of the programs in this monograph, needless to say, has been tested on a machine. (From "A Discipline of Programming.")
* Computer science is not about computers, any more than astronomy is about telescopes.
* The question of whether computers can think is just like the question of whether submarines can swim.

"Supposing a tree fell down, Pooh, and we were underneath it?" [said Piglet.]
"Supposing it didn't," said Pooh after careful thought.
Page Maintained by: Lane A. Hemaspaandra