Hostname: page-component-745bb68f8f-lrblm Total loading time: 0 Render date: 2025-01-22T08:48:05.111Z Has data issue: false hasContentIssue false
  • English
  • Français

The monoidal structure of Turing machines†

Published online by Cambridge University Press:  28 February 2013

MIKLÓS BARTHA
MIKLÓS BARTHA*
Affiliation:
Department of Computer Science, Memorial University of Newfoundland St. John's, NL, Canada Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Indexed monoidal algebras are introduced as an equivalent structure for self-dual compact closed categories, and a coherence theorem is proved for the category of such algebras. Turing automata and Turing graph machines are defined by generalising the classical Turing machine concept so that the collection of such machines becomes an indexed monoidal algebra. On the analogy of the von Neumann data-flow computer architecture, Turing graph machines are proposed as potentially reversible low-level universal computational devices, and a truly reversible molecular size hardware model is presented as an example.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 23 , Special Issue 2: Developments In Computational Models 2010 , April 2013 , pp. 204 - 246
Copyright
Copyright © Cambridge University Press 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

This work was partially supported by the Natural Science and Engineering Research Council of Canada.

References

Abramsky, S. (2005a) A structural approach to reversible computation. Theoretical Computer Science 347 441–464.CrossRefGoogle Scholar
Abramsky, S. (2005b) Abstract Scalars, Loops, and Free Traced and Strongly Compact Closed Categories. In: CALCO 2005. Springer-Verlag Lecture Notes in Computer Science 3629 1–31.CrossRefGoogle Scholar
Abramsky, S. and Coecke, B. (2004) A categorical semantics of quantum protocols. In: Proceedings of the 19th Annual Symposium on Logic in Computer Science, LICS 2004, IEEE Computer Society Press 415–425.CrossRefGoogle Scholar
Abramsky, S., Haghverdi, E. and Scott, P. (2002) Geometry of Interaction and Linear Combinatory Algebras. Mathematical Structures in Computer Science 12 625–665.CrossRefGoogle Scholar
Arnold, A. and Dauchet, M. (1978–79) Théorie des magmoïdes. In: RAIRO – Theoretical Informatics and Applications 12 235–257 and 13 135–154.Google Scholar
Bartha, M. (1987a) A finite axiomatization of flowchart schemes. Acta Cybernetica 8 (2)203–217. (Also available online at http://www.cs.mun.ca/~bartha/linked/flow.pdf.)Google Scholar
Bartha, M. (1987b) An equational axiomatization of systolic systems. Theoretical Computer Science 55 265–289.CrossRefGoogle Scholar
Bartha, M. (1992) An algebraic model of synchronous systems. Information and Computation 97 97–131.CrossRefGoogle Scholar
Bartha, M. (2008) Simulation equivalence of automata and circuits. In: Local Proceedings, 12th International Conference on Automata and Formal Languages, Balatonfüred, Hungary 86–99. (Available online at http://www.cs.mun.ca/~bartha/linked/afl08.pdf.)Google Scholar
Bartha, M. (2009) Equivalence relations of Mealy automata. In: Local Proceedings, First Workshop on Non-Classical Models of Automata and Applications, Wroclaw, Poland 31–45. (Available online at http://www.cs.mun.ca/~bartha/linked/wroc.pdf.)Google Scholar
Bartha, M. (2012) Quantum Turing automata. Proceedings, 8th International Workshop on Developments of Computational Models (DCM 2012). Electronic Proceedings in Theoretical Computer Science (in press).Google Scholar
Bartha, M. and Gombás, É. (1991) The Gallai–Edmonds algebra of graphs. Technical Report 9105, Department of Computer Science, Memorial University of Newfoundland, St. John's, NL, Canada. (Available online at http://www.cs.mun.ca/~bartha/linked/g-e.pdf.)Google Scholar
Bartha, M. and Jürgensen, H. (1989) Characterizing finite undirected multigraphs as indexed algebras. Technical Report 252, Department of Computer Science, The University of Western Ontario, London, Ontario, Canada. (Available online at http://www.cs.mun.ca/~bartha/linked/ind.pdf.)Google Scholar
Bartha, M. and Krész, M. (2003) Structuring the elementary components of graphs having a perfect internal matching. Theoretical Computer Science 299 179–210.CrossRefGoogle Scholar
Bartha, M. and Krész, M. (2006) Deterministic soliton graphs. Informatica 30 281–288.Google Scholar
Bartha, M. and Krész, M. (2010) Soliton circuits and network-based automata: review and perspectives. In: Martín-Vide, C. (ed.) Mathematics, Computing, Language, and Life: Frontiers in Mathematical Linguistics and Language Theory 2, Scientific Applications of Language Methods, Imperial College Press 585–631.Google Scholar
Bartha, M. and Krész, M. (2011) Molecular switching by Turing automata. In: Local Proceedings, Third Workshop on Non-Classical Models of Automata and Applications, Milan, Italy 31–45. (Available online at http://www.cs.mun.ca/~bartha/linked/mol.pdf.)Google Scholar
Bauderon, M. and Courcelle, B. (1987) Graph expressions and graph rewritings. Mathematical Systems Theory 20 83–127.CrossRefGoogle Scholar
Bennett, C. H. (1973) Logical reversibility of computation. IBM Journal of Research and Development 17 (6)525–532.CrossRefGoogle Scholar
Bloom, S. L. and Ésik, Z. (1985) Axiomatizing schemes and their behaviors. Journal of Computer and System Sciences 31 375–393.CrossRefGoogle Scholar
Bloom, S. L. and Ésik, Z. (1993) Iteration Theories: The Equational Logic of Iterative Processes, Springer-Verlag.CrossRefGoogle Scholar
Burstall, R. M., Goguen, J. A. and Tarlecki, A. (1989) Some fundamental tools for the semantics of computation. Part 3: Indexed categories. Report ECS-LFCS-89-90, Laboratory for Foundations of Computer Science, University of Edinburgh, Edinburgh, United Kingdom.Google Scholar
Căzănescu, V. E. and Ştefănescu, Gh. (1990) Towards a new algebraic foundation of flowchart scheme theory. Fundamenta Informaticae 13 171–210. (Also appeared as: INCREST Preprint Series in Mathematics 43, Bucharest, Romania 1987.)CrossRefGoogle Scholar
Dassow, J. and Jürgensen, H. (1990) Soliton automata. Journal of Computer and System Sciences 40 154–181.CrossRefGoogle Scholar
Davidov, A. S. (1985) Solitons in Molecular Systems, Reidel, Dordrecht.CrossRefGoogle Scholar
D'Hondt, E. and Panangaden, P. (2006) Quantum weakest preconditions. Mathematical Structures in Computer Science 16 (3)429–451.CrossRefGoogle Scholar
Elgot, C. C. (1975) Monadic computations and iterative algebraic theories. In: Rose, H. E. and Shepherdson, J. C. (eds.) Logic Colloquium 1973, Studies in Logic and the Foundations of Mathematics 80, North Holland 175–230.Google Scholar
Engelfriet, J. and Vereijken, J. J. (1997) Context-free graph grammars and concatenation of graphs. Acta Informatica 34 773–803.CrossRefGoogle Scholar
Freyd, P. and Yetter, D. (1992) Coherence theorems via knot theory. Journal of Pure and Applied Algebra 78 49–76.CrossRefGoogle Scholar
Girard, J.-Y. (1987) Linear logic. Theoretical Computer Science 50 1–102.CrossRefGoogle Scholar
Girard, J.-Y. (1989) Geometry of Interaction I: Interpretation of System F. In: Ferro, R.et al. (eds.) Logic Colloquium'88, North-Holland221–260.Google Scholar
Girard, J.-Y. (1990) Geometry of Interaction II: Deadlock-free Algorithms. In: Martin-Lof, P. and Mints, G. (eds.) COLOG-88. Springer-Verlag Lecture Notes in Computer Science 417 76–93.CrossRefGoogle Scholar
Hines, P. (2003) A categorical framework for finite state machines. Mathematical Structures in Computer Science 13 451–480.CrossRefGoogle Scholar
Hyland, M. (1997) Game semantics. In: Pitts, A. M. and Dybjer, P. (eds.) Semantics and Logics of Computation, Cambridge University Press 131–194.CrossRefGoogle Scholar
Joyal, A. and Street, R. (1991) The geometry of tensor calculus I. Advances in Mathematics 88 (1)55–112.CrossRefGoogle Scholar
Joyal, A., Street, R. and Verity, D. (1996) Traced monoidal categories. Mathematical Proceedings of the Cambridge Philosophical Society 119 447–468.CrossRefGoogle Scholar
Katis, P., Sabadini, N. and Walters, R. F. C. (2002) Feedback, trace, and fixed-point semantics. Theoretical Informatics and Applications 36 181–194.CrossRefGoogle Scholar
Kelly, G. M. (1982) Basic Concepts of Enriched Category Theory, London Mathematical Society Lecture Notes Series 64, Cambridge University Press.Google Scholar
Kelly, G. M. and Laplaza, M. L. (1980) Coherence for compact closed categories. Journal of Pure and Applied Algebra 19 193–213.CrossRefGoogle Scholar
Kleene, S. C. (1956) Representation of events in nerve nets and finite automata. In: Shannon, C. E. and McCarthy, J. (eds.) Automata Studies, Princeton University Press 3–42.Google Scholar
Krész, M. (2007) Graph decomposition and descriptional complexity of soliton automata. Journal of Automata, Languages and Combinatorics 12 237–263.Google Scholar
Krész, M. (2008) Soliton automata with constant external edges. Information and Computation 206 1126–1141.CrossRefGoogle Scholar
Lafont, Y. (1989) Interaction nets. In: Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages 95–108.Google Scholar
Landauer, R. (1961) Irreversibility and heat generation in the computing process. IBM Journal of Research and Development 5 183–191.CrossRefGoogle Scholar
Leiserson, C. E. and Saxe, J. B. (1983) Optimizing synchronous systems. Journal of VLSI and computer systems 1 41–67.Google Scholar
Lovász, L. and Plummer, M. D. (1986) Matching Theory, North Holland.Google Scholar
Lutz, C. and Derby, H. (1982) Janus: A Time-Reversible Language. (Available online at http://tinyurl.com/janus82.)Google Scholar
MacLane, S. Lane, S. (1963) Natural associativity and commutativity. Rice University Studies 49 28–46.Google Scholar
Mac Lane, S. (1971) Categories for the Working Mathematician, Springer-Verlag.CrossRefGoogle Scholar
MacLane, S. Lane, S. and Paré, R. (1985) Coherence for bicategories and indexed categories. Journal of Pure and Applied Algebra 37 59–80.Google Scholar
Milner, R. (2009) The Space and Motion of Communicating Agents, Cambridge University Press.CrossRefGoogle Scholar
Roman, S. (2005) Advanced Linear Algebra, Springer-Verlag.Google Scholar
Selinger, P. (2009) A survey of graphical languages for monoidal categories. In: Coecke, B. (ed.) New Structures for Physics. Springer-Verlag Lecture Notes in Physics 813 289–355.CrossRefGoogle Scholar