# 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