Mesin Turing sebagai Coalgebras

Saya mencari untuk menulis survei tentang metode yang mewakili dinamika perhitungan berbasis negara dalam kerangka kerja coalgebras. Sejauh ini saya sudah berhasil menemukan makalah tentang representasi coalgebra DFA, NFA, mesin Mealy, mesin Moore, tata bahasa bebas konteks, dan bahkan sistem kuantum sederhana. Saya belum menemukan sumber yang bagus untuk merepresentasikan Mesin Turing sebagai batubara.

Adakah sumber / pemikiran?

Terima kasih!

Pavlovic et al. lihat mesin Turing melalui alfabet biner sebagai coalgebras untuk functor . Simbol dan dengan demikian mewakili pita bergerak.$\lambda X. \, 2 \times \mathcal{P}_{\mathrm{fin}}(X \times 2 \times \{\lhd,\rhd\})^2$$\lhd$$\rhd$

Bart Jacobs telah disajikan dalam "berjalan Coalgebraic, dalam perhitungan kuantum dan Turing" pendekatan dengan menggunakan monad. Dia menyajikan mesin Turing dengan menyatakan sebagai coalgebra untuk functor pada set. Atau, pertimbangkan jenis yang mewakili pita dan posisi kepala pada pita. Mesin Turing dengan state juga merupakan endomorfisme pada dalam kategori join-semilattice, atau -matrix dari 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})$

Pendekatan paling canggih untuk mesin Turing (dan juga push-down automata) diberikan oleh Goncharov et al. Para penulis memberikan presentasi monads untuk jenis-jenis mesin oleh generator dan persamaan, mereka menunjukkan bagaimana merepresentasikan perilaku rasional melalui ekspresi titik tetap dan membuktikan berbagai sifat lainnya. Secara khusus, mereka juga mempelajari semantik bahasa mesin tersebut.

Saya harap ini membantu.