Universality of a reversible two-counter machine

✍ Scribed by Kenichi Morita

• Book ID: 104326180
• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 884 KB
• Volume: 168
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(96)00081-3

✦ Synopsis

A k-counter machine (CM(k)) is an automaton having k counters as an auxiliary memory.

It has been shown by Minsky that a CM(2) can simulate any Turing machine and thus it is universal. In this paper, we investigate the computing ability of reversible (i.e., backward deterministic) CMs. We first show that any irreversible CM(R) can be simulated by a reversible CM(k + 2). In this simulation, however, the reversible CM(k + 2) leaves a large number as a garbage in some counter when it halts. We then show that, if k more counters are added, this garbage information is erased reversibly. Finally, we prove that any reversible CM(R) (k = 1,2,3,. . .) can be simulated by a reversible CM(2). From these results computation-universality of a reversible CM(2) is established.