Definition:Computational Method

From ProofWiki
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


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