ALGORITHMS, PROBLEMS, PROGRAMS


     ALGORITHMS AND PROGRAMS

An ALGORITHM is an effective computational procedure.

A PROCEDURE is a finite specification of step-by-step instructions.

A COMPUTATIONAL procedure is one that in principle could be carried
out by a computer. It's result, or output, depends only on the
syntactic form of whatever input is supplied to it, hence its
input-output relation is formal and does not vary from one execution
to another as long as the input is the same. We say it is
deterministic, in that the output is determined by the input.

An EFFECTIVE procedure is one that always terminates after some finite
amount of time, no matter what the input.

A PROGRAM is simply a computational procedure specified in a formal
programming language.

Observations: Not all programs are algorithms: they might not be
effective. For instance, an operating system (ideally) never
terminates. But any program that is guaranteed to always terminate, is
an algorithm.  Conversely, not all algorithms are programs: they might
not be specified in a programming language.

Having all this clarity is nice, but it tells us little about what an
algorithm (or program) actually does.  Roughly speaking, an algorithm
solves a problem; this requires further definitions.



     PROBLEMS and PROBLEM-INSTANCES

A PROBLEM (or problem-class) consists of three things:

1. Specification of an input type, I
2. Specification of an output type, O
3. Specification of a relation R between input and output.

Example: < finite-list-of-integers, integer, least-element >
represents the ``least element'' problem class, where intuitively the
problem is to find the least element of a list of integers. Note that
the desired result, the least element, depends (only) on the input
list. And < integer, {yes,no}, is-prime > represents the is-prime
problem (ie, given an integer, decide whether or not it is prime).

It is easy to write a program (or algorithm) that finds the least
element of a given list of integers; we call any such algorithm a
SOLUTION of the least-element problem.

In general, an algorithm A ``solves'' problem < I,O,R > if for
every input i of type I, A[i] (the result of applying A to input i)
has relation R to i.

A problem P is SOLVABLE if there exists at least one algorithm that
solves P.

It turns out that some problems are unsolvable. But even among those
that are solvable, some are solvable by ``fast'' algorithms and some
are not.  Just what this might mean, and how we can use such ideas, is
the main topic of this course.

The most famous (and the first ever discovered, by Alan Turing)
example of an unsolvable problem is the HALTING problem.  This is the
problem of deciding (outputting a yes or a no) whether an program
and some data, both given as input, will halt if the program is run on
that data. Note what this means: that there cannot ever be, even in
principle, an algorithm that always correctly outputs the right answer
for all programs and data (yes for halt, no otherwise). It is
astonishing that such a result could be proven, and yet Turing's proof
ofit is relatively short and straightforward, but with a clever
twist. It is also, in some respects, unfortunate, since if there were
an algorithm to solve the halting problem, it could be very useful,
telling the programmer in advance whether any particular program
(running on particular data) will eventually halt or loop forever.

Another problem of great interest is the Natural Language Problem (NLP, also
used to refer to "natural-language processing", which is what the
natural language problem tries to solve). This can be stated as follows:

< English-text, a program, the program does what the text says to do >

In order to solve NLP, an algorithm would have to be able to
"understand" English very well. That is, it would have to parse the
text, find the sentences that represent commands, figure out exactly
what each command asks for, and then produce a program to carry out
those commands.  This is admittedly a bit vague; essentially it means
that, with such an algorithm -- if implemented as a program -- we
could simply talk to our computers and they'd be able to do what we
ask them to, instead of our having to write (other) programs for each
thing we want done. This is a fascinating challenge, not only because
it would eliminate lots of the drudgery of programming but also
because it might represent a potentially major advance in our
understanding of human language use, since we know very little of how
we ourselves manage to communicate.  NLP is a major part of the field
of artificial intelligence, which includes attempts to understand the
nature of intelligence well enough to build programs that exhibit
human-level abilities.  There are some who believe NLP is unsolvable
-- that there cannot be, even in principle, an algorithm that performs
this way.  And there are many others who are trying hard to find such
an algorithm. If we restrict the problem to special cases (or
instances, to use the expression defined below) then the problem is
sometimes solvable, eg if the English text is required to consist of
only one simple sentence using only a small vocabulary.

If a problem is solvable by one algorithm, then most likely it is
solvable by many different algorithms. A question that arises then is,
which algorithm is "best"?  What this might mean is a major aspect of
this course. Certain things some to mind easily: how "fast" the
algorithm is; how much memory (and other resources) it requires; how
easy it is implement; whether it requires special hardware.  We will
consider all of these, but primarily we will be concerned with the
first: speed, often described in terms of "runtime", but even that
expression needs much refinement before it becomes useful.  All of
these considerations can be lumped together under the broad term of
"efficiency".

An INSTANCE of a problem P = < I,O,R > is given by specifying a
single input i from I.  Thus < 5, {yes,no}, is-prime > is an
instance of the is-prime problem, and < < 3,2,7 > , integer,
least-element > is an instance of the least-element problem.

It is very important to distinguish a problem-instance from its problem
(class).



     DECISION PROBLEMS

Consider a problem < I,O,R > for which O = {yes,no} and where, for
each i, either ``yes'' or ``no'' but not both, has the relation R to
i. Any such problem is called a DECISION PROBLEM.  Such problems are
an important subclass of problems; we think of a decision problem
intuitively as asking us, for a given input i, to determine (or
decide) whether i is ``yes''-related, or ``no''-related. In other
words, R in effect makes some sort of claim about i that is either
true (yes) or false (no).

Example: < integer, {yes,no}, is-prime > is a decision problem, that
asks, for each integer i, whether i is prime, as we saw just above.

Example: The HALTING Problem.



     INFINITE AND FINITE DECISION PROBLEMS

Some problems have only a finite number of instances (i.e., I is
finite). Such a problem is called a finite problem. Any finite
DECISION problem < I,O,R > is solvable.  For let I = < i_1,i_2,...i_n >,
and let < v_1,v_2,...,v_n > be the corresponding correct truth-values
(or yes-no's) that R specifies.  Then the algorithm A =
{< i_1,v_1 >,< i_2,v_2 >,...,< i_n,v_n >} correctly solves the problem. 
That is, A simply consists of a lookup table of correct answers for each
instance of the problem; think of it as a long case statement.

This may seem like cheating. There seems to be no work, no computing,
no figuring-out of the answers. Or rather, it seems that someone has
to look carefully at R ahead of time, and figure out the answers, and
then code them into A. However, note that for a problem to be solvable,
an algorithm must exist; we do not need to find it ourselves, nor does
it have to be found at all -- it simply must exist in the mathematical
sense of being possible in principle. And since there are only
finitely many inputs (n of them) and two outputs (yes and no) then
there are only 2^n conceivable lists of pairings between I and O, and
since R determines an answer in O for each i in I, then exactly one of
these lists of pairings gets it right, and that one will be A. We
don't need to find it, it is ``there'' as a possibility in principle.

But if P = < I,O,R > were an infinite decision problem (i.e, if I were
infinite), then there is no automatic guarantee that P is solvable. If
we use the same method we just saw for finite decision problems, we
would get an "algorithm" A with an *infinite* case statement, and this
is not an algorithm at all; so for such problems we must in fact have
a method that does some "computing" of the answer instead.

Some infinite decision problems are solvable, of course. For instance,
the is-prime one above certainly is: it is easy to write an algorithm
to test an input integer for primality. (However, although it is easy
to *write*, all such algorithms that have been discovered tend to
*run* very slowly. This important distinction will come up again.)

(Also, if P has a finite I but is not a decision problem, again it
might be that P is unsolvable, simply because for some instances i,
there might be no output at all that satisfies R).

Web Accessibility