Advertisement
Published in:
2013 | OriginalPaper | Chapter
Time-Symmetric Machines
Authors : Martin Kutrib, Thomas Worsch
Published in: Reversible Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Reversible computational models with discrete internal states are said to be time-symmetric, if they can go back and forth in time by applying the same transition function. The direction in time is adjusted by a weak transformation of the phase-space, that is, an involution. So, these machines themselves cannot distinguish whether they run forward or backward in time. From this viewpoint, finite state machines and pushdown machines are studied in detail. In essence, it turns out that there are reversible machines which are not time-symmetric, but equivalent time-symmetric machines can effectively be constructed. The notion of time-symmetry is discussed, several examples are given, and further results concerning unary inputs and descriptional complexity issues are shown.