Reversible Turing Machine

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.

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.

This is equivalent to the requirement that for all states, for 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 Reversible TMs 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