Introduction to the Busy Beaver Function - Revision history

Polygon: Introduced halting transition

2025-09-21T15:26:16Z

Introduced halting transition

← Older revision		Revision as of 15:26, 21 September 2025
Line 49:		Line 49:
	** If I see 1: Keep it a 1, Move to the Right, Go to State HALT		** If I see 1: Keep it a 1, Move to the Right, Go to State HALT

	These individual points can be called the machines instructions. These instructions can also be given names according to which state they are in and which symbol is seen, for example: The instruction of state A which is used when a 0 is seen can be called A0. Alternatively, an instruction can also be called a transition. The content of a transition is usually given in the following form: symbol that is written, direction to move in and state to transition to. The halting state is commonly referred to as either H or Z.		These individual points can be called the machines instructions. These instructions can also be given names according to which state they are in and which symbol is seen, for example: The instruction of state A which is used when a 0 is seen can be called A0. Alternatively, an instruction can also be called a transition. The content of a transition is usually given in the following form: symbol that is written, direction to move in and state to transition to. The halting state is commonly referred to as either H or Z. The transition which leads to the halting state is called the halting transition.

	Another way to show a programs transitions is in a transition table:		Another way to show a programs transitions is in a transition table:

Polygon: Added standard format

2025-09-02T11:16:00Z

Added standard format

← Older revision		Revision as of 11:16, 2 September 2025
Line 63:		Line 63:
	\|1RH		\|1RH
	\|}		\|}
			The number above each column is the symbol which is seen while the letter next to each row is the state which sees that symbol.

			Another way to represent a program is the '''standard format''', where the machines transitions are ordered based on which state they are in, beginning with state A. Different states are connected with underscores. Within a state, the transitions are ordered according to which symbol they are triggered by, beginning with 0.

			The program mentioned above would be 1RB1LB_1LA1RH in standard format.

	If you ran this program, you will see that the robot reaches the halt state on step 6, and it creates 4 ones in the process. And it turns out that this program is the best you can do with 2 states. Therefore, the busy beaver value for 2 states is 4 ones and 6 steps. In other words:		If you ran this program, you will see that the robot reaches the halt state on step 6, and it creates 4 ones in the process. And it turns out that this program is the best you can do with 2 states. Therefore, the busy beaver value for 2 states is 4 ones and 6 steps. In other words:

Polygon: Added transition table

2025-09-02T10:59:04Z

Added transition table

@@ Line 49: / Line 49: @@
 ** If I see 1: Keep it a 1, Move to the Right, Go to State HALT
-These individual points can be called the machines instructions. These instructions can also be given names according to which state they are in and which symbol is seen, for example: The instruction of state A which is used when a 0 is seen can be called A0. Alternatively, an instruction can also be called a transition.
+These individual points can be called the machines instructions. These instructions can also be given names according to which state they are in and which symbol is seen, for example: The instruction of state A which is used when a 0 is seen can be called A0. Alternatively, an instruction can also be called a transition. The content of a transition is usually given in the following form: symbol that is written, direction to move in and state to transition to. The halting state is commonly referred to as either H or Z.
 If you ran this program, you will see that the robot reaches the halt state on step 6, and it creates 4 ones in the process. And it turns out that this program is the best you can do with 2 states. Therefore, the busy beaver value for 2 states is 4 ones and 6 steps. In other words:

Polygon: Added introduction to "transition"

2025-09-02T10:46:27Z

Added introduction to "transition"

← Older revision		Revision as of 10:46, 2 September 2025
Line 48:		Line 48:
	** If I see 0: Turn it into a 1, Move to the Left, Go to State A		** If I see 0: Turn it into a 1, Move to the Left, Go to State A
	** If I see 1: Keep it a 1, Move to the Right, Go to State HALT		** If I see 1: Keep it a 1, Move to the Right, Go to State HALT

			These individual points can be called the machines instructions. These instructions can also be given names according to which state they are in and which symbol is seen, for example: The instruction of state A which is used when a 0 is seen can be called A0. Alternatively, an instruction can also be called a transition.

	If you ran this program, you will see that the robot reaches the halt state on step 6, and it creates 4 ones in the process. And it turns out that this program is the best you can do with 2 states. Therefore, the busy beaver value for 2 states is 4 ones and 6 steps. In other words:		If you ran this program, you will see that the robot reaches the halt state on step 6, and it creates 4 ones in the process. And it turns out that this program is the best you can do with 2 states. Therefore, the busy beaver value for 2 states is 4 ones and 6 steps. In other words:

Sligocki: Add some formatting, wikilinks.

2024-06-13T04:15:27Z

Add some formatting, wikilinks.

← Older revision		Revision as of 04:15, 13 June 2024
Line 1:		Line 1:
	The following is an informal explanation of what the Busy Beaver function means and how it is determined.		The following is an informal explanation of what the [[Busy Beaver function]] means and how it is determined.

	The values of the Busy Beaver function are a result of playing the Busy Beaver game.		The values of the Busy Beaver function are a result of playing the '''Busy Beaver game'''.

	Premise of the game:		Premise of the game:
Line 7:		Line 7:
	Imagine you have a robot on an infinite 1-dimensional tape full of zeros. Your friend challenges you to create a program that will allow the robot to turn those zeros into as many ones as possible.		Imagine you have a robot on an infinite 1-dimensional tape full of zeros. Your friend challenges you to create a program that will allow the robot to turn those zeros into as many ones as possible.

	You think about it for a moment, and you have a genius idea. This is your program.		You think about it for a moment, and you have a genius idea. This is your program:

	[State A]		* [State A]
			** If I see 0: Turn it into a 1, Move to the Right, Stay on State A
	If I see 0: Turn it into a 1, Move to the Right, Stay on State A		** If I see 1: N/A

	If I see 1: N/A

	Your robot turns a zero into a one, and then moves to the right. Your robot will then see another zero. This will occur infinitely often, creating an infinite number of ones! You win, right?		Your robot turns a zero into a one, and then moves to the right. Your robot will then see another zero. This will occur infinitely often, creating an infinite number of ones! You win, right?
Line 21:		Line 19:
	Ok, you think. Here is a program that can create arbitrarily many ones and then halt:		Ok, you think. Here is a program that can create arbitrarily many ones and then halt:

	[State A]		* [State A]
			** If I see 0: Turn it into a 1, Move to the Right, Go to State B
	If I see 0: Turn it into a 1, Move to the Right, Go to State B		** If I see 1: N/A
			* [State B]
	If I see 1: N/A		** If I see 0: Turn it into a 1, Move to the Right, Go to State C
			** If I see 1: N/A
	[State B]		* [State C]
			** If I see 0: Turn it into a 1, Move to the Right, Go to State D
	If I see 0: Turn it into a 1, Move to the Right, Go to State C		** If I see 1: N/A
			* [State D]
	If I see 1: N/A		** If I see 0: Turn it into a 1, Move to the Right, Go to State E
			** If I see 1: N/A
	[State C]		* [State E]
			** If I see 0: Turn it into a 1, Move to the Right, Go to State F
	If I see 0: Turn it into a 1, Move to the Right, Go to State D		** If I see 1: N/A
			* [State F]
	If I see 1: N/A		** If I see 0: Turn it into a 1, Move to the Right, Go to State HALT
			** If I see 1: N/A
	[State D]

	If I see 0: Turn it into a 1, Move to the Right, Go to State E

	If I see 1: N/A

	[State E]

	If I see 0: Turn it into a 1, Move to the Right, Go to State F

	If I see 1: N/A

	[State F]

	If I see 0: Turn it into a 1, Move to the Right, Go to State HALT

	If I see 1: N/A

	A robot running this program will create 6 ones before halting. But you can add as many states as you like, and the program will create that many ones. So you've beaten the busy beaver game—you just need an extremely large number of states.		A robot running this program will create 6 ones before halting. But you can add as many states as you like, and the program will create that many ones. So you've beaten the busy beaver game—you just need an extremely large number of states.
Line 61:		Line 42:
	For this reason, the busy beaver game sets a limit on the number of states your program can use. If we set the limit to 2 states, you can make the following program. I strongly suggest you get a paper and pencil and run this program manually. This will allow you to get a feel for how busy beaver programs work. (Note: the robot will always start on a tape full of zeros and on state A)		For this reason, the busy beaver game sets a limit on the number of states your program can use. If we set the limit to 2 states, you can make the following program. I strongly suggest you get a paper and pencil and run this program manually. This will allow you to get a feel for how busy beaver programs work. (Note: the robot will always start on a tape full of zeros and on state A)

	[State A]		* [State A]
			** If I see 0: Turn it into a 1, Move to the Right, Go to State B
	If I see 0: Turn it into a 1, Move to the Right, Go to State B		** If I see 1: Keep it a 1, Move to the Left, Go to State B
			* [State B]
	If I see 1: Keep it a 1, Move to the Left, Go to State B		** If I see 0: Turn it into a 1, Move to the Left, Go to State A
			** If I see 1: Keep it a 1, Move to the Right, Go to State HALT
	[State B]

	If I see 0: Turn it into a 1, Move to the Left, Go to State A

	If I see 1: Keep it a 1, Move to the Right, Go to State HALT

	If you ran this program, you will see that the robot reaches the halt state on step 6, and it creates 4 ones in the process. And it turns out that this program is the best you can do with 2 states. Therefore, the busy beaver value for 2 states is 4 ones and 6 steps. In other words:		If you ran this program, you will see that the robot reaches the halt state on step 6, and it creates 4 ones in the process. And it turns out that this program is the best you can do with 2 states. Therefore, the busy beaver value for 2 states is 4 ones and 6 steps. In other words:

	BB_Σ(2) = 4		* BB_Σ(2) = 4
			* BB_S(2) = 6
	BB_S(2) = 6

Peacemaker II at 03:37, 13 June 2024

2024-06-13T03:37:13Z

← Older revision		Revision as of 03:37, 13 June 2024
Line 73:		Line 73:
	If I see 1: Keep it a 1, Move to the Right, Go to State HALT		If I see 1: Keep it a 1, Move to the Right, Go to State HALT

	If you ran this program, you will see that the robot reaches the halt state on step 6, and it creates 4 ones in the process. And it turns out that this program is the best you can do with 2 states. Therefore, the busy beaver value for 2 states is 6 steps ~~and 4 ones~~. In other words:		If you ran this program, you will see that the robot reaches the halt state on step 6, and it creates 4 ones in the process. And it turns out that this program is the best you can do with 2 states. Therefore, the busy beaver value for 2 states is 4 ones and 6 steps. In other words:

	BB_Σ(2) = 4		BB_Σ(2) = 4

	BB_S(2) = 6		BB_S(2) = 6

Peacemaker II: Created an introductory page for the Busy Beaver function

2024-06-13T03:28:12Z

Created an introductory page for the Busy Beaver function

New page

The following is an informal explanation of what the Busy Beaver function means and how it is determined.

The values of the Busy Beaver function are a result of playing the **Busy Beaver game**.

Premise of the game:

Imagine you have a robot on an infinite 1-dimensional tape full of zeros. Your friend challenges you to create a program that will allow the robot to turn those zeros into as many ones as possible.

You think about it for a moment, and you have a genius idea. This is your program.

[State A]

If I see 0: Turn it into a 1, Move to the Right, Stay on State A

If I see 1: N/A

Your robot turns a zero into a one, and then moves to the right. Your robot will then see another zero. This will occur infinitely often, creating an infinite number of ones! You win, right?

Well, not quite. The busy beaver game forbids a program to have an infinite runtime (what use is a computer program that never ends?). In the busy beaver game, the robot must eventually halt.

Ok, you think. Here is a program that can create arbitrarily many ones and then halt:

[State A]

If I see 0: Turn it into a 1, Move to the Right, Go to State B

If I see 1: N/A

[State B]

If I see 0: Turn it into a 1, Move to the Right, Go to State C

If I see 1: N/A

[State C]

If I see 0: Turn it into a 1, Move to the Right, Go to State D

If I see 1: N/A

[State D]

If I see 0: Turn it into a 1, Move to the Right, Go to State E

If I see 1: N/A

[State E]

If I see 0: Turn it into a 1, Move to the Right, Go to State F

If I see 1: N/A

[State F]

If I see 0: Turn it into a 1, Move to the Right, Go to State HALT

If I see 1: N/A

A robot running this program will create 6 ones before halting. But you can add as many states as you like, and the program will create that many ones. So you've beaten the busy beaver game—you just need an extremely large number of states.

For this reason, the busy beaver game sets a limit on the number of states your program can use. If we set the limit to 2 states, you can make the following program. I strongly suggest you get a paper and pencil and run this program manually. This will allow you to get a feel for how busy beaver programs work. (Note: the robot will always start on a tape full of zeros and on state A)

[State A]

If I see 0: Turn it into a 1, Move to the Right, Go to State B

If I see 1: Keep it a 1, Move to the Left, Go to State B

[State B]

If I see 0: Turn it into a 1, Move to the Left, Go to State A

If I see 1: Keep it a 1, Move to the Right, Go to State HALT

If you ran this program, you will see that the robot reaches the halt state on step 6, and it creates 4 ones in the process. And it turns out that this program is the best you can do with 2 states. Therefore, the busy beaver value for 2 states is 6 steps and 4 ones. In other words:

BB_Σ(2) = 4

BB_S(2) = 6