Informal Properties of an Algorithm
(from Rogers, 1987)
1.
An algorithm is given as a set of instructions of finite size.
(cf. program)
2. There is a computing agent, usually human, which can react
to the instructions and carry out the computations. (cf.
logical elements, circuitry)
3. There are facilities for making, storing, and retrieving steps
in a computation. (cf. storage memory)
4. Let P be a set of instructions as in 1 and L be a computing
agent as in 2. Then L reacts to P in such a way that, for any
given input, the computation is carried out in a discrete stepwise
fashion, without use of continuous methods or analogue devices.
(cf. digital)
5. L reacts to P in such a way that a computation is carried
forward deterministically, without resort to random methods or
devices, e.g., dice. (cf. mechanistic)
6. Is there to be a fixed finite bound on the size of inputs?
(F: No; P: Yes)
7. Is there to be a fixed finite bound on the size of a set of
instructions? (F: No; P: Yes)
8. Is there to be a fixed finite bound on the amount of "memory"
storage space available? (F: No; P: Yes)
9. Is there to be, in any sense, a fixed finite bound on the
capacity or ability of the computing agent L? (F: Yes; P: Yes)
10. Is there to be, in any way, a bound on the length of a computation?
more specifically, should we require that the length of a particular
computation be always less than a value which is "easily
calculable" from the input and from the set of instructions
P? To put it more informally, should we require that, given any
input and given any P, we have some idea, "ahead ot time,"
of how long the computation will take? (F: No) |
1-5 are
usually taken as inherent to the informal idea of an algorithm.
[ F indicates answer motivated by formal considerations and P
motivated by practical considerations.]
|
|
