-
Session Topic:
Introduction to the Course.
Included:
general introduction to the course and
review of the
Course Information Handout;
background information sheet;
diagnostic quiz (does not count towards the course grade).
- Questionnaire on Background. Here.
- Diagnostic Quiz. Here.
Note: As mentioned in class, this was just a test
(so to speak) run, and does not count towards your course grade (as a
multi-chunk quiz or otherwise).
- Diagnostic Quiz Answers.
Here.
- Diagnostic Quiz Statistics. Low/Median/High: 0/0/3 (out of 20).
This quiz does not
count towards your grade, so
don't panic at all.
- Slides. Slides (for a prefix of the course) are
here (as pdf rather than postscript).
The following very strong disclaimers apply:
No promises of any sort are made about these xeroxes (some
slides may be missing that I will use, some slides that are in the pdf
I won't use, some I'll have edited somewhat between when they
were scanned and when they'll be used in class,
etc., etc.). They are simply made available to you in case you
choose to make a copy of them. Note: The first sheet has the
number "0" and the last one has the number "101," so there are 102
sheets in total in the pdf.
But indeed you should each please make a xerox of this
about-102-page-long item, as it will save you lots of note-taking
time/effort in class. Namely, you might wish to add your own
hand-made class notes right
onto these sheets during class.
- Reading (due 090909/159pm).
-
In our Hemaspaandra-Ogihara textbook, read the
"Invitation" subsection of the Preface. This will give you
some insight into how I view complexity (the topic that we will
cover as the second part of the term). By the way, you'll notice
even in the first part of the course that many proofs are
quite algorithmic (or perhaps procedural, if you want to be very
finicky about word use).
-
In the first edition (the 1979 first edition, that is---NOT
the 2nd or 3rd editions) of
Hopcroft and Ullman's "Introduction to Automata
Theory, Languages, and Computation"
(Addison-Wesley)---which is on
reserve for us at the library---review chapters 1, 7, and 8.
Do not use the
*second* edition of the same book
(which has DIFFERENT authors: Hopcroft, Motwani, and Ullman)---use
the first edition only for this reading.
You should also review the
following (as another treatment of some of the same stuff):
In our Bovet-Crescenzi textbook,
Chapters 1 and 2 except skip sections 2.1.4 and 2.1.5.
You can also look at the analogous parts of Chapter
2 of our (optional textbook) Papadimitriou if
you like, but actually Bov-Cre is actually
clearer on this.
-
Also, though we went over it in class today,
you should read for yourself, in full detail,
the class information handout, so
that you know the rules under which the course will
operate (it is always available,
in its most recent version, from this web site).
The version handed out in class today is version 1.00, which
is (currently) the current version.
If/when I create updated versions during the course, I
will announce that via
a "note" on the this page.
(On each version of the course
document, the base date will be the date of version 1.00 and the
"last updated" date/time will be the date/time of the version you are
looking at. Oh... if I ever say a document is up and it isn't up,
please let me know. Sometimes the TA or I put into the
web site but forget to turn it from latex into postscript, and so
we think it is up but if you click on the link it won't be there.)
- Note 1 (090902/901pm). Notes will be used by me to stick
on comments and so on. The number will be only within the class day,
i.e., the first note, if any, after the next class session will again
be a "Note 1." Note that I may put up new notes as the day goes
on, or during the days between one class and the next. Notes start
with the date/time they went up, in the format YYMMDD/time.
(I at times will, often
for emphasis, instead use
the format YY/MM/DD/time or even YYYY/MM/DD/time.)
Note: It is now 9:01pm on 9/2 and if you're seeing this and
this is the last note, please be aware that I'll probably between
now and the next class put up here
a bunch of additional notes, and most of them
will probably go up this evening (actually, I'll before saving
this file stick in lots of notes, and then save it to the web...
but even after that I might add more notes between now and next
class, so please do look here often).
- Note 2 (090902/901m).
Oh... I'll generally try (though I am not promising this in blood; for
example, today's entry has lots of notes and so will probably be
completed and up around 10PM) to have
the web site up and (relatively settled
regarding the stuff that happened in that day's class, except perhaps
whatever
Notes (such as this one) or quiz solutions or statistics
that will be added later) by about 9PM on the given day. A corollary
is even if you peek at the page before 9PM, you should definitely
reload the page (making sure not to get a cached copy!) after 9PM---or
early the next day---so
that you get the final version of the readings/etc. (Note: very
often I'll have it up even earlier.)
- Note 3 (000902/903pm). How to avoid having your browser
cache pages: It varies from browser to browser and I'm no expert
on that. In Firefox you might want to just bite the bullet and
set your cache size to 0 (under Tools/Options/Privacy/Cache). Under
Internet Explorer, probably a good approach is to go to
Tools/Internet Options/General/Temporary Internet Files/Settings,
and then change that to "Every visit to the page" (do NOT
trust "Automatic" to do the right thing---it does not, I think).
Note that even if you do the above things, sometimes
browsers hold things without rechecking them. This most
typically happens on things such as postscript documents
called by links from web pages (even when it knows to recheck the
web page each time, a browser may be too lazy to do that for
files in its cache). If you have problems with that, simply
emptying your cache should get you the fresh version of the object.
Note that in Netscape/Mozilla/Firefox, if you find that
it seems not to be grabbing the most current version of a web page
(and on some browsers, using the forward/back buttons
evades even the most emphatic preference settings),
it often helps to simply use
Shift-[ReloadButton] to tell it, "Go check again."
Disclaimer: Hey, I'm a theory professor, so I'm probably
the worst person imaginable to take advice from on taming your
browser.
P.S.
A bit of
additional browser
advice, from a
Firefox fan:
[Here is] how to tune cache settings for Firefox. The following steps
are used do it:
1) Type "about:config" (without quotes) in URL bar, press ENTER,
2) Find key "browser.cache.check_doc_frequency",
3) Change value to "1", which means "Check every time I view the page".
That should do it. The default is "3 (default): Check when the page is
out of date (automatically determined)", but that does not always work.
- Note 4 (090902/905pm). Don't panic; note 3 is unlikely to
be on midterm I or the Comprehensive Exam.
- Note 5 (090902/905pm). Oh... if you happen to be interested in
theory, please do feel very much invited to attend the
Rochester Theory Seminar if you wish. It is open to
the public, and is filled with lots of interesting stuff.
It meets 2 or 3 times a month, right after the CS Department
Seminar's slot.
You can find full information (still for the past year, but
the info for the current year will be up soon)
via the following link:
Rochester Theory Seminar Home Page.
- Note 6 (090902/906pm).
The two chapter 1's (chapter
1 of Bov-Cre and chapter 1 of Hop-Ull) from your reading assignment
give some coverage of discrete math
basics. However, if you are seriously short of discrete math
background, that is a severe worry. If you fall in that
category, *please* read
carefully one or more of the following
excellent discrete mathematics books, some of which
are on---or on the way to coming back from recall and
being on---reserve for our course (Biggs;
Graham-Knuth-Patashnik; Gries-Schneider; Maurer-Ralston; Rosen) on
reserve. The best one to start with is perhaps Rosen---if you have
problems with proofs, pay particular attention
to the chapter on proof techniques
(it was Chapter 3 at least in the older edition I knew),
and to the proofs throughout Rosen's book.
In particular, though we will read or cover quite a bit about
undecidability, we can't possibly build the MTH150 course (the
undergraduate discrete math course) into this course. So, do make
sure that you know (as in, by this coming Wednesday at latest) the
equivalent of MTH150. As to what that means, you can easily see that
(and, implicitly, what to read in Rosen)
from the MTH150
web site's course outline (look at the "weekly schedule" part of
that page in particular).
- Note 7 (090902/908pm).
Very many people seem not to have ever seen or had a course touching
on how to prove things undecidable (although quite a few of
those people seem to have
had an undergraduate models course that covered regular sets,
CFLs, and often Turing machines, but that
stopped just sort of reaching such
issues as undecidability).
So, if you are such a person---someone who has not before
had a course that covers how to prove something undecidable,
you have much company.
This isn't a cause for panic. Rather, in light of how many
people have this particular background, we'll do the following. The
coming lectures will take as a starting point that people know the
basics of Turing machines (and your current reading assignment will
review even that, and at the very start of the next class I'll
actually quickly define even the basic formalization of Turing
machines right in class),
but we will as part of this course review the definitions
of recursive/RE/undecidability, and cover in quite good detail the
techniques for proving undecidability, and will try to do so in such a
way that even people who have not had that before will, with serious
effort, be able to learn it from this class. (I apologize to the
people
who are coming in
with a broader exposure, in case this prefix of the course may be a
bit repetitive to you. However, Knuth, one of the most brilliant computer
scientists ever, always says that he himself only learns something
deeply after seeing it at least twice. So maybe the review
will help you lock this material in even more firmly.)
As a side effect of the above, let me mention that if there is a
surprise quiz this Wednesday, I will *not* ask you to already on that
prove things undecidable. So, just to be clear
about this particular possible surprise quiz (or surprise
quizzes!): Anything about the course
logistics mentioned
during the first class session might be on the quiz, anything about the
course info handout might be on the quiz, but as to reading material,
for this particular quiz, what might be asked includes just:
the "Invitation" of Hem-Ogi, Chapter 7 of the *first*
edition of Hop-Ull (yes, classic 1979 edition with only two authors, not
the lower-level second edition)
and Chapter 2 of Bov-Cre except not sections 2.1.4 and 2.1.5 and 2.2.
(This doesn't mean you should ignore the other stuff, such
as Chapter 8 of Hop-Ull and Section 2.2 of Bov-Cre, but rather,
I'm just trying to more tightly define what might be on the quiz.)
Quizzes can be of any form. For example, regarding Chapter 7 I
might (or might not!)
give one or two theorems from your readings---or things that
look very similar to those theorems but are not (or are) true
statements. Note that you generally will have
a much better shot of doing well on quizzes if you do the reading
carefully and make a good notes sheet. And of course,
making this page your home page (or at least reading it
all the time) is a good idea, so that you can read (with
luck) helpful notes such as this one.
Oh... in addition,
regarding any possible quiz next class, in addition to everything
the above puts as potentially on the quiz, all of the discrete math
prerequisites are also fair game to be on the quiz (see Note 6 for
points on how to review discrete math if you've forgotten it). If I
were you, I'd make sure to come into class on next class with a very firm
grasp of such notions as, for example, proof by induction. If there
is a quiz next class (and there very, very well might be one), it might very
well be for a short period of time yet have multiple questions on it,
so you'll want to come into class with a firm, comfortable control of
the items mentioned in this note (as there will
not be time during the quiz to thrash around).
- Note 8 (090902/913pm).
A reminder regarding the books on reserve at the
library:
Please remember, if you look on the regular shelves under their
call numbers for books on our
reserve list, you'll usually find nothing. That is because books on
our list are on reserve.
What this means
is that you must to go the library main desk to request it (and so
that everyone can have a chance to with luck have
equal access it can be kept out for a fixed period of
time---2 hours for some books
and overnight for
the others).
By the way, you are responsible for all the readings, even if you
have bad luck and the reserve copies are heavily checked out. It is
true that the reserve copies can get very busy during the few days
before a class (that might have a surprise quiz---and they all might)
or before a homework set is due, so if you want to use those, you'll
want to start very early to be safe.
- Note 9 (090902/914pm). Regarding "Hopcroft-Ullman"
(which, in the second/third editions, actually adds Motwani as an author),
please don't confuse the editions, or do problems or
readings in one when I in fact ask you to do such in the other.
(note that the chapter numbers and problems are NOT identical between
the editions). FYI,
the first edition is written at a far more
advanced level/flavor than the second and third editions.
Almost always when I
use one, it will be the first edition that I use (the one with
copyright date 1979!!!!... not the copyright date 1969 one, and not
the one copyright date 2000 one, and not the copyright 2006 one).
- Note 10 (090902/915pm).
I commend to your attention the rules of the course regarding the one
sheet of handwritten self-prepared notes that you are allowed to use
on surprise quizzes. (I think the act of distilling information
and preparing such a sheet is itself a valuable learning experience.
And who knows... when you are sitting there at some quiz with your
books and notes closed to you, you might at times be very happy to have your
one-page-of-wisdom open to you.) Of course, so far we're only coming
to the second class, so maybe you think there is not much
to write down... but when we're a bit deeper into the course,
and you (with luck) have lots of learned things to organize, the notes
sheet can really be a help... and even before next class, you'll have
a reasonable amount of information (from the readings, for example!) to
distill.
- Note 11 (090902/916pm). Oh... just to
make sure no one has any unpleasant surprises later in the term
regarding academic honesty or regarding grading/regrading rules:
-
please do read extra carefully the section of the course info handout
called "homework preparation" so you know what is cheating (as that
is very very bad and the school's firm academic honesty rules apply in
that case) and, and this is important too, what is quite allowed in
the course (as knowing that will help you learn collaboratively with
your class colleagues).
- please do read carefully the grading
rules... e.g., regarding chunks and dropped chunks
For example, a quiz that has 6 10-point questions
might if one were careless look like a 60-point quiz as it has 60
points (and we list the statistics on such things and homeworks and so
on in terms of a 0-60 or 0-whatever range), but do keep in mind that
it in terms of chunks such a quiz is six separate 10-point chunks when
it comes to the issue of computing your grade and chunk-dropping.
NOTE IN PARTICULAR: Sometimes a question may look as if it
is an integral 20 (or 30, or) point question. Such things
are handled as follows (in the case of 20, in this example).
It is actually two identical 10-point chunks, i.e.,
if you got 7/20 then this is recorded as two 3.5/10 scores. you'll
see this type of superchunking in a big-time way if we have a course
project---e.g., if the project has the value of K points (K being
a multiple of 10), it actually will be K/10 identical chunks, each
of which will have the score YOURSCORE (out of an ideal total of K)
times 10 divided by K---and possibly on midterms or elsewhere.
- Note 12 (090902/918pm). As to Homework Set 1 (and maybe
even Set 2), it probably
will be given out on the next class's web block.
For now, please focus mostly on
the things mentioned above, such as the reading (and, if you have
worries about background in discrete math or DFAs/NFAs and so on, in
also doing reading related to those).
- Note 13 (090902/919pm). Usually, we will not put a note up
when we put up the scores or answer sheets. They have slots around where
they naturally belong,
and will appear there typically before the class or two after the item
for the case of scores, and also for the case of answers in those cases
where there is a slot for answers.
- Note 14 (090902/924pm). FYI, when
we update an already posted answer sheet and the changes
are important, we will
typically (although no promises in blood here)
post a note letting you know to re-download the
revised answer sheet. Answer sheets will always
(unless we're careless), if they have been
revised, contain the revision date and time.
- Note 15 (090902/924pm). Reminder: If you want a
bookmark that will always take you to the most recent material on
the page directly (i.e., to the bottom of the page, rather
than the top of the page), please look,
near the top of the page, at the discussion under "Navigation
Information." Myself, I do use that suggestion regarding my bookmark
for the page---so that I always when I click on my bookmark indeed
get sent to whatever is most recent. (My guess is that you also
will want to use that. It save you from having to scroll down
the web page each time.)
- Note 16 (090902/928pm).
Oh... most of the documents for the course will go up as postscript
documents. Of course, the URCS machines have postscript previewers,
and free postscript previewers are easily available, e.g.,
at this site.
- Note 17 (090902/928pm).
Oh... I use the UR "yellowjacket"
icon to separate days of the course on this page. But, so that you
can quickly tell the bottom of the page from the other separator
characters, the bottom
of the page has not a single yellowjacket, but a row of two
of them (almost mirror-imaged, except for
its "UR" being readable forward on both).
- Note 18 (090904/1213pm).
As I mentioned earlier,
usually, we will not put a note up
when we put up the scores or answer sheets. They have slots above where
they naturally belong,
and will appear there typically before the class or two after the item
for the case of scores, and also (sometimes, as now,
even earlier) for the case of answers in those cases
where there is a slot for answers (typically quizzes and
in-class midterms; homework sets we'll instead go over in class).
However, because this is the
first time any answer set has gone up, let me mention that
you can now find (in the natural place above) answers for the
diagnostic quiz. But do not worry---I will NOT on the
(very likely surprise) quiz next class quiz you
again on building such reductions... rather, we'll (somewhat quickly, I
hope, but we'll take whatever time is needed)
via reading and class lectures build to the point where you can
(I hope) confidently do such proofs.
Although we as I just mentioned typically don't mention when
answers go up, and an exception is that we do typically mention when
answer sets that were up get modified nontrivially. We don't have an
example of that yet, but when it happens, you'll be able to tell that
as (we'll mention it in a note typically) and the revised answers will
have a string on them of the form "revised 090904/1229PM" or whatever
date/time holds.
- Note 19 (090904/3123pm). Reminder: There is no class
this coming Monday (it is Labor Day and so a federal and a University
of Rochester holiday; I forgot this myself in part when putting up the
web site initially and so spoke of giving a quiz on Monday, but
since there will be no class on Monday there will be no quiz
on Monday). So the next class (and its
likely surprise (!?) quiz) will be on Wednesday, September 9. As
hinted in an earlier note above, you certainly will want to come into
that class with a good knowledge of, well, all the stuff mentioned in
the earlier note regarding that possible (very, very possible ;-})
surprise quiz, which will very likely ask questions both about the
rules/etc. of the course and about the material from the reading (but
just in the ways described in the earlier note, so you might very well
be asked to prove some theorems that are proven in Chapter 7 of HU but
I will not on Sept. 9 quiz you on the material of Chapter 8 of HU even
though that is in your reading).
- Note 20 (090906/647pm, revised 090906/657pm). Actually,
since some people are hitting the Chapter 7 HU (i.e., Chapter 7 of the
Hop-Ull 1979 book) material for the first time, let me make a bit less
broad the scope of what could be on the (very likely) surprise quiz
next class. I had said that I might as you to prove some of the
theorems from Chapter 7, but let us say I in fact won't do that this
next class (although I might well ask you to do that in the (very
likely) surprise quiz the class after that). However, you certainly
should *know* all of the theorems of Chapter 7 (e.g., if I ask you to
quote some, or I give something that looks like one and ask if it is
true, or etc., etc., you should be prepared to answer that question
well). And, again, in addition to one or more questions about Chapter
7, there will also be one or more questions on the rules/logistics of
the course, so do review the first-day information sheet too,
carefully. More broadly, please use the gap between the first two
classes to do all the assigned reading (and make sure to do all of it,
e.g., don't forget to read the Preface of the Hem-Ogi book, as that
too could well be asked about on the surprise quiz), and, if you have
any holes regarding background such as regarding discrete math or
finite automata or Turing machines, please use this between class
period (and the various books on reserve for this course, and also
your textbooks) to close those holes.
- Note 21 (090906/710pm). By the previous note, I don't
at all mean to imply that those proofs (from Chapter 7) are not
important; they are important. But I'll in the next class very
briefly go over (very quickly) the flavor of a few of them, and so
that you can see that before your quizzed on them, the previous note
shifts back (to the class after next class) the time point regarding
when you'll be asked to show that you can prove theorems from Chapter
7.
- Note 22 (090906/717pm). Remarkable fact: Just some
hours before next class's (surprise) quiz, the date/time will be
09/09/09 09:09:09.
- Note 23 (090908/222pm, revised 090921/656pm).
Very Important: Midterm I will
be October 19th, so please unless you have already spoken to me about
a conflict on that day make absolutely sure to be in town on that day
(if you don't take a midterm, the loss of points would utterly kill
your course average and thus your grade).
-
Session Topic: Introduction to the Course II, and Turing
Machines. Went over the lovely non-constructive proof that
(\exist irrational positive real a)(\exist algebraic irrational
positive real b)[a^b is rational]); brief comments on constructive
versus nonconstructive proofs; went over the goal-structure of the
course, namely, that of course the main and general goal is to
cover the material of the course (the study of computability and
of complexity), but that as a shadow goal I hope the course will
also give you some sense of how theoreticians think and approach
problem (formalizing notions carefully, framing claims and proving
claims, etc.) since that approach can be helpful and is often
employed not just in theory but also in AI, systems, etc., and by
the way, as a sub-shadow goal, if/when time allows, I'll try to
give you some insight into some of the logistics/tales/etc. of
research/academic computer science (e.g., the story today about
the famous paper that when proving an "if and only if" statement
accidentally proved one direction twice and the other direction
not at all; by the way note what one might learn from that: if
even great theoreticians can make rookie mistakes, then all the
rest of us---who are in even more danger of error---should be
amazingly careful indeed to check and recheck every step and claim
of our proofs); reminded the Ph.D.-program students to please not
exclude, for example, any 3-2 student regarding outside-of-class
homework discussions and so on;
why you should
always have a pen and paper near your bed;
how Donald Knuth reads a paper, and that his way is a very
(time-consuming but often) wise way
to read papers/textbooks/etc.;
Turing machine definition
(and reminder that they are defined as
an octuple of things, or a septuple if one is
in
the Hop-Ull model---as we will
be except we'll not adopt their sticky-accepting-state approach---and
thus one does not have a left-end-marker,
and some
quick comments on the nasty ``sticky'' feature of the
Hop-Ull definition; see the long comments on these issues
later in this day's entry)
in the Hop-Ull model;
2 stacks = 1 tape; quick comments on why 2-dimensional
tapes are no better than a 1-dimensional tape;
pairing function (between pairs of integers, and the integers);
counters and pebbles (e.g., if we use a left end marker
then two pebbles can simulate two counters just fine);
definition of the
recursive sets and the RE (recursively enumerable, and we will
next class see the robustness of the notions) sets.
- Quiz. Here.
- Quiz Answers. Here.
- Quiz Statistics. Low/median/high = 5/21.5/30 (out of 30).
- Midterm I Date. Reminder: Midterm I will be on October 19th,
2009. See the note under the first class of the term's web
section above.
- Reading Reminder. There was a lot of reading due
today. If you didn't do it all already, then please do it now
(and please always do the reading, on time).
- Comment. I mentioned in class today that the a^b problem
is related to one of Hilbert's famous problems (the 7th, in fact).
Just in case you are interested, to read Hilbert himself giving his
problems, click here
and you'll see Hilbert's talk from the year 1900. (The part on the
7th almost sounds like he is saying his conjectured statement has a
known proof, but he isn't... he is guessing that it will be true, as
one can tell from his last sentence). By the way, the insanely
heavyweight theorem---the result that I know the proof of which would
stump the whole CS faculty (myself included) if we were in a locked
room---behind the curtain here is the Gelfond-Schneider Theorem,
which says that if a is an algebraic number other than 0 and 1, and b
is an irrational algebraic number, then a^b is transcendental. Note
in particular that this implies that (sqrt(2))^(sqrt(2)) is
transcendental. So, by the proof in class today, plus that
application of the (hard, powerful) Gelfond-Schneider Theorem, a pair
(a,b) meeting the conditions of the the issue---prove there are an
irrational a and an irrational, algebraic b such that a^b is
rational---is a=(sqrt(2))^(sqrt(2)) and b=sqrt(2). More to the
point, note that the simple (although nonconstructive) proof we gave
in class shows that appropriate a and b exist (and the simple proof
did NOT require appealing to some way-heavyweight theorem).
- Fun with Left End Markers.
(Please read this and the item right after it, about
sticky/nonsticky stuff, very carefully. Model issues
are subtle, tricky, and easy to get confused on.
Note that even THIS item itself is very carefully spun---note
how I end this item---to
intermesh well with the sticky/nonsticky stuff of the
following comment. By the way, note that in light of this
comment and the next, you should on your homework regarding
programming Turing machines NOT treat
TMs as octuples, but rather as septuples. Of course, this
distinction becomes much less interesting after around a week
from today, when we'll mostly be thinking in (much) higher-level terms
than actual programming of Turing machines.)
Actually, to avoid there
being conflicting models in the class, let us say that from now on
we'll adopt (in particular on this homework) the Hop-Ull approach
to the left-end of the tape.
Note that they actually do NOT use an explicit left-end marker.
They use a (somewhat kinky) scheme in which, briefly put,
if the machine has
its head is
on the leftmost tape cell and it tries to move left, then that
particular path simply has no next ID. Routinely, if a transition
function has no next state that is a way to make a machine halt.
However, THAT is about the transition function. Here, I simply
mean that if the transition function itself, for example,
tries to have the machine move left when
its head is
on the leftmost tape cell, then regardless of what state (if any)
the machine tries to say we should go into, we (at the
meta-level of interpreting things) view this as being a case
in which the current ID has no next ID. This does raise
the issue of whether THIS is a type of halting. The issue is
important as it ties into our definition of acceptance.
So, to be clear, let us say that when a machine has no
next move/ID, either due to their being none in the
transition function or due to their being none due to this
override case kicking in, that the machine indeed is viewed as
having halted (on the current path).
- Fun with Nonsticky/Sticky Accepting States. But we will
diverge from Hop-Ull is that we will treat machines as accepting
not if they on some path can reach an accepting state (read
as they've written things,
that is what Hop-Ull have as their notion of acceptance) but rather
if they on at least one path HALT from an accepting state.
(Hop-Ull try to finesse the whole issue with their "w.l.o.g." that
comes two sentences before Example 7.1, but that "w.l.o.g." while
true in a formal sense also has a rather evil unintended
consequence,
and so we will not adopt it.)
- Homework Set 1 (due 200pm, Wednesday, September 16).
These problems
are 10 points each.
Hop-Ull is (always) the 1979 Hop-Ull book. Writing TM code is
time-consuming, so please do start early!
-
(1) Hop-Ull problem 7.1a (i.e., part (a) of problem 7.1).
Use the Hop-Ull model (except NOT its
``sticky'' quirk---see above).
Note regarding this problem and problem 2 of this set also:
Regarding the H-U problem 7.1 questions, it might be natural to
wonder whether I am on this answer looking for pure pseudo-code, or
delta function + pseudo-code, as H/U do on page 152, or would
either be acceptable as long as transitions are not ambiguous? And
the answer to that is that the point is to really (well, "really")
program TMs, so your answer will need to outright specify the tuple
(states, transition function, work alphabet, etc.), totally, that
defines a TM. Along with that (and whether you choose to
interleave that with the tuple specification or do it separately is
up to you, but you should overall have given a clear and complete
specification of the tuple that defines the machine) you indeed
probably should, to help make your answers clearer (and to help get
partial credit if your detailed code is flawed---and it is
distressingly easy to leave flaws in code), include some high-level
words/description/pseudocode of what your machine is trying to do.
But the actual machine specification should give/define a fully
specified Turing machine. (And yes, it is painful. But as CS
people, we live as if we understand Turing machines intimately. It
is a good thing to have actually gotten one's hands dirty at some
point programming them, so that one can, in the future, have a
better feel for the objects that are being used in so very many,
many of our proofs. That is, you'll better understand how very
much is being pushed under the rug when you (or I) in some proof
mention that a Turing machine can easily be assumed to have no
problems dancing in the moonlight (or whatever).)
-
(2) Hop-Ull problem 7.1c (i.e., part (c) of problem 7.1).
Use the Hop-Ull model (except NOT its
``sticky'' quirk---see above).
-
(3) Hop-Ull problem 7.3 but solve it just for the special
case k=1, l=3, and m=2. (Note: You should already have read the proof
of Theorem 7.4, which does what would be the
k=1/l=2/m=1 case of problem 7.3 if 7.3 were made simpler
by deleting the word "nondeterministic." However, in your
solution, you should do exactly what I mention above:
problem 7.3 but for the special
case k=1, l=3, and m=2, and 7.3 does have the words "nondeterministic"
and "deterministic" in it.)
Note (regarding problem 3, but the comment applies more generally):
As mentioned below, understanding the questions is a real
part of doing problem sets.
But let me mention regarding this
problem that I
think that the text location most of you are
probably going to look at, the bottom half of page 164 (about
a 2-dimensional tape), pretty
heavily telegraphs what one most naturally may
mean regarding what it means to have a 3-dimensional tape.
Of course, in your solutions, do be clear about what
you take it to mean. In fact, more generally,
When interesting
issues/boundary cases/loophopes/etc. come up on homeworks, do
discuss them in your solutions. These can be very interesting---reading
sharply and closely, and noting interesting issues, is a great
habit to have!
- Homework Set 1 Answers. Typically, homework answers
will be done not by having an answer set on the web site, but rather
we'll go over the homework in class. However, since this particular
set is just TM programming and a TM model-equivalence issue, this
set is an exception, and we'll not go over it in class but rather will
post an answer set here. So, the homework answers are
here.
- Homework Set 1 Statistics. Low/median/high = 0/24/29 (out of 30).
- General Comments on Homeworks. Well, since I have
posted the first set, let me mention this (as was also noted in
class earlier), regarding in-progress homeworks in general: Since
understanding the questions is a big part of homework questions, I
typically don't answer questions on in-progress homeworks. Either
via an answer set or (more typically) via my going over them in
class, you'll eventually see all, and you'll understand it all the
better if you have thought hard about what the question means and
about finding its answer. (However, it is possible that the TA at
his office hours might be a bit more flexible regarding answering
questions for in-progress homework.)
- Note 1 (090909/653pm). Hint, hint, hint: It would not be
shocking if next class we had a quiz whose question (or
questions) might in part draw on your confident understanding of
material that has been covered or mentioned in the course so far...
so know the reading please (they are a real and important part of the
course), and know what we covered in class. I'd say it wouldn't even
be utterly shocking if you were asked to prove (or give the idea of
the proof of) something (or some things). In fact, let me a bit a bit
more explicit (see also the hints given in class).
It is important that you all quickly become comfortable with (and
decently expert on) Turing machines and the fact that certain models
are equivalent to other models and so on (and on!). So, let me
mention some things. On the (surprise!) quiz Wednesday, I will (along
with perhaps other questions) ask you to prove at least one (and
possibly more of Hop-Ull Theorems 7.1, 7.2, 7.3, 7.4, and 7.5 (and not
your choice among those... rather,
I'll on the quiz tell you which one(s) to
prove, or the sorting hat will choose).
So, knowing the proofs---really knowing them---is a good
idea. No kidding.
During the
quiz you may, as you know,
have just one sheet of self-prepared notes, of course.
Those are the rules. And it is (sigh) legal if you really want to embed the
answers on those sheets, but even if you do so, please make sure
to not just do that but to LEARN THOSE PROOFS.
(And don't forget, we will be treating TMs,
regarding the
sticky/nonsticky issue, in the way I mentioned above, which is NOT
the way Hop-Ull formulate TMs---this is our one point of departure
from their core model; except, for the purposes of this quiz, and
only for this one quiz, you may if you wish on one or more of the problems
stay totally in the Hop-Ull model; make SURE you at the start of your
answer explicitly state on the quiz whether you are in the pure Hop-Ull
model (sticky acceptance states) or whether you are in our course's
H-U but without sticky acceptance model).
And on the surprise quiz, which one(s) of Hop-Ull Theorems
7.1, 7.2, 7.3, 7.4, and 7.5 will you have to prove? Can you guess
that (or read my mind) and study extra-well the ones I'm most likely
to ask? Well... I'll in class probably have one of you
draw from the magic hat which of the theorem(s) you'll have to prove
on the quiz.
- Note 2 (090909/704pm). Reminder: Homework Set 1 is due
at 2PM (the very start of class) on 2009/9/16, and must be on time
(not late). Reminder: We often will go over homeworks in class (and not
put up solutions on the web), but HW 1 is an exception: We will not
go over HW 1 in class, but we will put up solutions on the web.
- Note 3 (090909/708pm). You'll probably get back next
class or the class after the quizzes from today's class.
(Typically, we'll try to---no promises or guarantees of this, and
this might not happen after long problem sets, but we'll try
to---as often as possible give back the quizzes and homeworks by
a week after they are handed in. And in the case of quizzes, you
might well find that many are handed back at the class right after
the quiz was taken.)
- Note 4 (090909/709pm).
Oh... let me touch quickly on the issue of whether it safe
to read the web site linearly (i.e., only read new stuff, and
assume that earlier stuff has not changed). Basically, the
answer is yes. That is, whenever I make a change that I think
might be interesting to you in an earlier part of this page, I'll
add a note letting you know what has changed. (On the other
hand, when I make very minor, unimportant changes---minor
editings things such as changing "has" to "have"---I'll do so
silently.)
Oh... an exception of course regards quizzes and posted quiz
answers and low/median/high numbers: Those always have slots
right on their day, which often start empty (such as "TBA" or "To
appear"), and as soon as those exist, they appear there but you
know already that that is where they will appear (but if we
CHANGE an answer set after we put up a first attempt, for
example, we will typically give a clear heads-up via an explicit
note alerting you to that, as THAT you might otherwise miss).
Another slight exception is I'll sometimes take the very last
note, if IT is what has to be revised, and change its time to
"revised at"... but I'll typically only do that if the change is
such a big one that it will jump off the page at you, and I won't
do it often at all (quite possibly, never, in fact).
- Note 5 (090909/710pm): On page 7 of my slides
you saw an example of a pairing function. Pairing functions
often are interesting. It isn't impossible, for example, that
if on a homework problem (hint, hint) multidimensional Turing
machine tapes are in play, that issues related to pairing functions
might be relevant.
By the way, if you want to see a bit more about pairing functions,
you can look at page 64 of the Rogers book on library reserve for the
course, or can look at---but be careful, they start the world at 1
rather than at 0, though you can work out for yourself how to change
their stuff to a start-at-0 world if you want to---page 169 of our
Hop-Ull book. There are some people who take pairing functions VERY
seriously, e.g., see brilliant SUNY-Buffalo professor Ken Regan's
Journal of Computer and System Sciences (Volume 45) paper,
"Minimum-Complexity Pairing Functions." Ken's mother has been quoted
as saying "How did I know Ken would become the pairing function maven?
Well, during his graduate complexity course, he was always looking at
the clock. Between us, I think he at first was enjoying--dare one say
a bit too much?--the natural bijection between (the finite domain)
{0,...,12} X {0,...,59} X {0,...,59} and (the finite domain)
{0,...,43199}. Before one could say `Boo!', he had started
going---one at a time---through the other bijections between those and
considering their aesthetic properties." (Disclaimer: The quote is
apocryphal.)
- Note 6 (090909/711pm): As a general point, let me mention
that if one is trying to on a homework problem invoke a result within
a proof, one MUST be utterly clear how the result is being invoked,
and the result had better match what it is being claimed to show. For
example, if Theorem 100.1 says "Each URCS professor weighs more than
100 pounds." Then if you are trying to prove that each URCS terminal
weighs more than 50 pounds, you cannot prove it like this: "Let A be a
URCS terminal. By Theorem 100.1 A weighs at most 100 pounds, and from
this it follows that A weights more than 50 pounds." The problem with
that proof is it used Theorem 100.1 as if it was about something it in
fact was not about. The same issues applies within your own proofs.
If you have proved a lemma and it does FOO (maybe it applies to all
cases where k>0), don't draw on it as if it was actually doing BAR
(for example, assuming it applies to all cases where k \geq 0).
- Note 7 (090909/712pm). By the way, I'll on this web
page freely use latex-isms to describe math things, e.g., "\geq" in
note 5 is the "great than or equal" sign. If you don't know latex (be
aware that all CS people researchers need to know latex, as CS
research papers are typically all written in that, but also) you can
just go to any book (on reserve for the course) or latex-teaching web
tutorial to figure out what the latex-isms mean (and to learn to
recognize them). (So if I write M_i(x), that means for example that i
is a subscript of M. that is another latex-ism. see the next note for
an example!)
- Note 8 (090909/712pm). By the way, in this course in
expressions (in my slides, for example) such as M_i(x) (side-comment
reminder: the "_" on this web page here that i just used is a
latex-ism... I'll often use latex source commands to symbolize
math/etc. on this web page), the argument there means the input and
this is a (slightly informal---because standing utterly alone M_i(x)
doesn't really have a direct meaning---but common and for our purposes
here ok) way of speaking of the action of M_i when it is run on input
x. For example, one might write "If M_7(s_7) accepts within 7 steps,
then..." and we'll take that as ok and having its natural reading.
- Note 9 (090909/717pm). Oh... you may notice that some
of the notes, having earlier times than this one, went up on the web
site at the same time. The reason is that when I build the web site
for a given day of the course, in order to make sure it is internally
consistent, I typically build it in a dummy location, look at it to
make sure the html doesn't come out haywire, and then move it to the
course homepage.
- Note 10 (090911/112pm). Very Important: An updated version
of the course information handout, version 2.00, just went up at the
top of this page. The change is the major one we discussed in class.
Namely, in light of the letters to faculty from the Dean and from the
directory of UHS, I as discussed in class and as a special
accommodation for this one instance of the course only am changing the
grading basis, and instead of dropping each student's lowest ten
chunks, I will drop each student's lowest sixteen chunks. There will
no drops beyond these (even for illnesses, as the sixteen chunks are
due to the possibility of illnesses, family crises, and all other good
and bad reasons for missing class). Since, in particular, you might
get the flu and/or the H1N1 ``swine'' flu, it would be very unwise
just to skip sixteen things at the start. Rather, the wise approach
is to do everything, so that when you have to miss classes to due a
flu or illness (and at the UR UHS web site you can find all the
information about what UHS asks you to do if you do get the flu---it
might be good to pre-read this, since when you're feeling miserable
you might not feel like reading it) or other reason, you'll have those
chunks available to cover that and be dropped. Also, remember that
even when sick, you can (and should) turn in your homeworks, namely,
be emailing them in (to "cs486" in the domain "cs.rochester.edu") as a
pdf file, and doing so no later than their deadline of course.
-
Session Topic:
Disjoint co-r.e. Sets Are Recursively Separable;
Undecidability via Many-One Reductions (Using Many-One Recursive
Reductions as a Tool for Proving Undecidability);
Turing Recursive Reductions (Another Tool for
Proving Undecidability).
In reviewing the quiz, proved that disjoint co-r.e. sets
are recursively separable
(i.e., we proved that
if $A$ is a coRE set and $B$ is a coRE set and $A \cap B =
\emptyset$ then there is a recursive set $C$ such that $A \subseteq C
\subseteq \overline{B}$);
as an application of our use-the-head-position-to-hold-info trick from
last class, defined the (quite possibly new) notion of
hibernating TMs, and sketched the proof that the class of
languages accepted by hibernating TMs is exactly the r.e.
sets (in the sketch, for which our model being, as it indeed is,
a 1-way infinite tape is indeed important (I don't remember
who ask about that in class, but one person did and
it was a very good question),
we had to be careful
regarding how we'd even find the rightmost nonblank cell
on the tape, at least in models where one can write blanks
to the tape);
many-one reductions;
many-one reductions as a tool for proving
undecidability;
used the tool to show a set
(having to do with machine-index and input pairs on which the
machine with that index halts on the given input) to be
undecidable, via providing a recursive many-one reduction from HP
to it;
Turing reductions; many-one reducibility for a pair of sets implies
Turing reducibility, but sometimes not the other way around;
Turing reductions as a tool for proving undecidability---if A
recursively Turing reduces to HP, then A is undecidable;
proved
that the index set L' = {i | L(M_i) = \emptyset} is coRE but
not recursive (or RE);
proved that the
index set L'' = {i | L(M_i) = \Sigma^\Star} is not recursive.
- Nonquiz Exercise
(a) Prove: There exists an infinite
set A \subseteq {0,1}^* such that A does not have an
infinite r.e. subset (in technical terminology, you're proving that
there is an RE-immune set).
(b) Consider the following plan on how to
that exercise: "We will show that \overline{HP} contains no
infinite r.e. subset." Prove that this approach is hopeless.
(Recall that our enumeration of TMs, M_1, M_2, ..., is that
of Hop-Ull.) (Note: I did part (b) in class today, but
still, please do it also, so that you know that you know it.
It is one thing to listen to me sketch a proof and for it to sound
right... but it is another thing for you to understand something
so well that YOU can write down a proof for it.)
So, the previous paragraph gives you a
"non-quiz
exercise."
What is this "nonquiz exercise"? Well, it is something that
could have appeared on the quiz today, except the quiz today
already had lots of stuff on it.
But here is how to approach it.
Please
try to put about two hours into this nonquiz
exercise before next class. If you
do solve it within that time---GREAT, and congratulations for
having both learned a certain proof we did in the class
before this one (namely, the diagonalization proof)
and being able to
very flexibly adapt it to a new situation! If you don't solve it, don't
worry, as it is pretty hard to see
and we will go over it probably next
class---but your having worked for two hours on it will make the
solution MUCH clearer to you when it is presented.
NOTE: I will not collect this in class and you are not being
graded on this---well, at least not in class next class, though
this or similar questions could appear on future quizzes/homeworks/etc.
And, as usual, there still could be a quiz next class (but if so,
it will not be on this problem).
- Quiz. Here.
- Quiz Answers. Here.
- Quiz Statistics. Low/median/high = 0/0/10 (out of 20).
- Homework Set 2 (due 2:00PM, September 23).
These problems
are 10 points each.
Bov-Cre is our Bov-Cre textbook.
-
(1) Bov-Cre problem 2.15.
-
(2) Bov-Cre problem 2.19.
-
(3) Bov-Cre problem 2.20.
-
(4) *Disprove* the claim made in Bov-Cre problem 2.22.
(Note: ``admits'' is, they way they are using it,
a synonym for ``has.'') Then fix the
loophole that Bov-Cre left in the natural way, and then solve
the thus-fixed problem.
-
(5) Define the concatenation of two languages A and B as AB = { xy | x \in A, y
\in B }.
Show that there exist two undecidable languages A and B such that AB is decidable.
-
(6) We will say that an RE language is inherently total if every
Turing machine that accepts it is total. List all RE languages over the
alphabet \Sigma = {0,1} that are inherently total. For each language
on your list prove that it is inherently total. For each RE language
over \Sigma that is not on your list prove that it is not inherently
total.
(Terminology reminder: A TM is said to be "total" exactly if it halts
on each input.)
-
(7) Show, via a many one reduction from the halting problem, that
L = { i | there exists
a string x such that M_i(x) halts} is
undecidable. (Note that it says "halts.")
-
(8) Show, via a many one reduction from the halting problem (HP,
which recall for us is always HP = {x | M_x(x) accepts}), that
L = { i | L(M_i) contains at least 486 strings and at most 2009 strings}
is undecidable.
-
(9) Show, via a many one reduction from \overline{HP} (i.e., from
the complement of the halting problem), that
L = { i | L(M_i) contains at least 486 strings and at most 2009 strings}
is
undecidable.
(NOTE: Based on what we'll learn in class next class, this problem
shows that L is not co-r.e. and the previous problem shows
that L is not r.e.)
- Homework Set 2 Statistics. low/median/high = 0/29.5/88 (out of 90).
- Note 1 (090916/709pm). Homework Set 2 is available
above. (I usually won't include pointer notes like this, but since
it is the second set, I'm doing it this time.)
- Note 2 (090916/714pm). As to RE/r.e./recursively
enumerable, let me warn you that the definitions in the exercises
(ones you are not yet assigned) of Bov-Cre define recursively
enumerable in a different way than Hop-Ull and I did (though they
can be proven to yield the same class of languages as each other).
[The issue here is that the concept is very robust and has many
different equivalent ways of defining it. Also, there is interplay
between locking into the history versus being in sync with certain
books.]
Also, let me warn you that my slides and
I freely overload "RE" and use it both
as a synonym for "recursively enumerable" (e.g., in "Let B
be an RE set") and as meaning {A | A is a recursively
enumerable set}, i.e., the class of all sets
that are recursively enumerable (e.g., in the latex
expression "Let $B \in {\rm RE}$"). The same holds
regarding coRE (for its different meaning).
But when I use r.e. or co-r.e. or recursively enumerable
I'll always use it in the adjectival sense (e.g., "If
A is an recursively enumerable set").
- Note 3 (090916/724pm). I just wanted to come back to
the issue of whether the r.e. sets all have to be over the alphabet
{0,1}. The Hop-Ull answer is no. However, in proofs we'll sometime
act as if the answer is yes (which isn't an utterly awful answer).
For example, note that, at least on its surface, the proof I gave one
class ago about why \overline{HP} is not r.e. seemed to assume all
the r.e. sets are over the alphabet {0,1}. (But, if you really care a
lot about this issue of richness of alphabets, note the point of the
first paragraph of Section 8.3. However, it probably is best not to
get lost in this technical side issue.)
Another good place to look to get insight into why alphabets are
often boring (even when doing complexity---where for this it is harder
to be boring, e.g., alphabet-size 1 vs. alphabet-size greater-than-1
is a huge deal in the complexity world, but in most computability
settings isn't an utterly huge deal) is on pages 39-40 of Bov-Cre.
- Note 4 (090916/726pm). As mentioned before, we usually
will not put up homework answers but rather will usually go over
homework sets in class. But homework set 1 is an exception: we'll for
that simply put up answers. They now appear above, below homework 1
within the Sept. 9 part of the web page. Reminder: But for all
homework sets except set 1 (so, for example, for Homework Set 2!!),
come into class with your original answers to hand in,
and a photostat of your answers so you have that when
we go over the answers (it may be very helpful to you if you are called
on to put up an answer).
- Note 5 (090916/747pm). If you did poorly on the quiz
today or are feeling overwhelmed, let me mention a bunch of things.
On one hand, we've covered in the past two lectures a massive amount
of material (trying to at least go quick through it, since many of you
didn't have an undergraduate course that covered it), and while doing
so, we've tried to do so in a way that gives you more contact with the
architecture of the study of undecidability than you'd typically get
in an undergraduate course (which might stress the tools and how why
they hold) So things indeed have been coming quickly. On the other
hand, please do keep in mind the following things. You should after
each class review and study on your own or with class colleagues the
material of that class session. It is not at all shocking if after
class, some of the hard proofs or claims (or definitions) are not
clear. But if so, the wrong thing is to ignore that. The right thing
to do is spend some timing looking at the slides, at your notes from
class, and at any relevant reading, alone or together with class
colleagues. If that doesn't make things clearer, please keep in mind
the office hours: The TA has office hours M/T/W/F (and teaches an
optional review session each Thursday for this course) and I have
office hours after each of our class meetings, and those are there so
we can help you.
- Note 6 (090916/756pm). The second review session is
tomorrow, Sept. 17, at 450PM in CSB 632. It is optional, but
attending these is probably a VERY good idea---you'll at the various
review sessions potentially see such things as, for example, proofs
reviews, see new exercises, have practice using tools and techniques,
etc.
- Note 7 (090916/1009pm). Just to be clear (the course
info document was clear that homework had to be handed in on time to
get credit, and that we have and will followed, but it didn't speak to
whether homework had to be in on time to get gone over carefully, so
let me be clear on what will hold from now on regarding that): To have
your homework graded and get credit for it, you must hand it in on
time. (That is, if you hand it in late, the only thing we'll write on
it is a zero. If you want the value of the TA's feedback, and you
certainly should, then you must please follow the rules of the course
and hand it in on time, as required. Of course, even in cases when
you don't hand in a homework, you can see the TA or me during our
office hours to chat about your solution ideas. But you won't be
getting red-pen feedback on the set itself on late sets.)
- Note 8 (090917/1142pm). Please before Monday's class
check and see whether Oct. 19 is a fatal conflict for you for a date
for our midterm I. (It is scheduled for Oct. 21, and it will stay there
unless no one has a fatal conflict on Oct. 19. However, for one
student, Oct. 21 is an impossible conflict, and I went through the
course structure and material timing, and given where we now are, it
will be possible to have midterm I on Oct. 19 in terms of course
timing, and so if 10/21 is not a fatal conflict for anyone, we should
move it there. So, I'll ask in class on Monday regarding 10/19 and
conflicts.)
- Note 9 (090917/1146pm). Could there be a surprise quiz
next class? That is *very* possible. In particular, I'd suggest you
study all of the material so far, so that you learn the material (but
as a side effect of learning it, you might also be better prepared for
the surprise quiz).
- Note 10 (0909d207/1243pm). I updated the course
information document from version 2.00 to version 2.10 to be clearer
about grades/grading, and in particular to be clear about
the things discussed in Note 7 above.
-
Session Topic: A More Sophisticated Use of Diagonalization
(Which Can Sometimes even Be Off the Diagonal), and
Proving Non-RE-ness and Non-coRE-ness (Via Many-One Recursive
Reductions).
Any set that many-one
reduces to an r.e. (respectively co-r.e., recursive) set is
itself r.e. (respectively, co-r.e. (I didn't explicitly
mention this in class, but it is clearly true from the
r.e. case plus the definition of co-r.e.), recursive);
that fact, which we stated and proved, gives a
tool that can be used to prove sets non-RE and
non-coRE;
as an example of how to use the new tool, we used it
to
prove that the index set L'' = {i | L(M_i) = \Sigma^\star} is
not r.e., and that L'' is also not co-r.e., and also to
show that {i | L(M_i) is infinite} is neither r.e. nor
co-r.e.;
diagonalization revisited; using the core idea of the
diagonalization we did last earlier,
but in a more flexible and (again)
very
nonconstructible way, we showed that there exists an infinite set
that has no infinite r.e. subsets (in the lingo: there is a set
that is RE-immune).
- Quiz. Here.
- Quiz Answers. Here.
- Quiz Statistics. Low/median/high = 15/21.5/38 (out of 40).
Note: Everyone was given 10 points (full points) on the "HP reduces to B"
question, since I had a "p" superscript on the reduction, which
is just wrong and so was confusing. (But for the future, if something
on a problem is wrong, please note that, explain why it is wrong,
and explain what you have treated it as being.)
- Individual Meeting. I'd like to have a ten-minute chat
with each of you next week about how you are doing so far and to
find if you have any questions about the material so far. The
sign-up sheet was passed around today. Just as a reminder, here
are the meeting times for each person (using the same form/amount of
the person's name as was written on the sign-up form):
Monday, Sept. 28: 320 = Elif; 330 = Anand; 340 = William; 350 = Young Chol;
400 = Maryam; 410 = Julia; 420 = Juan Chen; 430 = Xu Han;
440 = Chris Clingerman; 450 = Li Lu.
- Midterm I Date. Midterm I's will be
Monday, October 19th. (I've adjusted all references to
midterm I above to refer to that date.)
- Note 1 (090921/654pm).
This is not in any way required reading, but
let me mention that the library owns
(they are on reserve for our course)
some books by Polya that you might enjoy:
``How to solve it; a new aspect of mathematical method''
(over 1 million copies sold; really)
and
``Mathematical discovery; on understanding, learning,
and teaching problem solving.''
The former is more of a popular-reading book
than the latter 2-volume set.
These books will probably directly solve
for you a total of zero of this course's
problems; there is no magic bullet or
globally correct algorithm for solving problems and doing
creative research. But thinking about how
one does---and learns to do---such things is itself
interesting,
and perhaps as a long-term thing is of
real value.
Or you can try some
one-word semi-answer. My favorite
is: ``Osmosis!''
That is, find a
creative advisor, and see over and over
how he or she
magically solves things, and try to find out
via observation
just what his or her approach/flavor/method
is to posing, refining, and solving problems.
And start trying that yourself. But, better,
read these books, and so start the
process of learning and thinking about
learning, thinking, discovering, and solving.
Here are some wonderful quotes from ``How to Solve It'':
-
If there is a problem you can't solve, then there is an easier problem you can't solve: find it.
-
If you have to prove a theorem, do not rush. First of all, understand fully what the theorem says, try to see clearly what it
means. Then check the theorem; it could be false. Examine the consequences, verify as many particular instances as are
needed to convince yourself of the truth. When you have satisfied yourself that the theorem is true, you can start proving it.
-
The first rule of discovery is to have brains and good luck. The second rule of discovery is to sit tight and wait till you get a
bright idea.
-
A great discovery solves a great problem but there is a grain of discovery in any problem.
- Note 2 (090921/659pm).
I've mentioned this before, but let me just repeat: This web
page is quite central to the course. So, I urge you to
look at it often. (Indeed, things that appear here---for example
as ``Notes''---sometimes telegraph information about whether
there will be a surprise quiz, or hint at what may be on
surprise quizzes, or etc. So, the more often you look, the more
likely you are to catch such hints---which at times might
even appear extremely close to the time of the item (quiz/homework/etc.)
in question.)
- Note 3 (090921/659pm). Reminder: I have office hours
from immediately after each of class session through 4pm on both
Monday and Wednesday, and they will be in the classroom---that is,
if people come up with very short questions right after class I'll
usually answer them right there in the room---and my office.
Adam has office hours
MW 3:15PM--4:15PM, Tu 4:50PM--5:50PM, and F 10:00AM--11:00AM
(all in CSB 724,
except on Mondays and
Wednesdays, in CSB 632 and/or CSB 724), and teaches a (very helpful,
we hope)
Review Session for the course 450pm-550pm on Thursdays in CSB 632.
(But don't feel limited to
the just-mentioned hours for him or me. Any time you catch me or
Adam around, we'll in general be happy to discuss the course,
theory, etc.)
- Note 4 (090921/659pm). The Amazing Seer Lane Reads Your
Complexity Horoscope: Your upcoming classes
(surely at least one of the next two classes) may well hold a
surprise quiz (or nonquiz exercise). Good preparation is always a
wise course of action. If one appreciates the depth and texture of
one's field, one will be better in all one undertakes. If you
(yes, YOU) become a multi-millionaire, then you will donate a new
CS Building to URCS---complete of course with a lavish "Theory
Wing." (End of horoscope.)
Put more explicitly: You should always review very carefully the
many theorems, proofs, and techniques we've seen this term.
For example, we've proven
that \overline{HP} is not r.e., we've seen that diagonalization
can even go beyond that and keep certain infinite sets from
having any infinite r.e. subsets, and we've seen how to prove
sets nonrecursive and non-RE and non-coRE.
And you
should not merely
memorize these proofs/techniques,
but should even try to learn their *idea*(s), very well, so that
you can generalize, vary, and apply them.
- Note 5 (090921/703pm). A reminder, quoting from the
course info handout: "Homeworks must be submitted on time; late
homeworks get no credit." Please keep in mind also that, as stated
on the handout, "As a bow to sicknesses, broken cars, and other
compelling excuses, each 486 student will have his or her ten
[SPECIAL NOTE FOR THIS TERM: it will be sixteen rather than
ten this term!]
lowest chunks dropped (but no more, even with good excuses, unless
you have a letter from a convincing Dean)..."
Now, if for some reason (sickness, family crisis, etc.) you
cannot be around to turn in a homework (but can have it done before
the deadline), let me mention that you should try to arrange to
get the homework to the TA in a way that is CERTIFIABLY
(i.e., in a way
that made the arrival time self-evidence so the TA knew with
certainty that it had arrived on time) arrives no later than the due
day/time. so ideal is to email it as pdf (BEFORE the due
time).
alternatively, if you are home sick, it is ok to seal
your homework in an envelope and give it to someone else, such as a
classmate, to deliver to the TA no later than the due day/time (but
of course if that person fails in his/her task, then your homework
will be late and so will get a zero and not be graded or marked up).
- Note 6 (090921/707pm).
Important: The homeworks are a very important part of the learning
of this course. Very often, we'll learn something by proving it
on the homeworks. (And, even for material covered in class,
you'll understand it far more deeply when you get ``hands-on''
with it, via having to actually use it on homework sets.) So,
please (continue to) start the homeworks early, and work very hard on
them. (In particular, this is not a course in which one can start
the homeworks a few hours before their due times. Sometimes homework
problems are such that you'll need to ponder them quite a
bit---perhaps playing around with multiple lines of
attack---before you find a path that will solve them. Ok, ok,
HW Set 2 is perhaps
not a killer set, but many sets will have problems
that are challenging and require much thought.)
- Note 7 (090921/712pm). Oh... there is often confusion
regarding what the latex \subset symbol means. Some people use it to
mean strict subset, and some use it to mean \subseteq. Let us keep
this simple: Absolutely no one in this course should ever write (on
our course stuff) \subset---by hand or in latex. If you mean the
nonstrict version, write the \subseteq character. if you mean a
strict subset, write the appropriate symbol for that (the symbol that
looks like \subseteq but with a tiny slash through the bottom dash of
that symbol). (Again, \subset for some people means one and for some
means the other; that is why we will never use it---it is ambiguous.)
- Note 8 (090921/1126pm, revised 090922/1228am). I
updated the course info handout to version 2.20. It removes a slight
conflict between email and writing regarding regrades. By the way,
the general state on regrades is, as I mentioned earlier in
the term, if you got
genuinely misgraded, it is natural to ask for a regrade. But on an
issue of, say, trying to get one or two more points on a partially
correct answer regarding judgment as to how many points it deserved,
it probably is unwise to ask for a regrade, especially
as TAs are often already remarkably generous... plus, on regarding
scores can go up or can go down; probably better in such a case is to
simply chat with the TA to try to understand the grading, and what he
was worried about, and what different approach to the
answer/notation/whatever would be viewed as better. (By the way, my own
grading is very careful, and I expect answers to be crisp, clear, and
correct, so if you ask for a re-regrade, it is possible that your
score could go up but it is also possible that your score could
drop.)
- Note 9 (090922/313pm). As mentioned above under
quiz statistics:
Everyone was given 10 points (full points) on the "HP reduces to B"
question, since I had a "p" superscript on the reduction, which
is just wrong and so was confusing. (But for the future, if something
on a problem is wrong, please note that, explain why it is wrong,
and explain what you have treated it as being.)
-
Session Topic: Closure Properties. Went over the answers
to all of Homework Set 2, including many closure properties of the
r.e. sets and of the recursive sets; in particular, we saw that
the recursive sets are closed under union, intersection and
concatenation and that the r.e. sets are closed under union and
intersection; we saw (by some energetic dovetailing; this problem
was not on the homework) that the r.e. sets are closed under
concatenation; we saw that the recursive sets are not closed under
concatenation; we saw some examples of reductions.
- Quiz. Here.
- Quiz Answers. Here.
- Quiz Statistics. Low/median/high = 0/10/20 (out of 20).
- The Quiz, Question 2. Question 2 of the quiz didn't go
well... at all. Remember, THIS is the definition of \leq_m:
We say that A \leq_m B exactly if there is a recursive
function \sigma such that (\forall x )[x \in A
if and only if \sigma(x) \in B]. (The universe of x is typically
\Sigma^\star, but in some cases we may treat it as the natural
numbers; one can go back and forth via the standard bijection
between \Sigma^\star and the natural numbers.)
Now, in many of our examples,
sigma(x) was outputting the index of a machine. But the definition
doesn't apply to only that case. Question 2 was a case, for example,
that is very different.
Let me give you an example to make
the non-machine-index class clear. And to make this example
simple, we'll do it over sets of natural numbers.
Let EVEN = {n | n is even}.
Let ODD = {n | n is odd}.
I claim that EVEN \leq_m ODD, via the reduction \sigma(n) = n+1.
And I claim that ODD \leq_m EVEN, via the very same
reduction \sigma(n) = n+1. Please look at these carefully to
make sure you see why this is so!
From looking at the answers to the second quiz question
today, and from the reduction answers people put up in class,
I think that most people probably will benefit quite a bit from
more (lots more) practice on
many-one reductions, so please do use this weekend to master them. Your
homework set 3 (below!)
will give you various problems requiring reductions.
And of course many of the books I've put on reserve for the course
(and also many textbooks that are just on the shelves in the library)
have examples of proofs of undecidability.
(For example, the
book "Introduction to languages and the theory of computation,"
by John C. Martin, which is on reserve for our course at the library, is a book
that some people have in the past felt was a good on this.)
- Homework Set 3 (due 2PM, September 30).
Bov-Cre again is our Bov-Cre textbook.
Hop-Ull is the *first edition* (the 1979 edition) of the
book "Introduction to Automata Theory, Languages, and Computation"
(be careful---they have coauthored
a different book that is closely related, but I don't
mean that other book, and I also don't mean
the HMU second edition).
Bov-Cre and Hop-Ull (multiple
editions, but these problems
are from the first edition) are
on reserve for our course at Carlson Library. Warning: Some
of these problems are more than a bit challenging,
and there are unusually
many problems, so please start early.
- Homework Set 3 Statistics. Low/median/high = 0/63.5/89 (out of 120).
- Homework 3 (Optional) Review Session. There will be a
homework 3 revision session on Wednesday, September 30 (in room 632)
starting at
5:00PM
(and lasting as long as we need---maybe around 60-90 minutes,
I'd guess/hope---to have *you* (or me, on any that none of
you could do), to
go over each problem's solution, so please do
bring copies of your Homework 3 since you'll hand the originals
in in class and so won't have your original at the
review session). This session is optional but I'd
encourage each of you to attend it (or have a friend-from-class attend it and
convey the solutions to you) unless you're confident in each of your
solutions on this set. (Note: We won't have many such optional
sessions---we'll usually go over homeworks right in class. But this
particularly hard/long set is (I hope!) worth this special session, so
that everyone understands it well---because if you don't, moving
beyond it could be challenging. Adam won't be conducting this
one, although with luck he'll be there too, but I'll try to conduct it,
and it will go much the way today's homework review session went... except
there are more problems on Homework Set 3, and some are somewhat hard.)
- One-On-One Meeting Day Reminder. Our one-on-one meetings
will be this coming Monday, September 28. Please come in
to the meeting well brushed up on reductions (but also, at the
meeting, we'll try to do an example together, and I'll try to
help you on it if you have problems). You can find the times slots
and which is yours listed under the 9/21 class entry.
- Note 1 (090923/805pm). Homework Set 3 is up, above. It
probably is nontrivially more challenging than Homework Set 2, so
please do start it early enough to have time to give these problems
enough time. (It is based on things we already know, not on
what we'll cover next class, so using the weekend to work on
it is a good idea.)
- Note 2 (090923/816pm). Oh... I should mention that
sometimes (though not wildly often) I put things in latex-isms in this
html page (e.g., the statements of HW Set 3 problem 1 is very
latex-y),
and sometimes I just write stuff that look ok on the page (e.g., the
last sentence of problem 3 of HW Set 3 just looks like what I mean... if
one ran that through latex it would eat the brackets of course, but
that is not what I mean), and sometimes, there is some mixing and
matching (e.g., HW Set 3's problem 9 uses latex-isms locally for
subscripts, but doesn't have latex-y dollar signs and doesn't write \{
and \}, so it is a mix of text and latex-isms). However, you should
be able to tell which is which from context easily.
- Note 3 (090924/1023am). The staff just assigned us a
room for the homework review session on Wednesday, Sept. 30. The room
will be CSB 632 (our regular classroom), and the session will start at
5PM. It is *optional* (but I do recommend that, unless you're
very confident that you nailed HW Set 3, you either attend it or share
the notes made by someone who attended it, since we'll not put up
answers to set 3 or go over it in class---although of course your set
3 will be marked and given back to you---but rather will go over it
here). I've above on this web page in the place where the review
session is mentioned gone back and substituted in the room number so
that that entry won't be confusing.
- Note 4 (090925/1013am). Reminder: I doubt that in most
cases we'll use it, as we'll be chatting or quickly working on a
reduction, but please *make sure* to bring to our one-on-one Monday
meeting a folder containing all the graded things that were returned
to you in 486 so far this term, and also containing a copy of the
problem set (Set 2) that you just handed in two days ago.
- Note 5 (090926/1135pm). There will be a quiz on Monday.
Please come in having carefully reviewed the material of the course so
far. Among the things that could be on the quiz are reductions,
dovetailing, and diagonalization (probably not all three of those all
on this one quiz, of course).
- Session Topic:
The Kleene Hierarchy and the Tarski-Kuratowski Algorithm.
Reviewed in words the definition of the classes Sigma_k,
i.e., the levels of the Arithmetic Hierarchy (the Kleene Hierarchy)
and of the classes Pi_k; the oracle definition versus the quantifier
characterization of the levels of the arithmetic hierarchy; brief
description
of why (for the case of Sigma_2) they are equivalent,
including a definition of k-simulations; a universal set
for Sigma_2^0 (don't be freaked by the zero---we've been suppressing
it in class as implicit, so it doesn't mean anything important for
us);
hierarchy structure of the Kleene Hierarchy;
some examples of natural sets in different levels;
the
Tarski-Kuratowski algorithm (or... counting quantifier alternations
gives upper bounds; the term "Tarski-Kuratowski Algorithm"
refers to the process of unwinding down to a
bunch of alternating quantifiers on top of a recursive predicate...
it isn't really at all an utterly clean,
mechanical "algorithm" in the standard sense, but nonetheless, it is
routinely described as the "Tarski-Kuratowski Algorithm");
mentioned
that each set in Sigma_2^0 \cap Pi_2^0 is recursive in
the halting problem (note: one proves this by relativizing one of
our favorite earlier proofs);
examples of using the
Tarski-Kuratowski Algorithm, in particular, we showed
that {i | L(M_i) is finite} is in Sigma_2^0,
that {i | L(M_i) is infinite} is in Pi_2^0,
and
that {i | L(M_i) is cofinite} is in Sigma_3^0;
showed a quick very-green chart showing a list of
where certain things can be proven to fall (and we'll
on the homework do various examples);
on homework set 3, due today, you proved such things
as showing that there
exists a set that is RE-bi-immune (i.e., a set such
that neither the set nor its complement has an
infinite RE subset).
- Next Class and Beyond.
Due to Univ. of Rochester's Fall Break, there is no class on
10/5.
We'll spend next class
(10/7) going
over Homework Set 4.
We'll devote 10/12 to (going over any problems from Set 4
that we did not get to on 10/7, and then)
reviewing and doing examples of the various techniques
we've covered in this part of the term (including both the
earlier stuff and the stuff we just did this class), that is, it
will be a overview/review session for this part of the course.
10/14
will be the start of the
second half of the course: the start of our study of complexity
theory.
Midterm I (covering the first half of the course) will be 10/19.
- Reading Reminder. Please keep in mind to do the
reading from Rogers that (in the web area of last class I asked
you to please do right after the current class). That reading
regards the Arithmetic Hierarchy and the Tarski-Kuratowski
Algorithm.
- Reading (due 2009/10/14/159pm)
This reading is on complexity theory.
Read carefully in our Bov-Cre book from page 69 through
the end of page 78, and learn that material (and in Hop-Ull
you may find parts of chapter 13 helpful in doing the
forthcoming Homework Set 5
and understanding the BC reading). Also, please
re-read the Preface and skim the first three chapters
of our Hem-Ogi book, and also skim in our Hem-Ogi book
all sections of Appendix A and
Appendix B that relate to classes or reductions mentioned in
those chapters (and I may well
assign some of these "skimmed"
pages again
for detailed, close readings; this time, you're doing a skim/overview.)
- Homework Set 3 (Optional)
Review Session. It will be today at 5PM,
in room CSB 632.
In it, will go over homework set 3, which covered
many results and items, including:
How to create an f(i) such that no three
in a row of the machine names it outputs are machines
that all accept the same language;
there exists a set that is RE-bi-immune;
proved that there
exist two disjoint r.e. sets that are not recursively separable;
many
concrete examples of reductions between sets; the r.e. sets
are closed under Kleene star.
- Midterm I Reminder. The midterm will be in class on
October 19, 2PM-315PM. It will be worth many points (in particular,
it will be worth 280 points). Please
study hard and well. Recall: ``No makeups. No exceptions...
The first midterm [is] closed-book... The first midterm is
closed notes, except for the one sheet of [handwritten]
cram-notes prepared by yourself as discussed elsewhere.''
- Homework Set 4
(due 2009/10/7/200pm).
-
(1) [10 points] Prove, via many-one reducing from \overline{HP} to
L, that L is not r.e., where L = \{ i | (\exists x \in \Sigma^*)
(\exists y \in \Sigma^*) [ x \in L(M_i) if and only if
y \not\in L(M_i)]\}.
-
(2) [10 points] Give a Turing reducing from HP to
L, where L = \{ \langle w, x,y,z \rangle |
|| \{w,x,y,z\} \cap HP || = 2 \}. (Note: For a finite set B, ||B||
will denote the cardinality of B. And, here, \langle a,b,c,d \rangle
is just a nice, fixed, recursive 4-argument ``pairing'' function.)
- (3) [10 points]
For each of the following sets, either use Rice's Theorem
to argue that it is undecidable, or explain why Rice's Theorem
does not apply to it. (a) { x | the string x contains at least
486 characters}. (b) { i | \emptyset \neq L(M_i) \neq \Sigma^\star}.
(c) { i | On input 010101 machine M_i runs enters at least 14 times
the 17th
state mentioned in its program}.
- (4) [10 points] Prove (by giving a many-one reduction from \overline{HP}
to L) that L is not RE, where L = {i | there are at most 486
elements in L(M_i)}.
- (5) [10 points] Prove that { i | L(M_i) \neq \emptyset} is in Sigma_1.
- (6) [10 points] Prove that { \langle i , j \rangle | L(M_i)=L(M_j}
is in Pi_2.
- (7) [10 points] Prove that {i | L(M_i) is a context-free
language} is in Sigma_3.
- (8) [10 points]
In this problem we will consider a new type of enumerating
Turing machines. Our new machines, called Rochester-enumerators,
can enumerate strings like regular enumerators (via having
the string on their special enumeration tape and entering
a special "enumeration attempt" state), but they can
also attempt to retract strings (via having
the string on their special enumeration tape and entering
the special "retraction attempt" state).
Let E be a Rochester-enumerator. We say that a string x is
Rochester-enumerated by E if it both holds that
(a) in at least one point in the computation
of E, E enumerates x, and
(b) after E enumerates x for the first
time, it never retracts it.
(So, for example,
if a machine retracts foo, enumerates foo, and retracts foo,
then foo is by our
definition not Rochester-enumerated by E.
If a machine retracts foo and then enumerates foo and then
never again retracts it, then foo is by our definition Rochester-enumerated
by E.)
L(E) is the set of all strings
Rochester-enumerated by E. We say that language L is
Rochester-enumerable if there exists a Rochester-enumerator
E such that L=L(E).
Prove that
All coRE sets over the alphabet {0,1} are Rochester-enumerable sets.
And let me mention (I'm not asking you to prove it, but of course,
if you might like to think about it; you'll after some thought
perhaps see that it does hold and how to prove it, and it is
very satisfying to have a complete characterization for the
power of a model)
that one can pinpoint far more precisely
the power of this model, namely, the following holds (making it
clear that these sets are the recursion-theoretic analogues of
the complexity-theoretic notion of the class DP):
The set of all Rochester-enumerable sets over the alphabet
{0,1} is equal to {A - B | A and
B are r.e. sets over the alphabet {0,1}}.
- (9) [10 points]
Prove that A many-one reduces to B and B many-one
reduces to A, where
A = { \langle i , j \rangle | L(M_i) = L(M_j)} and
B = { i | L(M_i) is infinite}.
- (10) [10 points]
Using (twice) the
3-part version of Rice's Theorem, prove
that {i | L(M_i) has at least 1000 elements and at most 2000
elements} is neither RE nor coRE.
- (11) [10 points]
Consider L = {i | there exists a string x such that M_i(x0)
and M_i(x1) both run forever}. Prove that L is in
Sigma_2 - Sigma_1.
- Homework Set 4 Statistics. Low/median/high = 0/65.5/92 (out of 110).
- A (Tricky!) Tarski-Kuratowski Example.
In class, I mentioned that
{ i#j | L(M_i^{L(M_j)}) is Sigma_2-complete (i.e., $\leq_m$-complete
for Sigma_2)} is in (not just Pi_5 but even) Sigma_4.
Instead of doing that (as it is so involved that the details might
overwhelm the point), let me rather present a simpler
but closely related case.
In particular, I'd suggest you work on this problem: Show
that {i | L(M_i) is RE-complete (i.e., $\leq_m$-complete
for RE)} is in Sigma_3.
I think you'll find it very instructive to
apply Tarski-Kuratowski to it carefully and completely.
You should be able to show the intermediate step displayed
below,
and from it you should be able to reasonably easily determine
that the problem is in Sigma_3 (this is a problem that
if one were not careful one might merely classify as being
in Pi_4, but the approach below shows that it in fact is
in Sigma_3!):
{i| L(M_i) is RE-complete} =
{i |
(\exists h)
(\forall x)
[ (\exists t)[M_h(x) halts with some output within t steps]
AND
[(\exists t')[ M_J(x) accepts within t' steps]
<==>
(\exists t',v)[ (M_h(x) halts with output v within t' steps) AND
( M_i(v) accepts within t' steps)]
]
]}, *where M_J is some fixed machine accepting the halting
problem*.
- Note 1 (090930/749pm). If you have been having problems
with reductions (or anything else), please don't wait until right
before the midterm to address that. Rather, please right away (e.g.,
this week) see
Adam
and spend some time working on some examples with
him. (And of course, also review [and by review I don't mean just
swish your eyes over them and nod... I mean solve each and make sure
you are comfortable and confident doing so, and if not, keep reviewing
until you are] all the examples we've had, meet with classmates and
make up new examples for each other, etc., etc.)
- Note 2 (090930/810pm). Please
plan to
study very hard! You do?
Good plan!!
I'd suggest that one component
of a good approach to preparing for the Midterm I
exam is probably to come in knowing
every homework/quiz problem/solution, all of the class lecture and
reading materials, and generally speaking all of the course
stuff---and, just memorizing it all itself isn't enough... on the
test, you'll have to in some (ok, most, probably) places show you have
not merely memorized without understanding, but rather that you have
learned the *techniques* and approaches so well that you can solve
problems that you've never seen before (by choosing, employing,
combining, extending, etc. as needed the techniques you've learned).
Again, I'd stress that your classmates are wonderful resources (to
study with and so on). And let me remind you that
Adam
has
office hours every weekday (except Thursday, on which he
has a review session, which is also usually good for asking questions),
and that if
you not comfortable with any of this material, for goodness's sake use
those (if you are worried that it is embarrassing to show up for
office hours, consider that it probably is vastly more problematic to
do very poorly on the 280-point Midterm I exam, and that showing up for office
hours is a very wise path toward becoming comfortable and confident
regarding the knowledge/techniques/etc. that will be important in
doing well on the exam). [I realize that many of you are--or will
soon be---studying very hard, and have, if you feel they would be
helpful, been using office hours. Good for you!]
But from some of the
answers on
recent things,
such as some quizzes and the homework,
I'm worried that some---perhaps even
many---may still have need for substantial studying/doing
exercises/working old problems/etc.
So please do study hard and well.
Thanks!
- Note 3 (090930/813pm).
Regarding the reading in the book
by Rogers, that book is on reserve for this course in the library (on
the second floor of our building). (So, to take it out, it will NOT
be on the shelves, but rather it is kept behind the desk, and they
will only let you take it out for relatively short periods of
time---probably two hours at a time, or at least that is what I just
asked them to re-set the loan time to. Of course, one can retake it
for another two hours if someone else isn't by then already in line
for it. Please don't keep the book out so long or so repeatedly
that your class colleagues can't get to the book.)
- Note 4 (090930/828pm). Oh... by the way, please study hard
for next class's surprise (!?) quiz. It will be worth at least 20
points, and will have questions on at least two of these three topics:
proving things hard by reductions, diagonalization, and
Tarski-Kuratowski.
- Note 5 (090930/830pm). Please don't miss note 4
(immediately above this one). Also, let me mention that there will be
no office hours on Oct. 5 (it is during UR's curiously short Fall
Break). And also, let me mention that there will be (as there is
every Thursday) a review session tomorrow.
- Note 6 (091002/1108pm). Yesterday's review session went
over some very nice examples of reductions: proving {i | L(M_i) is
infinite} \leq_m { \langle a,b \rangle | L(M_a) \subseteq L(M_b) } and
proving { \langle a,b \rangle | L(M_a) \subseteq L(M_b) } \leq_m {i |
L(M_i) is infinite}. And it also went over some other reductions, and
also looked at the quantifier structure (think Tarski-Kuratowski!) of
the sets just mentioned. Let me stress again that these review
sessions, although not required, will probably be *very* helpful to
you, and I'd urge all of you (unless you are completely in command of
the material) to attend them if you don't have a conflicting meeting.