Pavlovic et al. veja Máquinas de Turing sobre um alfabeto binário como barras de carvão para o functor λX.2×Pfin(X×2×{⊲,⊳})2 . Os símbolos ⊲ e ⊳ representam assim a fita se move.
Bart Jacobs apresentou em "Caminhadas coalgebraicas, em computação quântica e de Turing" uma abordagem usando uma mônada. Ele apresenta uma máquina de Turing com estados como uma coalgebra para o functor em conjuntos. Como alternativa, considere o tipo que representa a fita e a posição da cabeça na fita. Uma máquina de Turing com estados também é um endomorfismo em na categoria junção semilática ou matriz de barras de carvão .nPfin[n]T=2Z×Zn2n⊗Pfin(T)n×nT→Pfin(T)
A abordagem mais avançada para máquinas de Turing (e também autômatos push-down) é dada por Goncharov et al. Os autores fazem apresentações de mônadas para esses tipos de máquinas por geradores e equações, mostram como representam o comportamento racional por meio de expressões de ponto fixo e provam várias outras propriedades. Em particular, eles também estudam a semântica da linguagem dessas máquinas.
Eu espero que isso ajude.