Reversible Turing Machine - Revision history

Polygon: Added holdouts list for BBrev(6)

2026-03-28T11:11:51Z

Added holdouts list for BBrev(6)

← Older revision		Revision as of 11:11, 28 March 2026
Line 60:		Line 60:
	\|(Early result from enumeration)		\|(Early result from enumeration)
	\|}		\|}

			For BBrev(6), 388 holdouts remain ([https://wiki.bbchallenge.org/w/images/8/86/BBrev6_holdouts_388.txt list]).

	== See Also ==		== See Also ==

Azerty: Removed the links that redirect to the normal Busy Beaver function.

2025-12-04T12:22:41Z

Removed the links that redirect to the normal Busy Beaver function.

← Older revision		Revision as of 12:22, 4 December 2025
Line 19:		Line 19:
	\|+		\|+
	!Domain		!Domain
	!Max Steps ~~(BB<sub>rev</sub>)~~		!Max Steps
	!TNF Size		!TNF Size
	!Champion		!Champion
	!Reference		!Reference
	\|-		\|-
	\| [[BB(2)]]		\| BB<sub>rev</sub>(2)
	\| style="text-align: right;" \| 6		\| style="text-align: right;" \| 6
	\| style="text-align: right;" \| 21		\| style="text-align: right;" \| 21
Line 30:		Line 30:
	\| [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki on Discord]		\| [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki on Discord]
	\|-		\|-
	\| [[BB(3)]]		\| BB<sub>rev</sub>(3)
	\| style="text-align: right;" \| 17		\| style="text-align: right;" \| 17
	\| style="text-align: right;" \| 356		\| style="text-align: right;" \| 356
Line 36:		Line 36:
	\| [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki on Discord]		\| [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki on Discord]
	\|-		\|-
	\| [[BB(4)]]		\| BB<sub>rev</sub>(4)
	\| style="text-align: right;" \| 48		\| style="text-align: right;" \| 48
	\| style="text-align: right;" \| 9,853		\| style="text-align: right;" \| 9,853
Line 42:		Line 42:
	\| [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
	\|-		\|-
	\| [[BB(5)]]		\| BB<sub>rev</sub>(5)
	\| style="text-align: right;" \| 388		\| style="text-align: right;" \| 388
	\| style="text-align: right;" \| 359,852		\| style="text-align: right;" \| 359,852
Line 48:		Line 48:
	\| [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
	\|-		\|-
	\|[[BB(6)]]		\|BB<sub>rev</sub>(6)
	\| style="text-align: right;" \| ≥537,556		\| style="text-align: right;" \| ≥537,556
	\| style="text-align: right;" \| ≥9,931,603		\| style="text-align: right;" \| ≥9,931,603
Line 54:		Line 54:
	\|[https://discord.com/channels/960643023006490684/1239205785913790465/1400255249847025776 Shawn Ligocki on Discord]		\|[https://discord.com/channels/960643023006490684/1239205785913790465/1400255249847025776 Shawn Ligocki on Discord]
	\|-		\|-
	\|[[BB(7)]]		\|BB<sub>rev</sub>(7)
	\| style="text-align: center;" \| <math>> 10^{19}</math>		\| style="text-align: center;" \| <math>> 10^{19}</math>
	\| style="text-align: right;" \| ≥542,487,066		\| style="text-align: right;" \| ≥542,487,066

Sligocki: Cleanup the BB_rev terminology discussion and put it all in the definitions section.

2025-09-21T15:37:50Z

Cleanup the BB_rev terminology discussion and put it all in the definitions section.

← Older revision		Revision as of 15:37, 21 September 2025
Line 1:		Line 1:
	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~~. For BB<sub>rev</sub>, only halting Reversible Turing Machines are considered~~.		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 ==		== History ==
Line 13:		Line 13:
	Bruce Smith called this "microscopic reversibility"<ref>https://scottaaronson.blog/?p=4916#comment-1851339</ref>		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>		Furthermore, let BB<sub>rev</sub>(n,m) be the maximum step function restricted to only reversible Turing machines. In other words, BB<sub>rev</sub>(n,m) is the maximum runtime across all halting n-state, m-symbol TMs.

	== Busy Beaver Champions ==		== Busy Beaver Champions ==
	~~We can restrict the Busy Beaver competition to only (1-tape) RTMs. When doing that we get the following champions:~~
	{\| class="wikitable"		{\| class="wikitable"
	\|+		\|+
	!Domain		!Domain
	!Max Steps		!Max Steps (BB<sub>rev</sub>)
	!TNF Size		!TNF Size
	!Champion		!Champion

Polygon: Added note that TMs must halt to be champions

2025-09-21T15:20:06Z

Added note that TMs must halt to be champions

← Older revision		Revision as of 15:20, 21 September 2025
Line 1:		Line 1:
	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.		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. For BB<sub>rev</sub>, only halting Reversible Turing Machines are considered.

	== History ==		== History ==
Line 16:		Line 16:

	== Busy Beaver Champions ==		== Busy Beaver Champions ==
	We can restrict the Busy Beaver competition to only (1-tape) RTMs ~~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"		{\| class="wikitable"
	\|+		\|+
Line 58:		Line 58:
	\| style="text-align: center;" \| <math>> 10^{19}</math>		\| style="text-align: center;" \| <math>> 10^{19}</math>
	\| style="text-align: right;" \| ≥542,487,066		\| style="text-align: right;" \| ≥542,487,066
	\|{{TM\|1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB1RZ}}		\|{{TM\|1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB1RZ\|halt}}
	\|(Early result from enumeration)		\|(Early result from enumeration)
	\|}		\|}

Polygon: /* Busy Beaver Champions */ Added "halt" to bbch-links of champions

2025-08-16T19:10:54Z

Busy Beaver Champions: Added "halt" to bbch-links of champions

Sligocki: /* Busy Beaver Champions */

2025-07-31T03:08:27Z

Busy Beaver Champions

← Older revision		Revision as of 03:08, 31 July 2025
Line 59:		Line 59:
	\| style="text-align: right;" \| ≥542,487,066		\| style="text-align: right;" \| ≥542,487,066
	\|{{TM\|1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB1RZ}}		\|{{TM\|1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB1RZ}}
	\|(Early result from ~~partial~~ enumeration)		\|(Early result from enumeration)
	\|}		\|}

Sligocki: /* Busy Beaver Champions */ New BB_rev(6) champion.

2025-07-30T23:16:49Z

Busy Beaver Champions: New BB_rev(6) champion.

← Older revision		Revision as of 23:16, 30 July 2025
Line 50:		Line 50:
	\|-		\|-
	\|[[BB(6)]]		\|[[BB(6)]]
	\| style="text-align: right;" \| ~~≥44~~,~~318~~		\| style="text-align: right;" \| ≥537,556
	\| style="text-align: right;" \| ≥9,931,603		\| style="text-align: right;" \| ≥9,931,603
	\|{{TM\|~~1RB0LA_1RC0RF_0LD1LE_1LD1LA_1RZ1RF_0RC0RB~~}}		\|{{TM\|1RB1LD_1LC1RE_0LD0LC_0RE0RF_0RA1RZ_1RF1RA}}
	\|[https://discord.com/channels/960643023006490684/~~1395095790443036682~~/~~1395097173879689226~~ Shawn Ligocki on Discord]		\|[https://discord.com/channels/960643023006490684/1239205785913790465/1400255249847025776 Shawn Ligocki on Discord]
	\|-		\|-
	\|[[BB(7)]]		\|[[BB(7)]]

Qwerpiw at 19:27, 26 July 2025

2025-07-26T19:27:07Z

← Older revision		Revision as of 19:27, 26 July 2025
Line 12:		Line 12:
	# Must write different symbols		# Must write different symbols
	Bruce Smith called this "microscopic reversibility"<ref>https://scottaaronson.blog/?p=4916#comment-1851339</ref>		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 ==		== Busy Beaver Champions ==
Line 66:		Line 68:
	== References ==		== References ==
	<references />		<references />
			[[category:Functions]]

Sligocki: Align Numbers in table

2025-07-22T19:17:16Z

Align Numbers in table

← Older revision		Revision as of 19:17, 22 July 2025
Line 24:		Line 24:
	\|-		\|-
	\| [[BB(2)]]		\| [[BB(2)]]
	\| 6		\| style="text-align: right;" \| 6
	\|21		\| style="text-align: right;" \| 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]
	\|-		\|-
	\| [[BB(3)]]		\| [[BB(3)]]
	\| 17		\| style="text-align: right;" \| 17
	\|356		\| style="text-align: right;" \| 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]
	\|-		\|-
	\| [[BB(4)]]		\| [[BB(4)]]
	\| 48		\| style="text-align: right;" \| 48
	\|9,853		\| style="text-align: right;" \| 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
	\|-		\|-
	\| [[BB(5)]]		\| [[BB(5)]]
	\| 388		\| style="text-align: right;" \| 388
	\|359,852		\| style="text-align: right;" \| 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
	\|-		\|-
	\|[[BB(6)]]		\|[[BB(6)]]
	\|≥44,318		\| style="text-align: right;" \| ≥44,318
	\|≥9,931,603		\| style="text-align: right;" \| ≥9,931,603
	\|{{TM\|1RB0LA_1RC0RF_0LD1LE_1LD1LA_1RZ1RF_0RC0RB}}		\|{{TM\|1RB0LA_1RC0RF_0LD1LE_1LD1LA_1RZ1RF_0RC0RB}}
	\|[https://discord.com/channels/960643023006490684/1395095790443036682/1395097173879689226 Shawn Ligocki on Discord]		\|[https://discord.com/channels/960643023006490684/1395095790443036682/1395097173879689226 Shawn Ligocki on Discord]
	\|-		\|-
	\|[[BB(7)]]		\|[[BB(7)]]
	\|<math>> 10^{19}</math>		\| style="text-align: center;" \| <math>> 10^{19}</math>
	\|≥542,487,066		\| style="text-align: right;" \| ≥542,487,066
	\|{{TM\|1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB1RZ}}		\|{{TM\|1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB1RZ}}
	\|(Early result from partial enumeration)		\|(Early result from partial enumeration)

Sligocki: /* Busy Beaver Champions */ Initial enumeration for BB_rev(7)

2025-07-20T04:02:44Z

Busy Beaver Champions: Initial enumeration for BB_rev(7)

← Older revision		Revision as of 04:02, 20 July 2025
Line 55:		Line 55:
	\|[[BB(7)]]		\|[[BB(7)]]
	\|<math>> 10^{19}</math>		\|<math>> 10^{19}</math>
	\|		\|≥542,487,066
	\|{{TM\|1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB1RZ}}		\|{{TM\|1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB1RZ}}
	\|(Early result from partial enumeration)		\|(Early result from partial enumeration)

← Older revision		Revision as of 19:10, 16 August 2025
Line 28:		Line 28:
	\| style="text-align: right;" \| 6		\| style="text-align: right;" \| 6
	\| style="text-align: right;" \| 21		\| style="text-align: right;" \| 21
	\| {{TM\|0RB1RZ_1LA1RB}}		\| {{TM\|0RB1RZ_1LA1RB\|halt}}
	\| [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 34:
	\| style="text-align: right;" \| 17		\| style="text-align: right;" \| 17
	\| style="text-align: right;" \| 356		\| style="text-align: right;" \| 356
	\| {{TM\|0RB1RZ_0LC1RA_1RB1LC}}		\| {{TM\|0RB1RZ_0LC1RA_1RB1LC\|halt}}
	\| [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki on Discord]		\| [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki on Discord]
	\|-		\|-
Line 40:		Line 40:
	\| style="text-align: right;" \| 48		\| style="text-align: right;" \| 48
	\| style="text-align: right;" \| 9,853		\| style="text-align: right;" \| 9,853
	\| {{TM\|1RB0LD_0LC0RB_1LA1LD_1LC1RZ}}		\| {{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		\| [https://discord.com/channels/960643023006490684/1243312334907375676/1389809599955210362 Matthew House] and [https://discord.com/channels/960643023006490684/1243312334907375676/1389807954013978756 Shawn Ligocki] on Discord
	\|-		\|-
Line 46:		Line 46:
	\| style="text-align: right;" \| 388		\| style="text-align: right;" \| 388
	\| style="text-align: right;" \| 359,852		\| style="text-align: right;" \| 359,852
	\| {{TM\|1RB0RD_1RC0RB_1RD1RZ_1LE1LA_0LE0LA}}		\| {{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		\| [https://discord.com/channels/960643023006490684/1243312334907375676/1389817569342652578 Shawn Ligocki] and [https://discord.com/channels/960643023006490684/1243312334907375676/1389820614415618109 Matthew House] on Discord
	\|-		\|-
Line 52:		Line 52:
	\| style="text-align: right;" \| ≥537,556		\| style="text-align: right;" \| ≥537,556
	\| style="text-align: right;" \| ≥9,931,603		\| style="text-align: right;" \| ≥9,931,603
	\|{{TM\|1RB1LD_1LC1RE_0LD0LC_0RE0RF_0RA1RZ_1RF1RA}}		\|{{TM\|1RB1LD_1LC1RE_0LD0LC_0RE0RF_0RA1RZ_1RF1RA\|halt}}
	\|[https://discord.com/channels/960643023006490684/1239205785913790465/1400255249847025776 Shawn Ligocki on Discord]		\|[https://discord.com/channels/960643023006490684/1239205785913790465/1400255249847025776 Shawn Ligocki on Discord]
	\|-		\|-