(Robert I. Soare, 1987) gives an informal definition of an algorithm (or an algorithmic function), shown in def-algorithm-inf, formally, an algorithm is equivalent to a partial recursive function.
informally, an algorithm (for a function
on
) is a finite set of instructions which, given an input
, yields after a finite number of steps an output
. the algorithm must specify how to obtain each step in the calculation from the previous steps and from the input. the algorithm may only yield a partial function. for example, let
, where
is some polynomial with integer coefficients and where
denotes "the least
such that
". now
may be defined for some but not all values of
. an algorithmic partial function which is defined on all arguments (i.e., which is total) is called recursive or computable.
for the sake of definiteness (Martin Davis, Ron Sigal, Elaine J. Weyuker, 1994) gives two precise mathematical formulations of computable functions, the recursive functions and the turing computable functions. these and numerous other formal definitions give rise to the same class of functions which is now commonly accepted as corresponding to the informal class of algorithmically computable functions. for our purposes it is immaterial which formal definition is chosen.