Reversible Turing Machine: Difference between revisions
m (→See Also) |
(Note Bennett. Briefly for now until I read his paper in more depth.) |
||
| Line 1: | Line 1: | ||
A '''Reversible Turing Machine''' is a [[Turing machine]] for which the computation can always be run backwards from any step back to the | A '''Reversible Turing Machine''' (RTM) is a [[Turing machine]] for which the computation can always be run backwards from any step back to the previous configuration (and so forth all the way to the start of the computation). This property (called logical reversibility) has theoretical implications for the limits of computation. Specifically, non-reversible computation cannot scale beyond some limit due to the inherent energy cost whereas reversible computations may be able to. | ||
== History == | |||
Charles Bennett described Reversible Turing Machines in a 1973 paper in which he proves that any standard TM can be simulated by a 3-tape RTM.<ref>C. H. Bennett, "[http://www.dna.caltech.edu/courses/cs191/paperscs191/bennett1973.pdf Logical reversibility of computation]", IBM Journal of Research and Development, vol. 17, no. 6, pp. 525–532, 1973</ref> This demonstrates that RTMs with 3+ tapes are universal. It is not entirely clear if 1-tape RTMs (considered in the remainder of this article) are universal. | |||
== Definition == | == Definition == | ||
For 1-tape TMs, they are reversible if and only if: | |||
For all states, all transitions to that state: | |||
# Must move in the same direction | # Must move in the same direction | ||
| Line 11: | Line 14: | ||
== Busy Beaver Champions == | == Busy Beaver Champions == | ||
We can restrict the Busy Beaver competition to only | We can restrict the Busy Beaver competition to only (1-tape) RTMs when doing that we get the following champions: | ||
{| class="wikitable" | {| class="wikitable" | ||
|+ | |+ | ||
Revision as of 04:04, 14 July 2025
A Reversible Turing Machine (RTM) is a Turing machine for which the computation can always be run backwards from any step back to the previous configuration (and so forth all the way to the start of the computation). This property (called logical reversibility) has theoretical implications for the limits of computation. Specifically, non-reversible computation cannot scale beyond some limit due to the inherent energy cost whereas reversible computations may be able to.
History
Charles Bennett described Reversible Turing Machines in a 1973 paper in which he proves that any standard TM can be simulated by a 3-tape RTM.[1] This demonstrates that RTMs with 3+ tapes are universal. It is not entirely clear if 1-tape RTMs (considered in the remainder of this article) are universal.
Definition
For 1-tape TMs, they are reversible if and only if:
For all states, all transitions to that state:
- Must move in the same direction
- Must write different symbols
Bruce Smith called this "microscopic reversibility"[2]
Busy Beaver Champions
We can restrict the Busy Beaver competition to only (1-tape) RTMs when doing that we get the following champions:
| Domain | Max Steps | Champion | Reference |
|---|---|---|---|
| BB(2) | 6 | 0RB1RZ_1LA1RB (bbch)
|
Shawn Ligocki on Discord |
| BB(3) | 17 | 0RB1RZ_0LC1RA_1RB1LC (bbch)
|
Shawn Ligocki on Discord |
| BB(4) | 48 | 1RB0LD_0LC0RB_1LA1LD_1LC1RZ (bbch)
|
Matthew House and Shawn Ligocki on Discord |
| BB(5) | 388 | 1RB0RD_1RC0RB_1RD1RZ_1LE1LA_0LE0LA (bbch)
|
Shawn Ligocki and Matthew House on Discord |
See Also
- Discussion on Discord on 1 July 2025: https://discord.com/channels/960643023006490684/1243312334907375676/1389756466482647142
References
- ↑ C. H. Bennett, "Logical reversibility of computation", IBM Journal of Research and Development, vol. 17, no. 6, pp. 525–532, 1973
- ↑ https://scottaaronson.blog/?p=4916#comment-1851339