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.
Users
Please
log in to take part in the discussion (add own reviews or comments).