A Universal Reversible Turing Machine.

Authors :: Hutchison, David
Kanade, Takeo
Kittler, Josef
Kleinberg, Jon M.
Mattern, Friedemann
Mitchell, John C.
Naor, Moni
Nierstrasz, Oscar
Pandu Rangan, C.
Steffen, Bernhard
Sudan, Madhu
Terzopoulos, Demetri
Tygar, Doug
Vardi, Moshe Y.
Weikum, Gerhard
Durand-Lose, Jérôme
Margenstern, Maurice
Morita, Kenichi
Yamaguchi, Yoshikazu
Source :: Machines, Computations & Universality (9783540745921); 2007, p90-98, 9p
Publication Year :: 2007
Abstract: A reversible Turing machines is a computing model with a "backward deterministic" property, which is closely related to physical reversibility. In this paper, we study the problem of finding a small universal reversible Turing machine (URTM). As a result, we obtained a 17-state 5-symbol URTM in the quintuple form that can simulate any cyclic tag system. [ABSTRACT FROM AUTHOR]