Article,

Simulating Turing Machines Using Colored Petri Nets with Priority Transitions

(Eds.)
Int. J. on Recent Trends in Engineering and Technology,, 9 (1): 7 (July 2013)

Abstract

In this paper, we present a new way to simulate Turing machines using a specific form of Petri nets such that the resulting nets are capable of thoroughly describing behavior of the input Turing machines. We model every element of a Turing machine’s tuple (i.e., Q, Γ, b, Σ, δ, q0, F) with an equivalent translation in Colored Petri net’s set of elements with priority transitions such that the resulting translation (is a Petri net that) accepts the same language as the original Turing machine. In the second part of the paper we analyze time complexity of Turing machine’s input in the resulting Petri net and show that it is a polynomial coefficient of time complexity in the Turing machine.

Tags

Users

  • @idescitation

Comments and Reviews