Turingmaschinen als Coalgebren

Ich möchte eine Umfrage über die Methode zur Darstellung der Dynamik staatlicher Berechnungen im Rahmen von Kohlegebren schreiben. Bisher habe ich es geschafft, Artikel über Kohlegebra-Darstellungen von DFA, NFA, Mealy-Maschinen, Moore-Maschinen, kontextfreien Grammatiken und sogar einfachen Quantensystemen zu finden. Ich habe keine gute Quelle gefunden, um eine Turingmaschine als Kohlegebra darzustellen.

Irgendwelche Quellen / Gedanken?

Vielen Dank!

Pavlovic et al. Anzeigen von Turingmaschinen über ein binäres Alphabet als Kohlegebren für den Funktor . Die Symbole und repräsentieren dabei die .$\lambda X. \, 2 \times \mathcal{P}_{\mathrm{fin}}(X \times 2 \times \{\lhd,\rhd\})^2$$\lhd$$\rhd$

Bart Jacobs hat in "Coalgebraic Walks, In Quantum and Turing Computation" einen Ansatz unter Verwendung einer Monade vorgestellt. Er präsentiert eine Turingmaschine mit Zuständen als Kohlegebra für functor auf Sets. Alternativ können Sie den Typ , der das Band und die Position des Kopfes auf dem Band darstellt. Eine Turing-Maschine mit Zuständen ist dann auch ein Endomorphismus auf in der Kategorie der Verknüpfungshalbgitter oder Matrix der Kohlegebren .$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})$

Der fortschrittlichste Ansatz für Turing-Maschinen (und auch Push-Down-Automaten) wird von Goncharov et al. Die Autoren präsentieren Monaden für diese Maschinentypen durch Generatoren und Gleichungen, sie zeigen, wie rationales Verhalten durch Fixpunktausdrücke dargestellt wird, und beweisen verschiedene andere Eigenschaften. Insbesondere untersuchen sie auch die Sprachsemantik solcher Maschinen.

Ich hoffe das hilft.