CS 280 Instructor Page
Course Name: Computer Models and Limitations
Instructor:
Prof. Lane A. Hemaspaandra
Graduate TA:
Scott Ames
The Course Catalog Description: This course studies
fundamental computer models and their computational
limitations. Finite-state machines and pumping lemmas, the Chomsky
hierarchy, Turing machines and algorithmic universality,
noncomputability and undecidability, tradeoffs between power and
formal tractability.
Textbook:
Introduction to the Theory of Computation, Michael Sipser,
(the brand new) third edition, 2012.
Be careful
not to accidentally get the first or second edition.
Prerequisites (very important): CSC162 OR CSC172 OR MTH172.
Course Information Document/Syllabus:
Here (version 1.15, last updated 2013/4/1/8:36PM).
Slides:
Here (version of 2013/4/12/3:52PM)
are the slides up to and including Chapter 5,
and
here is the slide set (consisting
of slides 67 through 87 of the slide set for CSC 286/486, a course all
UR CS Ph.D.-program students are required to take!) that we'll use for our
introduction to P and NP. In the dream case, we'll manage to cover
all these slides... and, if there is time left after that, then for
additional lectures (probably on applying P and NP to elections) we'll
have stand-alone lectures, most with their own slide sets.
The slide set for the 2013/4/24 lecture on Lewis Carroll's election
system and the class of sets computable by parallel access to NP
is available
here.
The slide set for the 2013/5/1 lecture on
"Search versus Decision for Election Manipulation Problems"
is available
here.
Reading Assignments (usually assigned the class before it is due):
-
Due 2013/1/23/325PM: Read the entire Course Information Document/Syllabus,
and in SIP read from page xi through the middle of page xiii. That is,
read, in the 3rd edition, within the "Preface to the First Edition,"
the sections called "To the Student" and "To the Educator." Expect
a surprise quiz on 1/23.
-
Due 2013/1/28/325PM: Read SIP Chapter 0. A surprise quiz on
1/28 would not be too surprising.
-
Due 2013/1/30/325PM: Read SIP Chapter 1.1. A surprise quiz on
1/30 would not be too surprising.
-
Due 2013/2/4/325PM: Read SIP Chapter 1.2. A surprise quiz on
2/4 would not be too surprising. This reading may well
(as will many reading that are for over weekends, and other
readings too) be helpful
on the homeworks (such as the current homework).
-
Due 2013/2/13/325PM: Read SIP Chapter 1.3.
This reading covers the constructions we went over in class
on 2/11.
-
Due 2013/2/18/325PM (but you'll want to do it before
doing the homework, I'd expect): Read SIP Chapter 1.4.
This reading covers what we went over in class
on 2/13.
-
Due 2013/2/25/325PM: Read SIP from the start of Chapter 2 through 4 lines from
the end of page 108.
-
Due 2013/2/27/325PM: Read SIP from 3 lines from
the end of page 108 through the end of page 129.
-
Due 2013/3/18/325PM (suggestion: it actually might be a good idea to
do this reading on 3/17 or early 3/18, so it is fresh in your mind
when you come to class on 3/18, a day on which there might well be a
(surprise!) quiz; of course, reading it right now first, and then
making that later reading be a second reading, is an even better idea;
reading it every day all through spring break might be a better idea
still, but that might be asking a tiny bit too much I suppose): Read
SIP from the start of Chapter 3 through the end of Section 3.1.
-
Due 2013/3/20/325PM: Read SIP Section 3.2. Also (and the Terminology
subpart of this wasn't at all covered in class, but will help you with
later SIP readings and at the workshop this week) read SIP Section 3.3.
-
Due 2013/3/25/325PM: Read SIP, from the start of Chapter 4 to the end
of Section 4.1.
-
Due 2013/4/1/325PM: Read SIP, Section 4.2.
-
Due 2013/4/3/325PM: Read SIP, From the start of page 215 up to 10 lines from
the end of page 220.
-
Due 2013/4/10/325PM: Read SIP from the start of Section 5.3. through
the 8th line of page 238 (i.e., to right before Theorem 5.30). And if
you are not yet thoroughly, utterly, totally comfortable with and
great at proving things undecidable, then please reread very carefully
from the start of Section 5.1 to 10 lines from the end of page 220;
related note: it is quite important that you understand how to prove
things undecidable.... by the way, we will have more quizzes on (in
part) undecidability, including probably one at our 4/10 class.
-
Due 2013/4/15/325PM: Read in SIP the statement and proof
of Theorem 5.30.
-
Due 2013/4/17/325PM: Read in SIP from three lines from the end of page
284 to the end of the proof of Theorem 7.14, and from the start of
Section 7.3 to five lines from the end of page 295. WARNING: That
second batch of reading gives a quite lovely but
not-standardly-used-as-the-primary-definition definition of NP, and
then as Corollary 7.22 proves that it gives the same class as the
standard definition (which is the definition we covered in class
today). (More typical is to define NP the standard way, namely as
nondeterministic polynomial time, and then note that the same class of
languages is also captured by the lovely notion that Sipser uses as
the primary definition, and in fact that was I mentioned briefly in
class today, and it appears on slide 7 of our P/NP slide.)
-
Due 2013/4/22/325PM: (As always, but it is more important for this
material than for most, please review the slides we covered this week,
namely, the separate P/NP slide set on our main web site!) Read in
SIP from 4 lines from the end of page 295 through the end of the proof
of Theorem 7.36. (Note that, assuming we take it as settled that 3SAT
is NP-complete, as it indeed is, Theorem 7.32 establishes that CLIQUE
is NP-hard, and since CLIQUE is also in NP, we have that CLIQUE is
NP-complete.) To get a sense of the nature of some other NP-complete
problems, skim Section 7.5, by which I mean I won't test you on this
reading, but you should at least read the definitions of the four
additional NP-complete problems discussed in this section (and if you
really are a theory fan, you might want to skim or even read the
proofs of their NP-completeness). OPTIONAL (just for anyone who is
particularly interested in this): You do NOT have to go read
Borodin-Demers in the literature... however, if you do want a
statement/proof of Borodin-Demers... well, you can find that on the
course slides, namely, the final two slides we went over today! If
you want another source, well, you could go to their original 1976
paper, but if you do, my guess is you might have a bit of trouble
connecting that to the version of their theorem, or the proof, that we
covered in class (even I'd have a big bit of trouble, and I'm pretty
expert on this). However, you can find a relatively clean write-up of
the unambiguous-version-of-NP (so-called UP) analogue of
Borodin-Demers as Chapter 6.2 of my Ph.D. thesis (you can find my
thesis
here;
I'm amazed that my advisor and the graduate school at Cornell
let me get away with including a joke ``publication'' with a
2400-years-ago-dead person in the footnote
on page iii),
and that write-up
implicitly makes clear a simple proof of the NP version too, by
analogy. (Warning: For the UP version, the converse also holds, and
the thesis proves that, but for the NP version, it remains an open
research question whether the converse holds---and there is so-called
relativized evidence that it does not.)
-
Reading related to the 2013/4/24 lecture:
This is not required reading. But just in case you do want to
read or skim the full paper corresponding to today's lecture,
that paper is:
"Exact Analysis of Dodgson Elections:
Lewis Carroll's 1876 Voting System is Complete
for Parallel Access to NP,"
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe,
Journal of the ACM,
V. 44, Issue 6,
pp. 806-825,
November 1997. You can get it free online through
the UR library's ejournals gateway.
-
Reading related to the 2013/4/29 lecture: This is not required
reading. But just in case you do want to read or skim the full paper
corresponding to today's lecture, that paper is: How Hard Is Bribery
in Elections?, P.~Faliszewski, E.~Hemaspaandra, and L.~Hemaspaandra,
Journal of Artificial Intelligence Research, V.~35, pp.~485--532, July
2009.
You can get it free online at its journal web site
here.
-
Reading related to the 2013/5/1 lecture: This is not required
reading. But just in case you do want to read or skim the full paper
corresponding to today's lecture, that paper is:
Search versus Decision for Election Manipulation Problems,
E. Hemaspaandra, L. Hemaspaandra, and C. Menton. The conference
version, in STACS 2013, is online
here,
and the full technical report version is online
here.
Homework Sets (this list does not include the large number of homework-style problems you'll solve in your workshop):
- HW Set 1 (handed out 1/23 and due 2013/1/28/325PM).
-
(10 pts) 0.2 b/f.
-
(10 pts) 0.3 b/d/f.
-
(20 pts) 0.6 b/d.
-
(20 pts) 0.7 b.
-
(20 pts) 0.11 b.
-
(20 pts) Prove by induction that the number of binary strings
(strings over the alphabet consisting of 0 and 1) of length
at most k is 2^{k+1} - 1.
That is, prove by induction that 0 + 1 + 2 + 4 + ... + 2^k = 2^{k+1} -
1. (Note: "^" denotes exponentiation. More generally, in this course,
when writing math as ascii text, I'll often use LaTeX-style notation.
See any LaTeX guide's basic chapter on math for more on what LaTeX
math notation looks like.)
- HW Set 2 (handed out 1/30 and due 2013/2/4/325PM).
Be careful. The first thee problems aren't very hard.
But the last two are drawing on beautiful insights, though ones
that you may have seen used in your workshops, although on simpler
cases. The fifth problem is especially magical (or difficult,
depending on one's view of things), as it works even
if B is an undecidable set; it is an example of a construction
that isn't a (so-called) "effective" construction.
-
1.4 (20 points) f,g.
-
1.5 (20 points) d.
-
1.7 (20 points) e.
-
(20 points)
[This removes all the hints, as they were badly flawed.
See my "Announcement" at BB of 2/3; but due to the flawed
hints, everyone will get full credit for this problem
as long as they turn in this problem set.]
Finally, let our alphabet Sigma be {A,B,...,Z}.
(a) What is the size of the smallest DFA that accepts the language of
all strings over the alphabet Sigma that have length at least 4 and
whose 4th to last character is the letter L.
(b) Prove that no DFA smaller than the size you came up with in part (a)
can accept that language.
(c) Write the obvious NFA (for this language) that is wildly smaller than
the DFA of part (a)?
-
(20 points) Prove that if A is a regular set over the alphabet {0,1},
and B is any set over the alphabet {0,1} (you may NOT assume that
B is regular), then the set Zounds(A,B), defined by
Zounds(A,B) = { w | (\exists y \in B) [wyy \in A}, is itself regular.
(Hint: This extends SIP Problem 1.45, which you with luck
will have covered
in your workshop.)
- HW Set 3 (handed out 2/6 and due 2013/2/10/325PM).
The two problems here are from the
"Example Problems, Week of 2013/2/4" sheet
that was handed out on 2/4, and is also
available at
here (note:
this isn't the exact version handed out in class; I've
fixed the hint to Harder Problem 1, and made explicit
which ones want a DFA rather than an NFA\@.
Your answer should not be just copying out of notes you
took on the solution groups put up in class, but should
be your own (together with your homework-mate if you're doing
it in a group of two) good write-up of a solution, that you
thoroughly understand, to these problems. (So, ideally, without
looking at your notes, do the entire problem solution and write-up.
Even if you need to look at your notes, ideal is to put them aside
as you do the write-up, so that you know that you know how to do it.)
And yes, these problems add up to 110 points, so you can even
end up with more than one hundred percent, as we'll view it as out of
100 and anything beyond 100 would in effect be giving you extra credit.
-
(25 points) Number 4 of the "Easy Problems" section. Except
Except both draw the NFA and then also specify the NFA you drew,
as a 5-tuple.
-
(25 points) Number 1 of the "Harder problems" section (for the binary
case), and make sure to give a DFA, not an NFA, and to have at most
three states in it.
-
(30 points) Number 1 of the "Harder problems" section (for the binary
case), except now for the case of division by five. Your solution
must be a DFA, not an NFA, and must have at most five states in it.
-
(30 points) Number 3 of the "Harder problems" section.
(We in this problem are speaking of DFAs, not NFAs.)
NOTE: When originally posted, this problem had a parenthetical "for
the binary case," but as per the 2/7 announcement, you should
ignore that, as this problem is over a 26-letter alphabet and
you should tackle it for that case. Thank you!
- HW Set 4 (handed out 2/13 and due 2013/2/18/325PM).
This adds up to 120, so you can
get up to 120/100, i.e., up to 20 extra credit points if you get
everything right. (These are the to-be-graded homework problems for
this weekend. Of course, you'll have done a large number of
problems and examples in your workshop---some quite related to these,
perhaps!)
-
(30 points) 1.17(a).
-
(30 points) 1.21(a).
-
(30 points) Give a DFA of at most 7 states that
accepts all strings over the alphabet {0,1,2,3,4,5,6,7,8,9}
that when viewed as decimal integers are multiples of 7.
(Interpret the empty string as representing the integer 0, and leading
0's are treated naturally, e.g., 0017 represents the integer
seventeen.) (Doing problems like this by in effect doing long
division---as we did in class for the case of multiples of 3 in binary---is
a great approach, as that approach works quite generally.)
-
(30 points) (a) (15 points) 1.29(b). (b) (15 points) Prove that
{a^i b^i c^i | i \geq 0} is not regular; do so just using the
pumping lemma---not by using closure properties or intersections.
The alphabet is {a,b,c}, there is no space in the alphabet... I've put
spaces in the definition of the set just so it is easier for you to read---they
are not really there as to the actual strings in the set.
- HW Set 5 (handed out 2/18 (!) and due 2013/2/25/325PM).
The set is
this PDF document,
to be printed and then for you to
write your answers onto and hand in.
- HW Set 6 (handed out 2/27 and due 2013/3/4/325PM). This adds up
to 110, so you can get up to 110/100, i.e., up to 10 extra credit
points if you get everything right. (These are the to-be-graded
homework problems for this weekend. Of course, you'll have done many
problems and examples in your workshop and in the in-class
example/problem day we had
on 2/27.) Please do these quite carefully, and please check your
work; it is surprisingly easy to misread or misdo problems like this,
e.g., if the problem says n \geq 1 but you read it as if it said n
\geq 0, or you miss a case, or etc., and for CFLs, pumping lemma proofs
require even more care than was the case with the earlier pumping
lemma for regular sets (because it is so very easy to miss cases
as to how the string w might be broken up into 5 parts meeting
the rules).
-
(30 points) Give a context-free grammar generating
L = {0^m 1^n | m \neq n and m \geq 0 and n \geq 0}.
(Note: \neq is the "is not equal to" symbol.)
(Note: In the strings in this language
there is no space between the 0's and the 1's... the space above
is, as usual here and elsewhere (e.g., problems 2 and 4 of this set also),
just so you can clearly read what the set is. So for example
the string 00011111111 is a member of the set. And the alphabet
for this problem is (implicitly) {0,1}, not {0,1,SPACE}, where SPACE is the
space character.)
-
(25 points) Give a context-free grammar generating
L = {0^{m+3} 1^{4m+7} | m \geq 2 }.
-
(25 points) Use the pumping lemma for context-free languages
to prove that {w##w# | w \in {a,b}^*} is not a CFL. (Our
alphabet here is {a,b,#}. Do note the three #s in the problem's statement,
since your proof will have to be aware of the #s and handle/discuss
them appropriately.)
-
(30 points) Use the pumping lemma for context-free languages
to prove that {a^n b^n a^n b^n a^n | n \geq 1} is not a CFL.
- Note: Due to HW Sets 5 and 6 having been done extremely
well by the class, there will not be a homework assignment
given on 3/6 for over spring break. (There however is a reading
assignment for over spring break, and there probably will be a
(surprise!) quiz on the first day after spring break, namely, 3/18.)
- HW Set 7 (handed out 3/20 and due 2013/3/25/325PM).
This adds up
to 110, so you can get up to 110/100, i.e., up to 10 extra credit
points if you get everything right. (The third problem, of course,
is the really fun, cute one. It takes an insight!)
-
(40 points)
SIP 3.13.
-
(40 points) SIP 3.16, part b. (Machines can run
forever! Failing to remember that fact could lead you to
an incorrect solution. Perhaps some technique that lets one
avoid falling down a black hole would be helpful here? Or,
alternatively, perhaps helpful might be
using some other (other than just using a TM
directly, that is) approach to handling Turing-recognizable
sets---such as the idea of using enumerators---that already in some sense
prepackages for you protection against getting sucked into
a black hole?)
-
(30 points)
SIP 3.19. (Hint: Thinking a bit about an enumerator for the language might
help here, on this takes-an-insight problem!)
- HW Set 8 (handed out 2013/3/28 and
due 2013/4/1/325PM).
This adds up to 110, so you can
get up to 110/100, i.e., up to 10 extra credit points if you get
everything right.
Please when doing this set note the
point 2 of the 2013/3/27 BB announcement, regarding
(as a one-time exception to our normal guidelines) being able to
use in your write-up discussion/notes/text from your workshop
this week, but note also the caution regarding this contained in
point 2 of that BB announcement.
-
(25 points)
SIP 4.2,
-
(25 points)
SIP
4.7
-
(25 points)
SIP
4.16
-
(35 points) SIP 4.18. (Don't forget to do both the ``if'' and the
``only if'' directions!) (Hint: Note that for each Turing machine M,
the set { \langle x,t \rangle | M accepts input x within t steps} is a
decidable set. Perhaps you can find a way to put that to use on this
problem? Relatedly, perhaps finding a way to map strings to natural
numbers, in a way that works within the context of the problem, might
be the charm for part of this?)
- HW Set 9 (handed out 2013/4/4/140AM and
due 2013/4/8/325PM).
This adds up to 120, so you can
get up to 120/100, i.e., up to 20 extra credit points if you get
everything right. Please start this set early; all four of
these problems are hard, or at least, are quite possible to get
wrong unless you are careful.
- [30 points] SIP 5.2. (So, you need to specify, in a high-level
way, a TM M such that the language accepted by M is the set of all pairs
of CFGs such that the languages of the two CFGs *differ*. Hmmmm... two
languages differ exactly if there is at least one string on which
one of them accepts and one of them rejects. And note Theorem 4.7.
Can you put this all together to achieve the goal here?)
- [30 points] SIP 5.9.
- [30 points] Prove that {\langle M \rangle | \overline{L(M)} is infinite } is
undecidable. (Use the Sipser Chapter 5.1 flavor of proof. So assume
it is decidable. And then use a hypothetical total TM (decider) for
it to let you show that $A_{TM}$ problem is decidable. And note that
that is a contradiction.) Warning: "\overline{L(M)}
is infinite" is NOT semantically identical to "L(M) is finite." For
example, the set of odd length strings has an infinite complement, yet
is infinite itself. Note: Yes, this was from your workshop (assuming
your workshop got up to doing this); but even so, you need to write
it up in your own words, even if you took notes on this at the
workshop.
- [30 points] For this problem, assume that (TMs had been defined so
that) all TMs have input alphabet $\{0,1\}$ and that all strings (that
we discuss) are over that same alphabet. Let
$WHEE = \{\langle M_1,M_2,M_3 \rangle | M_1 and M_2 and M_3 are each
TMs, and L(M_1) union L(M_2) = L(M_3) \}$. Prove that $WHEE$ is
undecidable. (Use the Sipser Chapter 5.1 flavor of proof. So assume
it is decidable. And then use a hypothetical total TM (decider) for
it to let you show that $A_{TM}$ is decidable, and note that that is a
contradiction.)
- HW Set 10 (handed out 2013/4/9/546PM,
version of 2013/4/9/847PM,
and
due 2013/4/15/325PM).
This adds up to 115, so you can get up to 115/100, i.e., up to 15
extra credit points if you get everything right. Please start this
set early, and do the problems with great care. Note that the first
problem is worth 25 and the rest are worth 30 each.
- [25 points] Do SIP 5.4. (The correct answer to the first part of
5.4 is "no," so what you need to do on this homework is give an A and
a B that show that "no" holds, and explain why that is so.)
- [30 points] Prove that { \langle M,x,M' \rangle | if M accepts x and
M' does not accept x } is undecidable. (Use the Sipser Chapter 5.1
flavor of proof. So assume it is decidable. And then use a
hypothetical total TM (decider) for it to build a decider for A_TM
(NOT for E_TM, but for A_TM). And note that that is a contradiction.)
- [30 points] Prove that { \langle M1, M2, M3, M4 \rangle |
L(M1)=L(M2)=L(M3) and L(M1) \neq L(M4)} is undecidable. (Use the
Sipser Chapter 5.1 flavor of proof. So assume it is decidable. And
then use a hypothetical total TM (decider) for it to build a decider
for A_TM (NOT for E_TM, but for A_TM). And note that that is a
contradiction.)
- [30 points] Prove that { \langle M1, M2, M3, M4, M5 \rangle |
||{L(M1),L(M2),L(M3),L(M4),L(M5)}|| = 4} is undecidable. ||S||
denotes the cardinality of S.
- HW Set 11 (handed out 2013/4/16/1148AM,
version of 2013/4/16/1148PM,
and
due 2013/4/22/325PM).
This adds up to 125, so you can get up to 125/100, i.e., up to 25
extra credit points if you get everything right. Please don't leave
this set for the last minute: It will probably be our final problem
set of the term, but some of the problems are pretty hard, and almost all can
be gotten quite wrong (or at least one might lose serious points on
them) unless one does them quite carefully.
-
[25 points] SIP 7.12.
-
[25 points] We say a class C is closed under symmetric difference
exactly if for every pair of sets A \in C and B \in C, it holds that
the set (A-B) \union (B-A) itself belongs to C. Prove that P is
closed under symmetric difference. (Note: You may in your proof draw
on the following result that you proved at workshop this week: P is
closed under union, intersection, and concatenation.)
-
[25 points] Prove that NP is closed under symmetric difference IF
AND ONLY IF NP is closed under complement. (By C closed under
complement, we mean that for each A \in C, it holds that [A \in C IFF
\overline{A} \in C].) (Hint: Make sure to prove, separately and
clearly, both (1) If NP is closed under symmetric difference then NP
is closed under complement, and (2) If NP is closed under complement
then NP is closed under symmetric difference. [WARNING: Don't read
the rest of this hint unless you want to have a hint as to how to
solve the cuter part here---but you might well want to first tackle
this yourself, as I'll bet you can do it, and once you have, you won't
think it to have been hard at all.] One direction---item (1)---in
particular may take a cute trick that is easy one you've noticed it,
but might take a moment to find... hint: Is there some particularly
easy NP set that might really help with this direction---keep in mind
that NP is an upper bound, so even all P sets are members are NP!)
-
[25 points] Let FUN = {f | (f is a boolean formula) and (f \in SAT)
and (all variables in f appear the exact same number of times as each
other)}. Prove that FUN is NP-complete; in doing so, you may assume
that SAT is NP-complete. (Hint: So, you need to prove that FUN \in NP;
do so carefully. And you need to prove that SAT polynomial-time mapping
reduces to FUN; do so carefully.) For the purpose of this problem,
consider x and \overline{x} to be the same variable. So for example (x3
AND \overline{x2} AND \overline{x2}) OR ((x2 AND \overline{x3} AND
\overline{x3}) AND (x1 AND \overline{x1} AND \overline{x1})) is an
element of FUN, because each of x1, x2, and x3 appears three times, and
this happens to be a satisfiable formula. (Note: This problem---but not
its solution---was on our P/NP slides, and it was briefly verbally
discussed it in class. But the current problem is asking you to write
up an actual proof of the solution, making sure to handle both the
membership in NP and the NP-hardness.)
-
[25 points] For any set A (over the alphabet \Sigma), let
firsthalves(A) = { x | (exists y \in \Sigma^*) [ |x| = |y| and xy \in
A]. (Note: xy denotes x concatenated wit y.) So for example we know
that if A is regular, then firsthalves(A) is regular. Prove that if A
\in NP, then firsthalves(A) \in NP.
Other
Important
Links:
Some of My Favorite Bits of Science Wisdom:
-
After solving a challenging problem, I solve it again from scratch,
retracing only the *insight* of the earlier solution. I repeat this
until the solution is as clear and direct as I can hope for. Then I
look for a general rule for attacking similar problems, that *would*
have led me to approach the given problem in the most efficient way
the first time. -- Robert Floyd
-
In computer science, elegance is not a dispensable luxury, but a
matter of life and death. -- Edsger Dijkstra
-
Imagination is more important than knowledge. -- Albert Einstein
-
They are ill discoverers that think there is no land, when they can see
nothing but sea. -- Francis Bacon
Other Odds and Ends (Mostly Quotations):
-
I don't believe it. Prove it, and I still won't believe it.
--Life, the Universe and Everything
-
It was mentioned on CNN that the new prime number discovered
recently is four times bigger then the previous record.
-
Sooner or later society will realize that certain kinds of hard work
are in fact admirable even though they are more fun than just about
anything else. -- Donald E. Knuth
-
Getting tenure doesn't really change anything.
However, not getting tenure changes everything.
-
My late friend Stan Ulam used to remark that his life was sharply
divided into two halves. In the first half, he was always the
youngest person in the group; in the second half, he was always the
oldest. There was no transitional period.
-- Gian-Carlo Rota, "Indiscrete Thoughts"
-
Fools ignore complexity. Pragmatists suffer it. Some
can avoid it. Geniuses remove it.
-- Alan Perlis, Epigrams in Programming
-
More Quotes from Dijkstra:
* None of the programs in this monograph, needless to say, has been tested on a machine. (From "A Discipline of Programming.")
* Computer science is not about computers, any more than astronomy is about telescopes.
* The question of whether computers can think is just like the question of whether submarines can swim.
-
"Supposing a tree fell down, Pooh, and we were underneath it?" [said Piglet.]
"Supposing it didn't," said Pooh after careful thought.
Page Maintained by: Lane A. Hemaspaandra