Concurrent Turing Machines

• Autorzy: Farwer B. , Kudlek M. , Rölke H.
• Języki publikacji: EN

Abstrakty

EN

We define Concurrent Turing Machines (CTMs) as Turing machines with Petri nets as finite control. This leads to machines with arbitrary many tape heads, thus subsuming any class of (constant) k-head Turing machines. Space, time, and head complexity classes are introduced and discussed showing the difference of various acceptance conditions that are defined for CTMs. Nevertheless, we show that CTMs can be simulated by TMs. Concurrent Turing machines correspond to a class of multiset rewriting systems. The definition of a CTMs as a rewrite theory avoids the need for encoding multisets as words and using an equivalence relation on configurations. Multiset rewriting lends itself to be used in rewriting systems and tools like the rewriting engine Maude. For the rewriting system, a configuration is given by a varying sequence of strings and multisets.

Słowa kluczowe

EN

Concurrent Turing Machines (CTMs); Petri net

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 79, nr 3-4
• Strony: 303--317
• Opis fizyczny: bibliogr. 8 poz.

Twórcy

autor

Farwer B.

autor

Kudlek M.

autor

Rölke H.

• Durham University, Department of Computer Science, South Road, Durham DHI 3LE, U.K.,

Bibliografia

• [1] M. Clavel, F. Durán, S. Eker, P. Lincoln, N.Martí-Oliet, José Meseguer, and J. Quesada. Maude: Specification and Programming in Rewriting Logic, 1999.
• [2] A. Hemmerling. Systeme von Turing-Automaten und Zellularräume auf rahmbaren pseudomustermengen. Journal of Information Processing and Cybernetics EIK, 15:47-72, 1979.
• [3] O. Kummer, F. Wienberg, and M. Duvigneau. Renew - the Reference Net Workshop. Available at: http://www.renew.de/, June 2004. Release 2.0.
• [4] O. Kummer, F. Wienberg, M. Duvigneau, J. Schumacher, M. Köhler, D. Moldt, H. Rölke, and R. Valk. An extensible editor and simulation engine for Petri nets: Renew. In J. Cortadella andW. Reisig, editors, Applications and Theory of Petri Nets 2004. 25th International Conference, ICATPN 2004, Bologna, Italy, June 2004. Proceedings, volume 3099 of Lecture Notes in Computer Science, pages 484-493, Heidelberg, June 2004. Springer.
• [5] K. Wagner and G. Wechsung. Computational Complexity. D. Reidel Publishing Company, 1986.
• [6] J. Wiedermann. Parallel Turing machines. Technical Report RUU-CS-84-11, University of Utrecht, 1984.
• [7] J. Wiedermann. Parallel machine models: How they are and where they are going. In SOFSEM'95: Theory and Practice of Informatics, volume 1012 of Lecture Notes in Computer Science, pages 1-30. Springer-Verlag, 1995.
• [8] T. Worsch. On parallel Turing machines with multi-head control units. Technical Report 11/96, Department of Informatics, University of Karlsruhe, 1996.