[FOM] What Is an Algorithm?

[Vaughan Pratt]

Victor Makarov's view of "algorithm," as in his

>However, I am not completely satisfied with these answers [Moschovakis:
>algorithm = definable recursor, Gurevich: algorithm = abstract state machine],
>because before writing an algorithm we must already know objects (numbers,
>strings, graphs, ...) the algorithm is working with.
>... the concept of algorithm is 
>inseparable from the concept of mathematical theory and actually is 
>subordinate to it because before the development of an algorithm we should 
>have a mathematical theory. An algorithm is a definition (of some special 
>kind) in this theory.

is definitely closer to how those of us who actually write algorithms and
prove that they perform as advertised think of them.

The only thing I would add is that practitioners of the art of algorithms
usually aim for a compromise between naturality and abstractness in their
choice of data structures: naturality for the sake of a good fit to the
intended application, abstractness for the sake of generality of application.

There is a tendency for programmers, those responsible for generating
compilable code in an industrial-strength programming language, to let
naturality color their datatypes, e.g. distinguishing between {0,1} as
the datatype for Boolean rings (= arithmetic mod 2) vs. {false,true} as the
datatype for Boolean algebras.  Algorithmists push in the opposite direction,
trying to minimize algorithmically insignificant variations of this kind but
at the same time trying to avoid falling into the Turing tarpit of Turing
tapes as the only datatype needed.  This latter is one of the things that
might differentiate an algorithmist from a complexity theorist, though this
is admittedly a very difficult boundary to draw convincingly.

Vaughan Pratt