Machine := tuple of devices (d_{1}, …, d_{k})

Device \begin{cases}Realm := the set of states \\ Repetory := the set of operations \end{cases}

Operation := a partial function on the realm

Program

on machine M = (d_{1}, …, d_{k})

{Initializer α = (α_{1}, …, α_{k}) where α_{i} is a function from the possible arguments of P into the realm of d_{i} finite set I of instructions (f_{1}, …, f_{k}) where f_{i} is an operator of device d_{i} or the special operator NOOP, doing nothing Terminator ω = (ω_{1}, …, ω_{k}) where ω_{i} is a relation between the realm of d_{i} and the possible results of P

argument ⟶ program ⟶ result

The argument of a program P can be a graph, a number, etc., and likewise for the result.

The initializer tells how the argument is encoded as initial state for each of M’s devices.

The instructions tell how P goes from state to state.

The terminator tells for each of M’s devices which are its final states, and decodes a combination of final states into a result of P.

Configuration := tuple of states (s_{1}, …, s_{k}) of M’s devices, representing global state

History := \begin{matrix}(x, α, C_{0}, π_{1}, C_{1}, …, C_{n−1}, π_{n}, C_{n}, ω, y) with \\ xα = C_{0}, C_{i}α_{i+1} = C_{i+1} and C_{n}ω = y. \end{matrix}

Transfer relation: x ↦^{τ} y Partial History := (x, α, C_{0}, π_{1}, C_{1}, …, C_{n−1}, π_{n}, C_{n}) Infinite History := (x, α, C_{0}, π_{1}, C_{1}, π_{2}, C_{2}, …)