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:

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?