Simulating Turing Machines Using Colored Petri Nets with Priority Transitions
D. Hope (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.
%0 Journal Article
%1 hope2013simulating
%D 2013
%E Hope, Dr.Martin
%J Int. J. on Recent Trends in Engineering and Technology,
%K Colored Petri Turing machine net
%N 1
%P 7
%T Simulating Turing Machines Using Colored Petri Nets with Priority Transitions
%U http://searchdl.org/public/journals/2013/IJRTET/9/1/34.pdf
%V 9
%X 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.
@article{hope2013simulating,
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.},
added-at = {2014-02-03T05:44:52.000+0100},
biburl = {https://www.bibsonomy.org/bibtex/297f386a5479c325f63543ae545400e92/idescitation},
editor = {Hope, Dr.Martin},
interhash = {3dab455fd3aee52186d89d7b80ea072e},
intrahash = {97f386a5479c325f63543ae545400e92},
journal = {Int. J. on Recent Trends in Engineering and Technology,},
keywords = {Colored Petri Turing machine net},
month = {July},
number = 1,
pages = 7,
timestamp = {2014-02-03T05:44:52.000+0100},
title = {Simulating Turing Machines Using Colored Petri Nets with Priority Transitions},
url = {http://searchdl.org/public/journals/2013/IJRTET/9/1/34.pdf},
volume = 9,
year = 2013
}