Instructor: Lane A. Hemaspaandra
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.
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---though the "assignments" page at that same web site seems to actually give section numbers) from the MTH150 web site's course outline.
As a side effect of the above, let me mention that if there is a surprise quiz this Monday, 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.
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.
All the disclaimers I mentioned in class hold---no promises of any sort are made about these xeroxes (some slides may be missing that I will use, some that are in the packet I won't use, some I'll have edited somewhat before using them, 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 packet.
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.
From my look at your quizzes (from today) so far, my impression is that the first "real" quiz (but it was a very unusual quiz for the course---it wasn't proving anything or so on, and was in part about the course rules) went much better than the diagnostic quiz. Good, and thanks to (most of) you for having read the course info document and the reading so well! Nonetheless, I'm still worried about foundations, which are are a different issue. Clearly, 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!... I'll on the quiz tell you which one(s) to prove). 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 fine 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.)
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, 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 try to 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" as I just did with this one... 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.
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 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.)
What is this "nonquiz exercise"? Well, it is something that could have appeared on a quiz on Wednesday. However, it is pretty hard (though so is the quiz we'll have Wednesday). So let us do this. Please try to put about one hour into this nonquiz exercise before class on Wednesday. If you do solve it within that time---GREAT, and congratulations for having both learned a certain proof we did in class 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 and we will go over it in class on Wednesday---but your having worked for an hour 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 on Wednesday, though this or similar questions could appear on future quizzes/homeworks/etc.
Note that we have NOT yet covered in class the stuff needed to do its final problem (problem 7), but I expect that we will do so next class.
Comment: This homework set doesn't ask you any of the Bov-Cre problems that use the terms "domain" and "codomain" as regards functions, but just in case you for fun try to do some of the problems that do, let me mention that the way Bov-Cre use the terms is not standard (so do not use it anywhere else---certainly not on the comps---as no one will know what you mean). A safer term for what they call the codomain of a function would be the image of the function. And the term codomain often---though not by Bov-Cre---is used for the entire space on the receiving side of the function---both those elements that are hit and those that are never mapped to. And the term range is a killer as some people use it to mean that also, but some people use it to mean the image. So safest is to just avoid that word.
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}$").
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), are pages 39-40 of Bov-Cre.
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'':
Put more explicitly: You should review very carefully the proof we did today on Monday that \overline{HP} is not r.e. and solution to today's quiz; you should not merely memorize them , but should even try to learn their *idea*(s), very well, so that you can generalize, vary, and apply them. Another reason you should think hard about the quiz solution I presented in class today is that when a quiz goes not so well, I sometimes (hint, hint) either repeat the problematic problem, or give another problem that is similar or related.
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 might be able to arrange with the TA for him to accept your homework via fax or email or express mail. but in any such case, it would have to be by arrangement with him, and would have to 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) arrive no later than the due day/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).
Show, via a many-one reduction, that the language L = { i | M_i is a total TM } is not RE.
Speaking of the one-on-one meetings, here is a quick summary of some of the type of things I typically mentioned to people in our one-on-one meeting today (but I may have not mentioned all of these to everyone, so here are the highlights):
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).
(a) Prove that All coRE sets over the alphabet {0,1} are Rochester-enumerable sets.
(b) Prove that 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}}.
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 Satyaki has office hours every weekday, and that if you not comfortable with any of this material, for goodness 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 a perhaps-280-point 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!
Please remember also, as discussed in class, that each group will give and grade 10 10-point chunks of material (this will NOT be one 100-point superchunk; it must be 10 regular, independent chunks), which could be in various forms (quizzes and/or homeworks). Each person in the group giving the material will get, on each chunk, the median of what all the people outside of the group got on that particular chunk.
Also, you should make sure that you have graded and returned all quizzes and homeworks no later than during your final class session. And by that time or within a few minutes after, the grades for the 10 10-point chunks by that time should be in the TA's and my emailbox, from you. Also, by 1159PM the day of your final lecture I should have from you via email your revised slides for all of your lectures. (Be careful. This is a time-frame tightening relative to what I mentioned earlier today!) Mail the slides ideally as either .pdf (if you send them as .pdf make *sure* to also send an archive of the source code, but I'll probably just check the .pdf) or as a PowerPoint file. Reminder: all 3-4 of your lectures should be either in a SINGLE pdf file or a SINGLE PowerPoint file.
Further discussion of expectations went on in class today, and in our individual meetings today.
To ensure that your lectures are as polished as possible, each lecture of each group should be run-through for the TA (ideally, in 632 or some similar classroom, using the same A/V approach you will use in the actual class) long enough before the lecture that you can, in light of whatever suggestions he makes, re-edit/revise the slides/presentation to adopt any suggestions he makes that you think will improve your talk. (Slight disclaimer: He will do his best to make helpful comments, but of course his taste and mine may differ, so it is in concept possible that I'll dislike something you do based on his suggestion. In the end, it is your responsibility to make your talk as excellent as possible. However, I suspect that on average the TA's suggestions will be vastly more helpful than nonhelpful, and that you thus should follow them unless you strongly feel that his suggestion is not helpful.)
It probably is a very good idea to NOT make your classmates copy down your slides during your talks. Instead, I'd suggest that you hand out to the class copies of the slides you will be using in your talks, so your classmates can make their notes on those. (So, at the start of each class you could give them copies of your slides for that talk. Or, or example, at the start of the first talk, you could hand out slides for all three of your talks.)
A natural question to ask is: "Am I right in assuming that