FOM: accessibility of "algorithm"

[Vaughan R. Pratt]

>The invariance of the notion of what is programmable
>is surprising and slightly harder to explain, but even this is
>not really essential for understanding a statement like "no
>computer program can identify which equations are solvable in
>integers".  -- Joe Shipman

In the light of Joe's extremely reasonable and important (because
elementary) point, and Sam Buss's endorsement of it, I need to either
sharpen my claim for the importance of distinguishing size and
complexity or sharply reduce it.

You need this distinction to understand the *denotational semantics* of
computability as expressed in notions like recursively enumerable set
and partially recursive function.  But to simply appreciate that
computers have limitations, I'll concede (cheerfully since it makes all
our jobs easier) that it is sufficient and more direct to consider
operationally the question of whether a program exists that meets the
desired specification by carrying out an appropriate computation for
each input.

What denotational semantics in terms of computable sets permits is a
mathematically precise abstraction from the gorier details of the
definition of "program", while retaining sufficient formality for
rigorous arguments.

But to merely convey the idea that computers have their limitations,
without actually proving the theorems, such details aren't needed.  For
an informal introduction it suffices to point to the computers that run
on desktops worldwide as witnessing that programs exist for performing
a wide range of tasks.  You can then list a few of these tasks in
increasing order of difficulty, such as searching, sorting, and
traveling salesman (paralleling the regular-CF-P-NP-TM progression in
the more formal development, with the same motivation), leading up to
the halting problem for the very programs witnessing the solvability of
the preceding problems, *and their ilk*, whatever that turns out to
mean, including contenders for this job.  This sidesteps formalizing
the notion of either program or computability.

After that one can start waxing more pedantic about various points.

One such that I think should enter earlier rather than later, in
particular before denotational semantics and the size-complexity
distinction, is the distinction between the halting problem for a
particular input vs. that for an infinite set of inputs.  Students
often commit the type error of calling undecidable the question of
whether a particular program halts on a particular input, which leads
to incorrect conclusions and paradoxes.  It's a distinction that's
easily made and well worth practicing on with a few examples, including
examples of the paradoxes resulting from getting it wrong.

On the other hand, I think if I had gotten up to the halting problem as
above and still had ten minutes to spare, I'd skip the pedantics
altogether and simply give the diagonalization argument (draw a square
with columns indexed by programs and rows by inputs, fill it with 1's
and 0's indicating termination, show Big Claim: if you could solve the
halting problem you could write a program whose column would equal the
complemented diagonal, then look at their intersection).  Those
encountering computability for the first time may well not get it, but
at least they'll have seen all the essential structure of the argument
and know it isn't any bigger than that.  They might even read their
notes at home.

And then you can move them towards denotational semantics by asking how
many constantly 0/1 rows/columns can appear in this matrix, making the
connection between the columns viewed as sets and the domains of
computable functions, and bringing in the word recursively enumerable.

Sorry it took me two passes to tune this, my excuse is that I've been
in the same boat as Sam with regard to the preparation of my typical
students:

	From: sbuss at herbrand.ucsd.edu (Sam Buss)
	When I teach algorithms/Turing machines/automata to college who know
	how to program, the students are very ready accept the abstract
	notion of algorithm.

Vaughan Pratt