Least Busy Beaver - Revision history

Qwerpiw at 19:22, 26 July 2025

2025-07-26T19:22:35Z

← Older revision		Revision as of 19:22, 26 July 2025
Line 63:		Line 63:
	==Notes==		==Notes==
	<references />		<references />
			[[category:Functions]]

Racheline at 23:36, 16 February 2025

2025-02-16T23:36:25Z

← Older revision		Revision as of 23:36, 16 February 2025
Line 33:		Line 33:
	\|}		\|}

	Racheline proved by hand that <math>BB^-(2, 2) = 6</math><ref><math>BB^-(2, 2) = 6</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340062334952935594 Link to first Discord message]</ref>, and with the help of computer searches, she proved <math>BB^-(3, 2) = 21</math><ref><math>BB^-(3, 2) = 21</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340098138924515458 Link to first Discord message]</ref>. She later made a program that automatically tries to confirm lower bounds <math>BB^-(n, m)\ge t</math>, by covering the set of all initial tapes with a family of sets, where each set of the family contains tapes that agree in a given radius around the starting position, such that a single TM halts in <math>\ge t</math> steps without leaving that shared part of the tapes (and therefore halts in <math>\ge t</math> steps on all of those tapes with the same transition history). This program verified her previous results<ref><math>BB^-(2, 2) = 6</math> and <math>BB^-(3, 2) = 21</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340790512160084130 Discord message link]</ref> and produced the results <math>BB^-(2, 3) = BB(2, 3) = 38</math><ref><math>BB^-(2, 3) = 38</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340773779198185607 Discord message link]</ref> and <math>BB^-(4, 2) = 107</math><ref><math>BB^-(4, 2) = 107</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340827079012384911 Discord message link]</ref>. None of this has been formally verified as of 16 Feb 2025.<br>		Racheline proved by hand that <math>BB^-(2, 2) = 6</math><ref><math>BB^-(2, 2) = 6</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340062334952935594 Link to first Discord message]</ref>, and with the help of computer searches, she proved <math>BB^-(3, 2) = 21</math><ref><math>BB^-(3, 2) = 21</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340098138924515458 Link to first Discord message]</ref>. She later made a program that automatically tries to confirm lower bounds <math>BB^-(n, m)\ge t</math>, by covering the set of all initial tapes with a family of sets, where each set of the family contains tapes that agree in a given radius around the starting position, such that a single TM halts in <math>\ge t</math> steps without leaving that shared part of the tapes (and therefore halts in <math>\ge t</math> steps on all of those tapes with the same transition history). This program verified her previous results<ref><math>BB^-(2, 2) = 6</math> and <math>BB^-(3, 2) = 21</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340790512160084130 Discord message link]</ref> and produced the results <math>BB^-(2, 3) = BB(2, 3) = 38</math><ref><math>BB^-(2, 3) = 38</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340773779198185607 Discord message link]</ref>, and later <math>BB^-(4, 2) = 107</math><ref><math>BB^-(4, 2) = 107</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340827079012384911 Discord message link]</ref> using Shawn Ligocki's idea to speed up the process by first using TMs that are likely to halt late (such as the TMs listed in [[BB(4)]]) to filter out most tapes. None of this has been formally verified as of 16 Feb 2025.<br>
	Certificate of <math>BB^-(2, 2) = BB(2, 2) = 6</math>:<pre>		Certificate of <math>BB^-(2, 2) = BB(2, 2) = 6</math>:<pre>
	(0, 0, 0) 1RB1RZ_0LB1LA 6		(0, 0, 0) 1RB1RZ_0LB1LA 6

Racheline: BB^-(4) = 107

2025-02-16T23:32:28Z

BB^-(4) = 107

← Older revision		Revision as of 23:32, 16 February 2025
Line 25:		Line 25:
	\| <math>BB^-(2) = 6</math>		\| <math>BB^-(2) = 6</math>
	\| <math>BB^-(3) = 21</math>		\| <math>BB^-(3) = 21</math>
	\| <math>~~50\le~~ BB^-(4)~~\le~~ 107</math>		\| <math>BB^-(4) = 107</math>
	\|-		\|-
	\| 3-symbol		\| 3-symbol
Line 33:		Line 33:
	\|}		\|}

	Racheline proved by hand that <math>BB^-(2, 2) = 6</math><ref><math>BB^-(2, 2) = 6</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340062334952935594 Link to first Discord message]</ref>, and with the help of computer searches, she proved <math>BB^-(3, 2) = 21</math><ref><math>BB^-(3, 2) = 21</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340098138924515458 Link to first Discord message]</ref>. She later made a program that automatically tries to confirm lower bounds <math>BB^-(n, m)\ge t</math>, by covering the set of all initial tapes with a family of sets, where each set of the family contains tapes that agree in a given radius around the starting position, such that a single TM halts in <math>\ge t</math> steps without leaving that shared part of the tapes (and therefore halts in <math>\ge t</math> steps on all of those tapes with the same transition history). This program verified her previous results<ref><math>BB^-(2, 2) = 6</math> and <math>BB^-(3, 2) = 21</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340790512160084130 Discord message link]</ref> and produced the results <math>BB^-(2, 3) = BB(2, 3) = 38</math><ref><math>BB^-(2, 3) = 38</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340773779198185607 Discord message link]</ref> and <math>BB^-(4, 2)~~\ge 50~~</math><ref><math>BB^-(4, 2)~~\ge 50~~</math> [https://discord.com/channels/960643023006490684/960643023530762341/~~1340783571501187142~~ Discord message link]</ref>. None of this has been formally verified as of 16 Feb 2025.<br>		Racheline proved by hand that <math>BB^-(2, 2) = 6</math><ref><math>BB^-(2, 2) = 6</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340062334952935594 Link to first Discord message]</ref>, and with the help of computer searches, she proved <math>BB^-(3, 2) = 21</math><ref><math>BB^-(3, 2) = 21</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340098138924515458 Link to first Discord message]</ref>. She later made a program that automatically tries to confirm lower bounds <math>BB^-(n, m)\ge t</math>, by covering the set of all initial tapes with a family of sets, where each set of the family contains tapes that agree in a given radius around the starting position, such that a single TM halts in <math>\ge t</math> steps without leaving that shared part of the tapes (and therefore halts in <math>\ge t</math> steps on all of those tapes with the same transition history). This program verified her previous results<ref><math>BB^-(2, 2) = 6</math> and <math>BB^-(3, 2) = 21</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340790512160084130 Discord message link]</ref> and produced the results <math>BB^-(2, 3) = BB(2, 3) = 38</math><ref><math>BB^-(2, 3) = 38</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340773779198185607 Discord message link]</ref> and <math>BB^-(4, 2) = 107</math><ref><math>BB^-(4, 2) = 107</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340827079012384911 Discord message link]</ref>. None of this has been formally verified as of 16 Feb 2025.<br>
	Certificate of <math>BB^-(2, 2) = BB(2, 2) = 6</math>:<pre>		Certificate of <math>BB^-(2, 2) = BB(2, 2) = 6</math>:<pre>
	(0, 0, 0) 1RB1RZ_0LB1LA 6		(0, 0, 0) 1RB1RZ_0LB1LA 6

Racheline at 21:32, 16 February 2025

2025-02-16T21:32:55Z

← Older revision		Revision as of 21:32, 16 February 2025
Line 15:		Line 15:

	== Known Results ==		== Known Results ==
	<math>BB^-(2, 2) = BB(2, 2) = 6</math>		Clearly, <math>BB^-(1, m) = 1</math> for all positive integers <math>m</math>, since <math>BB_{init}(n, m, T)</math> is always at least <math>1</math> so we have <math>1\le BB^-(1,m)\le BB(1,m) = 1</math>.

	Certificate:		{\| class="wikitable"
	<pre>		\|+ Small least busy beaver values
			\|-
			\| \|\| 2-state \|\| 3-state \|\| 4-state
			\|-
			\| 2-symbol
			\| <math>BB^-(2) = 6</math>
			\| <math>BB^-(3) = 21</math>
			\| <math>50\le BB^-(4)\le 107</math>
			\|-
			\| 3-symbol
			\| <math>BB^-(2, 3) = 38</math>
			\|
			\|
			\|}

			Racheline proved by hand that <math>BB^-(2, 2) = 6</math><ref><math>BB^-(2, 2) = 6</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340062334952935594 Link to first Discord message]</ref>, and with the help of computer searches, she proved <math>BB^-(3, 2) = 21</math><ref><math>BB^-(3, 2) = 21</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340098138924515458 Link to first Discord message]</ref>. She later made a program that automatically tries to confirm lower bounds <math>BB^-(n, m)\ge t</math>, by covering the set of all initial tapes with a family of sets, where each set of the family contains tapes that agree in a given radius around the starting position, such that a single TM halts in <math>\ge t</math> steps without leaving that shared part of the tapes (and therefore halts in <math>\ge t</math> steps on all of those tapes with the same transition history). This program verified her previous results<ref><math>BB^-(2, 2) = 6</math> and <math>BB^-(3, 2) = 21</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340790512160084130 Discord message link]</ref> and produced the results <math>BB^-(2, 3) = BB(2, 3) = 38</math><ref><math>BB^-(2, 3) = 38</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340773779198185607 Discord message link]</ref> and <math>BB^-(4, 2)\ge 50</math><ref><math>BB^-(4, 2)\ge 50</math> [https://discord.com/channels/960643023006490684/960643023530762341/1340783571501187142 Discord message link]</ref>. None of this has been formally verified as of 16 Feb 2025.<br>
			Certificate of <math>BB^-(2, 2) = BB(2, 2) = 6</math>:<pre>
	(0, 0, 0) 1RB1RZ_0LB1LA 6		(0, 0, 0) 1RB1RZ_0LB1LA 6
	(0, 0, 1) 0LB1RZ_1RA0RB 6		(0, 0, 1) 0LB1RZ_1RA0RB 6
Line 25:		Line 41:
	(1, 1, 0, 1, 1) 0RB1RZ_0LB0LA 7		(1, 1, 0, 1, 1) 0RB1RZ_0LB0LA 7
	</pre>		</pre>
			Certificate of <math>BB^-(3, 2) = BB(3, 2) = 21</math>:<pre>
	<math>BB^-(3, 2) = BB(3, 2) = 21</math>

	~~Certificate~~:
	<pre>
	(0, 0, 0, 0, 1) 0LB0LC_1RB1LC_1RZ1RA 21		(0, 0, 0, 0, 1) 0LB0LC_1RB1LC_1RZ1RA 21
			(0, 0, 0, 1, 1) 1RB0LB_1RZ1LC_1RC1RA 22
			(0, 1, 0, 1, 1) 1RB0RC_1RC0LB_0LA1RZ 21
	(1, 0, 0, 0, 1) 0RA1LB_0LB0RC_1RA1RZ 23		(1, 0, 0, 0, 1) 0RA1LB_0LB0RC_1RA1RZ 23
	~~(0, 0, 0, 1, 1) 1RB0LB_1RZ1LC_1RC1RA 22~~
	(1, 0, 0, 1, 0) 1LA1RB_0LC0RB_0LA1RZ 23		(1, 0, 0, 1, 0) 1LA1RB_0LC0RB_0LA1RZ 23
	(1, 0, 0, 1, 1) 0LB1RC_1LA1RZ_0RC0LA 21		(1, 0, 0, 1, 1) 0LB1RC_1LA1RZ_0RC0LA 21
	~~(0, 1, 0, 1, 1) 1RB0RC_1RC0LB_0LA1RZ 21~~
	(1, 1, 0, 1, 1) 0RB0LB_1RZ1LC_1RA0RC 21		(1, 1, 0, 1, 1) 0RB0LB_1RZ1LC_1RA0RC 21
	(0, 0, 0, 0, 0, 0, 0) 1RB1RZ_1LB0RC_1LC1LA 21		(0, 0, 0, 0, 0, 0, 0) 1RB1RZ_1LB0RC_1LC1LA 21
	(0, 0, 0, 0, 0, 0, 1) 0LB1RZ_0LC1RB_1RA0RC 24		(0, 0, 0, 0, 0, 0, 1) 0LB1RZ_0LC1RB_1RA0RC 24
	~~(1, 0, 0, 0, 0, 0, 1) 0RA0LB_1LC1RZ_0LC1RA 40~~
	(0, 0, 0, 0, 1, 0, 0) 0LB0RB_1RB1LC_1RZ0LA 22		(0, 0, 0, 0, 1, 0, 0) 0LB0RB_1RB1LC_1RZ0LA 22
	(0, 0, 0, 0, 1, 0, 1) 0LB0RB_1RB1LC_1RZ0LA 22		(0, 0, 0, 0, 1, 0, 1) 0LB0RB_1RB1LC_1RZ0LA 22
			(0, 0, 1, 0, 1, 0, 0) 0RA0RB_1LB1LC_1RA1RZ 21
			(0, 0, 1, 0, 1, 0, 1) 0LA0LB_1RB1RC_1LA1RZ 21
			(1, 0, 0, 0, 0, 0, 1) 0RA0LB_1LC1RZ_0LC1RA 40
	(1, 0, 0, 0, 1, 0, 0) 0LA1RB_0RB0LC_1LA1RZ 24		(1, 0, 0, 0, 1, 0, 0) 0LA1RB_0RB0LC_1LA1RZ 24
	(1, 0, 0, 0, 1, 0, 1) 0LA1RB_0RB0LC_1LA1RZ 24		(1, 0, 0, 0, 1, 0, 1) 0LA1RB_0RB0LC_1LA1RZ 24
	~~(0, 0, 1, 0, 1, 0, 0) 0RA0RB_1LB1LC_1RA1RZ 21~~
	~~(0, 0, 1, 0, 1, 0, 1) 0LA0LB_1RB1RC_1LA1RZ 21~~
	(1, 0, 1, 0, 1, 0, 1) 0RB1RZ_0LC0LB_1RA0LA 21		(1, 0, 1, 0, 1, 0, 1) 0RB1RZ_0LC0LB_1RA0LA 21
	</pre>		</pre>

	~~<math>BB^-(2, 3)~~ = ~~BB(2, 3)~~ = ~~38</math>~~		==Notes==
			<references />
	~~Certificate: https://discord.com/channels/960643023006490684/960643023530762341/1340773779198185607~~

	<~~math>BB^-(4, 2) \ge 50<~~/~~math~~>

	~~Certificate: https://discord.com/channels/960643023006490684/960643023530762341/1340783571501187142~~

Sligocki: /* Known Results */

2025-02-16T21:29:23Z

Known Results

← Older revision		Revision as of 21:29, 16 February 2025
Line 17:		Line 17:
	<math>BB^-(2, 2) = BB(2, 2) = 6</math>		<math>BB^-(2, 2) = BB(2, 2) = 6</math>

	Certificate:<pre>		Certificate:
			<pre>
	(0, 0, 0) 1RB1RZ_0LB1LA 6		(0, 0, 0) 1RB1RZ_0LB1LA 6
	(0, 0, 1) 0LB1RZ_1RA0RB 6		(0, 0, 1) 0LB1RZ_1RA0RB 6
Line 23:		Line 24:
	(0, 1, 0, 1, 1) 0LA0LB_0RB1RZ 6		(0, 1, 0, 1, 1) 0LA0LB_0RB1RZ 6
	(1, 1, 0, 1, 1) 0RB1RZ_0LB0LA 7		(1, 1, 0, 1, 1) 0RB1RZ_0LB0LA 7
	</pre~~><math>BB^-(3, 2) = BB(3, 2) = 21</math~~>		</pre>

	Certificate:<pre>		<math>BB^-(3, 2) = BB(3, 2) = 21</math>

			Certificate:
			<pre>
	(0, 0, 0, 0, 1) 0LB0LC_1RB1LC_1RZ1RA 21		(0, 0, 0, 0, 1) 0LB0LC_1RB1LC_1RZ1RA 21
			(1, 0, 0, 0, 1) 0RA1LB_0LB0RC_1RA1RZ 23
	(0, 0, 0, 1, 1) 1RB0LB_1RZ1LC_1RC1RA 22		(0, 0, 0, 1, 1) 1RB0LB_1RZ1LC_1RC1RA 22
	~~(0, 1, 0, 1, 1) 1RB0RC_1RC0LB_0LA1RZ 21~~
	~~(1, 0, 0, 0, 1) 0RA1LB_0LB0RC_1RA1RZ 23~~
	(1, 0, 0, 1, 0) 1LA1RB_0LC0RB_0LA1RZ 23		(1, 0, 0, 1, 0) 1LA1RB_0LC0RB_0LA1RZ 23
	(1, 0, 0, 1, 1) 0LB1RC_1LA1RZ_0RC0LA 21		(1, 0, 0, 1, 1) 0LB1RC_1LA1RZ_0RC0LA 21
			(0, 1, 0, 1, 1) 1RB0RC_1RC0LB_0LA1RZ 21
	(1, 1, 0, 1, 1) 0RB0LB_1RZ1LC_1RA0RC 21		(1, 1, 0, 1, 1) 0RB0LB_1RZ1LC_1RA0RC 21
	(0, 0, 0, 0, 0, 0, 0) 1RB1RZ_1LB0RC_1LC1LA 21		(0, 0, 0, 0, 0, 0, 0) 1RB1RZ_1LB0RC_1LC1LA 21
	(0, 0, 0, 0, 0, 0, 1) 0LB1RZ_0LC1RB_1RA0RC 24		(0, 0, 0, 0, 0, 0, 1) 0LB1RZ_0LC1RB_1RA0RC 24
			(1, 0, 0, 0, 0, 0, 1) 0RA0LB_1LC1RZ_0LC1RA 40
	(0, 0, 0, 0, 1, 0, 0) 0LB0RB_1RB1LC_1RZ0LA 22		(0, 0, 0, 0, 1, 0, 0) 0LB0RB_1RB1LC_1RZ0LA 22
	(0, 0, 0, 0, 1, 0, 1) 0LB0RB_1RB1LC_1RZ0LA 22		(0, 0, 0, 0, 1, 0, 1) 0LB0RB_1RB1LC_1RZ0LA 22
			(1, 0, 0, 0, 1, 0, 0) 0LA1RB_0RB0LC_1LA1RZ 24
			(1, 0, 0, 0, 1, 0, 1) 0LA1RB_0RB0LC_1LA1RZ 24
	(0, 0, 1, 0, 1, 0, 0) 0RA0RB_1LB1LC_1RA1RZ 21		(0, 0, 1, 0, 1, 0, 0) 0RA0RB_1LB1LC_1RA1RZ 21
	(0, 0, 1, 0, 1, 0, 1) 0LA0LB_1RB1RC_1LA1RZ 21		(0, 0, 1, 0, 1, 0, 1) 0LA0LB_1RB1RC_1LA1RZ 21
	~~(1, 0, 0, 0, 0, 0, 1) 0RA0LB_1LC1RZ_0LC1RA 40~~
	~~(1, 0, 0, 0, 1, 0, 0) 0LA1RB_0RB0LC_1LA1RZ 24~~
	~~(1, 0, 0, 0, 1, 0, 1) 0LA1RB_0RB0LC_1LA1RZ 24~~
	(1, 0, 1, 0, 1, 0, 1) 0RB1RZ_0LC0LB_1RA0LA 21		(1, 0, 1, 0, 1, 0, 1) 0RB1RZ_0LC0LB_1RA0LA 21
	</pre><math>BB^-(2, 3) = BB(2, 3) = 38</math>		</pre>

			<math>BB^-(2, 3) = BB(2, 3) = 38</math>

	Certificate: https://discord.com/channels/960643023006490684/960643023530762341/1340773779198185607		Certificate: https://discord.com/channels/960643023006490684/960643023530762341/1340773779198185607

Sligocki: Add known results and "certificates"

2025-02-16T21:20:18Z

Add known results and "certificates"

← Older revision		Revision as of 21:20, 16 February 2025
Line 12:		Line 12:
	<math display="block">BB^-(n, m) \le BB(n, m)</math>		<math display="block">BB^-(n, m) \le BB(n, m)</math>

	We have not yet found an example where we can prove that <math>BB^-(n, m) \ne BB(n, m)</math>		We have not yet found an example where we can prove that <math>BB^-(n, m) \ne BB(n, m)</math>.

			== Known Results ==
			<math>BB^-(2, 2) = BB(2, 2) = 6</math>

			Certificate:<pre>
			(0, 0, 0) 1RB1RZ_0LB1LA 6
			(0, 0, 1) 0LB1RZ_1RA0RB 6
			(0, 1, 0, 1, 0) 0RA0RB_0LB1RZ 6
			(0, 1, 0, 1, 1) 0LA0LB_0RB1RZ 6
			(1, 1, 0, 1, 1) 0RB1RZ_0LB0LA 7
			</pre><math>BB^-(3, 2) = BB(3, 2) = 21</math>

			Certificate:<pre>
			(0, 0, 0, 0, 1) 0LB0LC_1RB1LC_1RZ1RA 21
			(0, 0, 0, 1, 1) 1RB0LB_1RZ1LC_1RC1RA 22
			(0, 1, 0, 1, 1) 1RB0RC_1RC0LB_0LA1RZ 21
			(1, 0, 0, 0, 1) 0RA1LB_0LB0RC_1RA1RZ 23
			(1, 0, 0, 1, 0) 1LA1RB_0LC0RB_0LA1RZ 23
			(1, 0, 0, 1, 1) 0LB1RC_1LA1RZ_0RC0LA 21
			(1, 1, 0, 1, 1) 0RB0LB_1RZ1LC_1RA0RC 21
			(0, 0, 0, 0, 0, 0, 0) 1RB1RZ_1LB0RC_1LC1LA 21
			(0, 0, 0, 0, 0, 0, 1) 0LB1RZ_0LC1RB_1RA0RC 24
			(0, 0, 0, 0, 1, 0, 0) 0LB0RB_1RB1LC_1RZ0LA 22
			(0, 0, 0, 0, 1, 0, 1) 0LB0RB_1RB1LC_1RZ0LA 22
			(0, 0, 1, 0, 1, 0, 0) 0RA0RB_1LB1LC_1RA1RZ 21
			(0, 0, 1, 0, 1, 0, 1) 0LA0LB_1RB1RC_1LA1RZ 21
			(1, 0, 0, 0, 0, 0, 1) 0RA0LB_1LC1RZ_0LC1RA 40
			(1, 0, 0, 0, 1, 0, 0) 0LA1RB_0RB0LC_1LA1RZ 24
			(1, 0, 0, 0, 1, 0, 1) 0LA1RB_0RB0LC_1LA1RZ 24
			(1, 0, 1, 0, 1, 0, 1) 0RB1RZ_0LC0LB_1RA0LA 21
			</pre><math>BB^-(2, 3) = BB(2, 3) = 38</math>

			Certificate: https://discord.com/channels/960643023006490684/960643023530762341/1340773779198185607

			<math>BB^-(4, 2) \ge 50</math>

			Certificate: https://discord.com/channels/960643023006490684/960643023530762341/1340783571501187142

Racheline at 18:24, 16 February 2025

2025-02-16T18:24:58Z

← Older revision		Revision as of 18:24, 16 February 2025
Line 1:		Line 1:
	The '''least busy beaver''' <math>BB^-(n, m)</math> problem is a variation of the busy beaver problem which considers TM behavior across all starting tapes (not just blank tapes like the traditional BB problem) ~~invented~~ by ~~racheline~~ on 15 Feb 2025.		The '''least busy beaver''' <math>BB^-(n, m)</math> problem is a variation of the busy beaver problem which considers TM behavior across all starting tapes (not just blank tapes like the traditional BB problem) discovered by Racheline on 15 Feb 2025.

	== Definition ==		== Definition ==

Racheline: Racheline moved page Least busy beaver to Least Busy Beaver: consistency

2025-02-16T18:22:02Z

Racheline moved page Least busy beaver to Least Busy Beaver: consistency

← Older revision	Revision as of 18:22, 16 February 2025
(No difference)

Sligocki at 18:19, 16 February 2025

2025-02-16T18:19:20Z

← Older revision		Revision as of 18:19, 16 February 2025
Line 4:		Line 4:
	Let <math>BB_{init}(n, m, T)</math> be the longest runtime for all n-state m-symbol TMs which halt when started on tape configuration T (where T is allowed to be any infinite tape configuration, including ones with an infinite number of non-zero values). Then		Let <math>BB_{init}(n, m, T)</math> be the longest runtime for all n-state m-symbol TMs which halt when started on tape configuration T (where T is allowed to be any infinite tape configuration, including ones with an infinite number of non-zero values). Then

	<math>BB^-(n, m) = min_T BB_{init}(n, m, T)</math>		<math display="block">BB^-(n, m) = min_T BB_{init}(n, m, T)</math>

	~~That is~~ the minimal value across all possible starting tapes. This minimum must exist because the values of <math>BB_{init}(n, m, T)</math> are all positive integers and thus well ordered.		In other words, the minimal value across all possible starting tapes. This minimum must exist because the values of <math>BB_{init}(n, m, T)</math> are all positive integers and thus well ordered.

	Note that <math>BB_{init}(n, m, B) = BB(n, m)</math> where B is the blank (all-zeros) tape. Therefore,		Note that <math>BB_{init}(n, m, B) = BB(n, m)</math> where B is the blank (all-zeros) tape. Therefore,

	<math>BB^-(n, m) \le BB(n, m)</math>		<math display="block">BB^-(n, m) \le BB(n, m)</math>

	We have not yet found an example where we can prove that <math>BB^-(n, m) \ne BB(n, m)</math>		We have not yet found an example where we can prove that <math>BB^-(n, m) \ne BB(n, m)</math>

Sligocki: Created page with "The '''least busy beaver''' $BB^-(n, m)$ problem is a variation of the busy beaver problem which considers TM behavior across all starting tapes (not just blank tapes like the traditional BB problem) invented by racheline on 15 Feb 2025. == Definition == Let $BB_{init}(n, m, T)$ be the longest runtime for all n-state m-symbol TMs which halt when started on tape configuration T (where T is allowed to be any infinite tape configuration, including one..."

2025-02-16T18:04:51Z

Created page with "The '''least busy beaver''' <math>BB^-(n, m)</math> problem is a variation of the busy beaver problem which considers TM behavior across all starting tapes (not just blank tapes like the traditional BB problem) invented by racheline on 15 Feb 2025. == Definition == Let <math>BB_{init}(n, m, T)</math> be the longest runtime for all n-state m-symbol TMs which halt when started on tape configuration T (where T is allowed to be any infinite tape configuration, including one..."

New page

The '''least busy beaver''' <math>BB^-(n, m)</math> problem is a variation of the busy beaver problem which considers TM behavior across all starting tapes (not just blank tapes like the traditional BB problem) invented by racheline on 15 Feb 2025.

== Definition ==
Let <math>BB_{init}(n, m, T)</math> be the longest runtime for all n-state m-symbol TMs which halt when started on tape configuration T (where T is allowed to be any infinite tape configuration, including ones with an infinite number of non-zero values). Then

<math>BB^-(n, m) = min_T BB_{init}(n, m, T)</math>

That is the minimal value across all possible starting tapes. This minimum must exist because the values of <math>BB_{init}(n, m, T)</math> are all positive integers and thus well ordered.

Note that <math>BB_{init}(n, m, B) = BB(n, m)</math> where B is the blank (all-zeros) tape. Therefore,

<math>BB^-(n, m) \le BB(n, m)</math>

We have not yet found an example where we can prove that <math>BB^-(n, m) \ne BB(n, m)</math>