Reversible Turing Machine

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. 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:

1. Must move in the same direction
2. Must write different symbols

Bruce Smith called this "microscopic reversibility"

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)	≥44,318	≥9,931,603	1RB0LA_1RC0RF_0LD1LE_1LD1LA_1RZ1RF_0RC0RB (bbch)	Shawn Ligocki on Discord
BB(7)	$>10^{13}$		1RB0LG_1RC0RD_1RD0RC_0LE0RA_1RA0LF_0RB1LE_1RZ1LF (bbch)	(Early result from partial enumeration)

See Also

• Discussion on Discord on 1 July 2025: https://discord.com/channels/960643023006490684/1243312334907375676/1389756466482647142