I'm looking to write a survey on the method of representing the dynamics of state-based computation within the framework of coalgebras. So far I've managed to find papers on coalgebra representations of DFA, NFA, Mealy machines, Moore machines, context-free grammars, and even simple quantum systems. I have not found a good source for representing a Turing Machine as a coalgebra.
Any sources/thoughts?
Thanks!
Pavlovic et al. view Turing machines over a binary alphabet as coalgebras for the functor $\lambda X. \, 2 \times \mathcal{P}_{\mathrm{fin}}(X \times 2 \times \{\lhd,\rhd\})^2$. The symbols $\lhd$ and $\rhd$ represent thereby the tape moves.
Bart Jacobs has presented in "Coalgebraic walks, in quantum and Turing computation" an approach by using a monad. He present a Turing machine with $n$ states as a coalgebra for functor $\mathcal{P}_{\mathrm{fin}}[n]$ on sets. Alternatively, consider the type $\mathbb{T} = 2^\mathbb{Z} \times \mathbb{Z}$ that represents the tape and the position of the head on the tape. A Turing machine with $n$ states is then also an endomorphism on $2^n \otimes \mathcal{P}_{\mathrm{fin}}(\mathbb{T})$ in the category of join-semilattices, or an $n \times n$-matrix of coalgebras $\mathbb{T} \to \mathcal{P}_{\mathrm{fin}}(\mathbb{T})$.
The most advanced approach to Turing machines (and also push-down automata) is given by Goncharov et al. The authors give presentations of monads for these types of machines by generators and equations, they show how represent rational behaviour by means of fixed point expressions and prove various other properties. In particular, they also study the language semantics of such machines.
I hope this helps.
