🚀 go-pugleaf

In article <1992Nov4.163618.17991@dcs.qmw.ac.uk> arodgers@dcs.qmw.ac.uk (Angus H Rodgers) writes:
>The analogy with grammars is a favourite one of mine, too. (If Vaughan 
>Pratt is reading this, perhaps he'll explain this analogy using enriched
>categories??)

Actually 2-categories are the right tool here, namely the case of
categories enriched in Cat.  :-)

I've been following this thread with some interest.  Let me first give
my background.  I ran the theory division in Stanford's computer
science department the past three years (I'm on sabbatical this year
and mixing writing papers and proposals with reading physics and
Usenet).  I've had plenty of opportunity in those years to wax
philosophical about theory's relationship with the other CS divisions,
systems, AI, and scientific computing.  This has led me to propose on a
couple of occasions to restructure the department orthogonally to its
present organization, a proposal that has been met with both some
interest and considerable inertia.  So although it's not going to
happen overnight there's hope.  In the meantime the department will
continue to segregate the scientists and the engineers, which has its
good points and bad.

The variation in degrees of science vs. engineering is much greater
within computer "science" than between the subjects CS, math, physics,
medecine, biology, electrical engineering, mechanical engineering,
operations research, psychology, and philosophy, this being a nearly
complete list of the subjects that CS-ers at Stanford tend to interact
with a lot.  All of these subjects except perhaps for math and
philosophy have both experimentalists and theoreticians, creating a
diversity of research styles that is replicated across departments.

To me engineering is the "how" of our universe and science is the
"wh-":  "why," "whether," "when," and "where."  "Universe" here is
broadly construed to include neutrons, nematodes, numbers, and
nebulae.  Some computer scientists want to know how to make their
computers faster and their users more productive.  Others want to know
why this edge-follower is correct, whether that logic is complete, when
this matrix-multiplier halts, and where that root-finder converges.

There is no clear boundary separating "how" from "wh-".  If the goal is
a product then "how" has priority, "wh-" is usually a luxury, but on
occasion a necessity.  Conversely if the goal is pure science, the
"how" may be merely the data from which the scientist starts, the "wh-"
is the goal, though the search may yield additional "how"'s in the
natural course of things.

Anyone who thinks that computer science puts more emphasis on "how"
than "wh-" may have experienced CS departments that emphasized computer
engineering over computer science.  As a prime counterexample, the
Cornell CS department has for much of its ~25 years of existence been
very theoretical, and I would think few familiar with that department
would deny its claim to be truly concerned at least as much with the
science of computation as with its engineering.  While it has in recent
years moved somewhat closer to an even mix of science and engineering,
my assessment is that Stanford, MIT, and Berkeley have all been well
balanced in that general regard from the beginning.  (This is not to
say they don't all have curriculum gaps of one kind or another; in that
respect I consider Stanford to have fewer glaring omissions today than
any of the other top handful of schools.)  CMU, which previously had an
engineering slant, has evened things up quite well within the past
decade by a consisiderable strengthening of its theory group, though
Dana Scott's move to Linz this year is quite a blow.  CMU plus Cornell
would be a dynamite combination!

When someone puts down any discipline as not being a science, an easy
test for whether they know what they're talking about is to ask them a
few of the elementary questions from the science of that discipline,
questions that any Ph.D. student taking the comprehensive exam should
be able to answer.  Here are some candidate questions for the science
of computation based on introductory courses I've taught recently at
Stanford.  Perhaps others would care to draw on their experience to add
to this list.

1.	Give upper and lower bounds, tight to within a constant factor,
	on the number of comparisons required to (a) sort an n-element
	array (b) merge two n-element arrays.

2.	How can the Fourier transform help with polynomial
	multiplication?  By how much?

3.	Define the complexity classes P and NP.  How are they related?
	Which class corresponds to the easy problems?  Which of the set
	of (a) primes (b) composites are in either of these classes
	when written in decimal?  Would the problem of testing
	primality become easier or harder in the above sense if the
	numbers are written instead in unary (tally) notation?

4.	Show how to find an occurrence of a pattern in a file in time
	proportional to the sum of their lengths.

5.	Is the halting problem decidable for a nondeterministic
	automaton equipped (a) with a stack (b) with a writable input
	tape (no writing permitted beyond each end) (c) both?

6.	What is a context-free language?  Give two definitions, in
	terms of grammars and in terms of automata, and define the
	grammars and automata you need.

7.	What is the distinction between ambiguity in a grammar and
	inherent ambiguity in a language?  Are there any inherently
	ambiguous (a) regular languages (b) context-free languages?
	If so give an example.

8.      Which definitions have a greater variety of fixpoints,
	primitive recursive or general recursive?  Why?  Can either kind
	have no fixpoint?

9.	Show that a set is recursive if and only if both it and its
	complement are recursively enumerable.

10.	In what sense can there be no programming language for the
	recursive sets, and why?  Can there be a programming language
	for the primitive recursive sets?

11.	What does it mean for a theorem proving method to be complete?
	Is Robinson's resolution method complete?  Explain.

12.	Name a logical system supporting program verification and give
	axioms or inference rules for it illustrating its use with two
	of the four program constructs, assignment, begin-end
	sequencing, conditional statement, iteration.

13.	Define and compare deadlock, starvation, and livelock.  Which
	are safety conditions and which liveness?

14.	Can a circle be drawn as a Bezier cubic, and if so how, (a) exactly
	(b) approximately?  What if rational cubics are permitted?

15.	In filtering an image to remove aliasing, what difference does
	it make whether you filter before or after sampling, and why?

16.	Is the CIE chromaticity diagram convex?  Why/why not?

17.	Can a color filter defeat color camouflage?  Explain.


I'd be interested in hearing from anyone who knows the answers to at
least twelve of these questions but who feels that computation has no
substantive underlying science.

-- 
Vaughan Pratt				There's no truth in logic, son.