# Computation model

Given enough time, a machine computes a function in \(I \to O\) where \(I\) and \(O\) are the machine’s input type and output type, respectively. We are also interested in the *steps* of the machine, but not in the details. We thus give such machine a *state* of type \(S\), and a *step function* in \(S \to S\). We need to encode the input into the initial state, so we need an input encoding function in \(I \to S\). The same thing holds for the output; we need an output decoding function in \(S \to O\). This abstraction transforms the problem of determining the *computability* of \(m\) into the problem of determining the existence of \(o\), \(s\), and \(i\) such that \[
\begin{align*}
m &= o \circ s^\infty \circ i
\\ m &: I \to O
\\ o &: S \to O
\\ s &: S \to S
\\ i &: I \to S
\end{align*}
\] and \(I\), \(O\), and \(S\) are countable, where we have taken some liberty with the notation: \[
s^\infty~x = \lim_{n \to \infty} s^n~x.
\] That limit only exists if the orbit of \(s\) starting at \(x\) has loop. Realistic computation models restrict \(s\) (otherwise every machine could be an oracle).

Formally, a *machine* \(m\) has:

- input type \(Input~m = I\);
- state type \(State~m = S\);
- output type \(Output~m = O\);
- input embedder \(input~m = i\) having type \(I \to S\);
- step function \(step~m = f\) having type \(S \to S\);
- output extractor \(output~m = o\) having type \(S \to O\).

A computation on machine \(m\) starts with initial state \(x\) containing an encoding of the input, and then goes to the state \(f~x\), and then goes to the state \(f~(f~x)\), and so on until the computation terminates, where \(f = step~m\).

\((S,f)\) is a mono-unary algebra (also called *unar*; a type and an endofunction on that type). This unar is the essence of the machine as the unar determines the power of the machine. In theory, usually the state space \(S\) is countable. In the real world, a machine has a finite (but very large) state space.

We define the *computation graph* \((V,E)\) where \(V = S\) and \(E = f\). Thus the unar and the computation graph are isomorphic; indeed every unar forms a directed graph. We then define *computation* as a path in the graph. A computation begins at an initial state and ends at a terminal state. An state \(s\) is *initial* iff there exists \(x\) such that \(i~x = s\). A *terminal state* is a fixpoint of the step function. A state \(s\) is terminal iff \(s = f~s\).

We can talk about computation using graph terminology or iteration terminology. The orbit of the step function starting at \(x\) is the same as the path of the computation graph starting at \(x\).

## Other models are special cases of this model

We get a deterministic finite automaton if we let \(S\) be the set of all input-state pairs and \(f\) be the automaton’s transition function. We get a Turing machine if we let \(S\) be the set of the machine’s states and \(f\) be the Turing machine’s transition function. We get lambda calculus if we let \(S\) be the set of all terms and \(f\) be \(\beta\)-reduction.

A machine is therefore a transition system; it is also a discrete dynamical system.

A terminating computation looks like this: \[ x,~f~x,~f~(f~x),\ldots,~y,~y,~y,\ldots \] which is to say that the orbit of the step function has a cycle of period one, or to say that the path in the computation graph has a loop (cycle of length one). In this case, we define the \(w\)-function as \(w~f~x = y\). Otherwise, \(w~f~x\) is undefined.

The *function a machine computes* is \(o \circ w~f \circ i\). The function \(m\) computes is \(fun~m : Input~m \to Output~m\): \[
fun~m = output~m \circ w~(step~m) \circ input~m.
\] Two machines \(m\) and \(n\) compute the same function iff \(fun~m = fun~n\).

An unanswered question: What property of \(f\) implies what property of \(w~f\), or the other way around?

https://en.wikipedia.org/wiki/Iterated_function