Prev Up Next
Go backward to 3.3 Computer Program
Go up to 3 An Example of Concept Webs: Programming Concepts
Go forward to 3.5 Definite (Nongeneric) Computational Method

3.4 Generic Computational Method

A generic computational method (a.k.a. an abstract computational method) is a method for solving a specific type of problem by means of a finite set of steps operating on inputs, which are quantities given to it before execution of the steps begins, and producing one or more outputs, which have a specified relation to the inputs. The number of steps in the method is required to be not only finite but also independent of the inputs. The method is also required to be resource constrained, which means there are requirements on all operations of all steps of the method that constrain the resources (time, space) that can used in executions of the method.

Execution of steps may repeat other steps, so that although the set of steps is finite, executions of them may produce an infinite sequence of steps--finite termination is not a requirement (it is a requirement of the generic algorithm concept). Nonterminating computational methods are useful, such as computer operating systems or event-driven simulation systems. Even though the execution of such methods does not terminate, we are still generally interested in bounding the number of steps taken in producing some partial output (as in proving response-time guarantees for an operating system).

In order to bound the resources--time and space--consumed during an execution of the method, we first need bounds on the resources consumed by individual steps. This motivates the resource-constraint requirement on generic computational methods.

Effectiveness of a computational method is the property that all operations of all steps of the method "must be sufficiently basic that they can in principle be done exactly and in a finite length of time." (Knuth [3] adds "by someone using pencil and paper," but it is a philosophical question whether humans have any computational capability beyond the effectiveness of machines.) As defined here, effectiveness of generic computational methods follows from their resource constraint requirement.


musser@cs.rpi.edu

Prev Up Next