Computational problem in the SCI hierarchy

A computational problem is a quadruple $(\Xi ,\Omega ,\mathcal{M},\Lambda )$: the primary set $\Omega$ contains the inputs, $\Lambda$ is the family of permitted evaluation functions, $(\mathcal{M},d)$ is the output metric space, and $\Xi :\Omega \to \mathcal{M}$ is the problem function.

A general algorithm reads only finitely many evaluations for each input, its output depends only on their values, and another input giving those same values causes it to request the same finite information. No restriction is placed on the finite computation performed after reading the data.

An arithmetic algorithm is a general algorithm in the SCI hierarchy whose finite computation uses only finitely many arithmetic operations and comparisons on the evaluated data.

In the ${\Delta }_1$ inexact-information model, a requested evaluation $\lambda (A)$ at precision $m$ may be replaced by any value within $2^{-m}$ of the exact value. An algorithm must work for every admissible stream of such approximations.

For a map $F:X\to X$, a perfect measurement device may query any $x\in X$ and any precision $m$, receiving $y$ with $d(F(x),y)\le 2^{-m}$. It is perfect in the information-theoretic sense: there is no sampling restriction and measurement error can be made arbitrarily small, although every terminating algorithm makes only finitely many queries.