<p><a href="https://dblp.org/rec/bib/conf/amast/PavlovicMW06" rel="nofollow noreferrer">Pavlovic et al.</a> view Turing machines over a binary alphabet as coalgebras for the functor <span class="math-container">$\lambda X. \, 2 \times \mathcal{P}_{\mathrm{fin}}(X \times 2 \times \{\lhd,\rhd\})^2$</span>. The symbols <span class="math-container">$\lhd$</span> and <span class="math-container">$\rhd$</span> represent thereby the tape moves.</p>

<p><a href="https://dblp.org/rec/bib/conf/fossacs/Jacobs11" rel="nofollow noreferrer">Bart Jacobs</a> has presented in "Coalgebraic walks, in quantum and Turing computation" an approach by using a monad. He present a Turing machine with <span class="math-container">$n$</span> states as a coalgebra for functor <span class="math-container">$\mathcal{P}_{\mathrm{fin}}[n]$</span> on sets. Alternatively, consider the type <span class="math-container">$\mathbb{T} = 2^\mathbb{Z} \times \mathbb{Z}$</span> that represents the tape and the position of the head on the tape. A Turing machine with <span class="math-container">$n$</span> states is then also an endomorphism   on <span class="math-container">$2^n \otimes \mathcal{P}_{\mathrm{fin}}(\mathbb{T})$</span> in the category of join-semilattices, or an <span class="math-container">$n \times n$</span>-matrix of coalgebras <span class="math-container">$\mathbb{T} \to \mathcal{P}_{\mathrm{fin}}(\mathbb{T})$</span>.</p>

<p>The most advanced approach to Turing machines (and also push-down automata) is given by <a href="https://dblp.org/rec/bib/journals/corr/GoncharovMS14" rel="nofollow noreferrer">Goncharov et al.</a> 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.</p>

<p>I hope this helps.</p>

CC BY-SA 4.0
2019-04-23T22:38:42.157Z
2019-05-03T08:25:13.880Z
2019-05-03T08:25:13.880Z
Henning Basold
<p>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.</p>

<p>Any sources/thoughts?</p>

<p>Thanks!</p>

<automata-theory><turing-machines><algebra><automated-theorem-proving>
Turing Machines as Coalgebras
Eric Bond
# Turing Machines as Coalgebras

(Asked by: username_0 on 2019-04-20)

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!

**Tags:** automata-theory, turing-machines, algebra, automated-theorem-proving


---

## 1 answers

### Answer by username_1 on 2019-04-23. Score: 6 | Accepted answer

[Pavlovic et al.](https://dblp.org/rec/bib/conf/amast/PavlovicMW06) 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](https://dblp.org/rec/bib/conf/fossacs/Jacobs11) 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.](https://dblp.org/rec/bib/journals/corr/GoncharovMS14) 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.


---

