# Definition:Computational Method

Jump to navigation
Jump to search

## Definition

A **computational method** is an ordered quadruple $\left({Q, I, \Omega, f}\right)$ in which:

- $Q$ is a set representing the
**states of the computation** - $I$ is a set representing the
**input to the computation** - $\Omega$ is a set representing the
**output from the computation** - $f: Q \to Q$ is a mapping representing the
**computational rule**

subject to the following constraints:

- $I \subseteq Q$ and $\Omega \subseteq Q$
- $\forall x \in \Omega: f \left({x}\right) = x$

### Computational Sequence

Each $x \in I$ defines a **computational sequence** $x_0, x_1, x_2, \ldots$ as follows:

- $x_0 = x$
- $\forall k \ge 0: x_{k+1} = f \left({x_k}\right)$

## Also see

- Definition:Algorithm: a
**computational method**which terminates in finitely many steps for all $x \in I$.

## Historical Note

The definition provided here for computational method is very nearly the same as that given by Andrey Andreyevich Markov Jr. in his *The Theory of Algorithms* (1954).

## Sources

- 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.1$: Algorithms