Reversible Turing Machine: Difference between revisions
(Clarify what we know about 1-tape RTMs. Technically, Bennett only talks about quadruple TMs. I suspect it applies to quintuple TMs as well, but remains to be proven.) |
(→Busy Beaver Champions: Add TNF sizes computed from my new enumeration code.) |
||
| Line 19: | Line 19: | ||
!Domain | !Domain | ||
!Max Steps | !Max Steps | ||
!TNF Size | |||
!Champion | !Champion | ||
!Reference | !Reference | ||
| Line 24: | Line 25: | ||
| [[BB(2)]] | | [[BB(2)]] | ||
| 6 | | 6 | ||
|21 | |||
| {{TM|0RB1RZ_1LA1RB}} | | {{TM|0RB1RZ_1LA1RB}} | ||
| [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki on Discord] | | [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki on Discord] | ||
| Line 29: | Line 31: | ||
| [[BB(3)]] | | [[BB(3)]] | ||
| 17 | | 17 | ||
|356 | |||
| {{TM|0RB1RZ_0LC1RA_1RB1LC}} | | {{TM|0RB1RZ_0LC1RA_1RB1LC}} | ||
| [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki on Discord] | | [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki on Discord] | ||
| Line 34: | Line 37: | ||
| [[BB(4)]] | | [[BB(4)]] | ||
| 48 | | 48 | ||
|9,853 | |||
| {{TM|1RB0LD_0LC0RB_1LA1LD_1LC1RZ}} | | {{TM|1RB0LD_0LC0RB_1LA1LD_1LC1RZ}} | ||
| [https://discord.com/channels/960643023006490684/1243312334907375676/1389809599955210362 Matthew House] and [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki] on Discord | | [https://discord.com/channels/960643023006490684/1243312334907375676/1389809599955210362 Matthew House] and [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki] on Discord | ||
| Line 39: | Line 43: | ||
| [[BB(5)]] | | [[BB(5)]] | ||
| 388 | | 388 | ||
|359,852 | |||
| {{TM|1RB0RD_1RC0RB_1RD1RZ_1LE1LA_0LE0LA}} | | {{TM|1RB0RD_1RC0RB_1RD1RZ_1LE1LA_0LE0LA}} | ||
| [https://discord.com/channels/960643023006490684/1243312334907375676/1389817569342652578 Shawn Ligocki] and [https://discord.com/channels/960643023006490684/1243312334907375676/1389820614415618109 Matthew House] on Discord | | [https://discord.com/channels/960643023006490684/1243312334907375676/1389817569342652578 Shawn Ligocki] and [https://discord.com/channels/960643023006490684/1243312334907375676/1389820614415618109 Matthew House] on Discord | ||
Revision as of 04:24, 16 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 quadruple RTM.[1] He states that they can also be simulated by a 1-tape quadruple RTM, but with quadratic slowdown. It seems likely that a standard TM can also be simulated by a 1-tape quintuple RTM (the type considered in the rest of this article), however, that was not explicitly discussed in Bennett's paper.
Definition
For 1-tape quintuple TMs, it is 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 | TNF Size | Champion | Reference |
|---|---|---|---|---|
| BB(2) | 6 | 21 | 0RB1RZ_1LA1RB (bbch)
|
Shawn Ligocki on Discord |
| BB(3) | 17 | 356 | 0RB1RZ_0LC1RA_1RB1LC (bbch)
|
Shawn Ligocki on Discord |
| BB(4) | 48 | 9,853 | 1RB0LD_0LC0RB_1LA1LD_1LC1RZ (bbch)
|
Matthew House and Shawn Ligocki on Discord |
| BB(5) | 388 | 359,852 | 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