# Turing Machines as Coalgebras

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})$$.