Turing Automata and Graph Machines

Miklós Bartha
(Memorial University of Newfoundland)

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 generalizing 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.

In S. Barry Cooper, Prakash Panangaden and Elham Kashefi: Proceedings Sixth Workshop on Developments in Computational Models: Causality, Computation, and Physics (DCM 2010), Edinburgh, Scotland, 9-10th July 2010, Electronic Proceedings in Theoretical Computer Science 26, pp. 19–31.
Published: 9th June 2010.

ArXived at: http://dx.doi.org/10.4204/EPTCS.26.3 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org