Máquinas de Turing como Coalgebras

Estoy buscando escribir una encuesta sobre el método de representar la dinámica de la computación basada en el estado en el marco de las coalgebras. Hasta ahora, he logrado encontrar documentos sobre representaciones de coalgebra de DFA, NFA, máquinas Mealy, máquinas Moore, gramáticas libres de contexto e incluso sistemas cuánticos simples. No he encontrado una buena fuente para representar una máquina de Turing como coalgebra.

¿Alguna fuente / pensamiento?

¡Gracias!

Pavlovic y col. vea las máquinas de Turing sobre un alfabeto binario como coalgebras para el functor . Los símbolos y \ rhd representan por lo tanto los movimientos de la cinta.$\lambda X. \, 2 \times \mathcal{P}_{\mathrm{fin}}(X \times 2 \times \{\lhd,\rhd\})^2$$\lhd$$\rhd$

Bart Jacobs ha presentado en "Caminatas coalgebraicas, en computación cuántica y de Turing" un enfoque utilizando una mónada. Presentó una máquina de Turing con estados como coalgebra para functor en los sets. Alternativamente, considere el tipo que representa la cinta y la posición del cabezal en la cinta. Una máquina de Turing con estados es, entonces, también un endomorfismo en en la categoría de unir semilattices, o un -matriz de coalgebras .$n$$\mathcal{P}_{\mathrm{fin}}[n]$$\mathbb{T} = 2^\mathbb{Z} \times \mathbb{Z}$$n$$2^n \otimes \mathcal{P}_{\mathrm{fin}}(\mathbb{T})$$n \times n$$\mathbb{T} \to \mathcal{P}_{\mathrm{fin}}(\mathbb{T})$

Goncharov et al., Ofrecen el enfoque más avanzado para las máquinas de Turing (y también los autómatas push-down) . Los autores dan presentaciones de mónadas para este tipo de máquinas mediante generadores y ecuaciones, muestran cómo representan el comportamiento racional mediante expresiones de punto fijo y prueban otras propiedades. En particular, también estudian la semántica del lenguaje de tales máquinas.

Espero que esto ayude.