Reversible Turing Machine: Difference between revisions

Latest revision as of 19:10, 16 August 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]

The reversible Turing machine function is denoted BB_rev

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
BB(6)	≥537,556	≥9,931,603	`1RB1LD_1LC1RE_0LD0LC_0RE0RF_0RA1RZ_1RF1RA` (bbch)	Shawn Ligocki on Discord
BB(7)	$>10^{19}$	≥542,487,066	`1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB1RZ` (bbch)	(Early result from enumeration)

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

[1] C. H. Bennett, "Logical reversibility of computation", IBM Journal of Research and Development, vol. 17, no. 6, pp. 525–532, 1973

[2] ttps://scottaaronson.blog/?p=4916#comment-1851339

[1]

[2]

@@ 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 original configuration. 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 entropy cost whereas reversible computations may be able to.
+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.<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> 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 ==
-There does not seem to be a completely clear consensus on exactly how to restrict TMs to support this model, but in this wiki we will use the following definition: Given any configuration there is at most one previous configuration that could lead to it.
+For 1-tape quintuple TMs, it is reversible if and only if:
-This is equivalent to the requirement that for all states, for all transitions to that state:
+For all states, all transitions to that state:
 # Must move in the same direction
 # Must write different symbols
 Bruce Smith called this "microscopic reversibility"<ref>https://scottaaronson.blog/?p=4916#comment-1851339</ref>
+The reversible Turing machine function is denoted BB<sub>rev</sub>
 == Busy Beaver Champions ==
-We can restrict the Busy Beaver competition to only Reversible TMs when doing that we get the following champions:
+We can restrict the Busy Beaver competition to only (1-tape) RTMs when doing that we get the following champions:
 {| class="wikitable"
 |+
 !Domain
 !Max Steps
+!TNF Size
 !Champion
 !Reference
 |-
 | [[BB(2)]]
-| 6
+| style="text-align: right;" | 6
-| {{TM|0RB1RZ_1LA1RB}}
+| style="text-align: right;" | 21
+| {{TM|0RB1RZ_1LA1RB|halt}}
 | [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki on Discord]
 |-
 | [[BB(3)]]
-| 17
+| style="text-align: right;" | 17
-| {{TM|0RB1RZ_0LC1RA_1RB1LC}}
+| style="text-align: right;" | 356
+| {{TM|0RB1RZ_0LC1RA_1RB1LC|halt}}
 | [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki on Discord]
 |-
 | [[BB(4)]]
-| 48
+| style="text-align: right;" | 48
-| {{TM|1RB0LD_0LC0RB_1LA1LD_1LC1RZ}}
+| style="text-align: right;" | 9,853
+| {{TM|1RB0LD_0LC0RB_1LA1LD_1LC1RZ|halt}}
 | [https://discord.com/channels/960643023006490684/1243312334907375676/1389809599955210362 Matthew House] and [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki] on Discord
 |-
 | [[BB(5)]]
-| 388
+| style="text-align: right;" | 388
-| {{TM|1RB0RD_1RC0RB_1RD1RZ_1LE1LA_0LE0LA}}
+| style="text-align: right;" | 359,852
+| {{TM|1RB0RD_1RC0RB_1RD1RZ_1LE1LA_0LE0LA|halt}}
 | [https://discord.com/channels/960643023006490684/1243312334907375676/1389817569342652578 Shawn Ligocki] and [https://discord.com/channels/960643023006490684/1243312334907375676/1389820614415618109 Matthew House] on Discord
+|-
+|[[BB(6)]]
+| style="text-align: right;" | ≥537,556
+| style="text-align: right;" | ≥9,931,603
+|{{TM|1RB1LD_1LC1RE_0LD0LC_0RE0RF_0RA1RZ_1RF1RA|halt}}
+|[https://discord.com/channels/960643023006490684/1239205785913790465/1400255249847025776 Shawn Ligocki on Discord]
+|-
+|[[BB(7)]]
+| style="text-align: center;" | <math>> 10^{19}</math>
+| style="text-align: right;" | ≥542,487,066
+|{{TM|1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB1RZ}}
+|(Early result from enumeration)
 |}
 == See Also ==
-* Discussion on Discord on 1 July 2025: https://discord.com/channels/960643023006490684/1243312334907375676/1389768637157478451
+* Discussion on Discord on 1 July 2025: https://discord.com/channels/960643023006490684/1243312334907375676/1389756466482647142
 == References ==
 <references />
+[[category:Functions]]

Reversible Turing Machine: Difference between revisions

Latest revision as of 19:10, 16 August 2025

Contents

History

Definition

Busy Beaver Champions

See Also

References

Navigation menu