Cellular automaton - Revision history

1something: /* Busy Beaver function */

2026-09-21T01:59:59Z

Busy Beaver function

← Older revision		Revision as of 01:59, 21 September 2026
Line 31:		Line 31:

	* '''Halting rule''': A cellular automaton is said to halt if the next transition rule is undefined for at least one cell.		* '''Halting rule''': A cellular automaton is said to halt if the next transition rule is undefined for at least one cell.

			=== Starting configuration ===
			To define a busy beaver function for cellular automata, we need to choose a starting pattern. Some possibilities follow.

			* '''All 0 cells''': If a cellular automaton starts in a configuration where every cell has the same state, then all future configurations will have all cells in the same state. Hence, any n-state cellular automaton will become an oscillator after at most n steps.

			* '''A single 1 cell, all other cells 0''':

	== Sources ==		== Sources ==

1something: /* Halting conditions */

2026-09-13T01:54:56Z

Halting conditions

← Older revision		Revision as of 01:54, 13 September 2026
Line 28:		Line 28:
	* '''Oscillating population''': A cellular automaton is said to halt if it reaches a state where its population (number of cells which are not 0) is cyclic. If the actual state of the cellular automaton is not cyclic, it may be nontrivial to determine whether its population will remain cyclic. In the Game of Life, it is common for small and medium-sized patterns to resolve into a collection of small still-lifes, oscillators, and gliders which travel away from the center. Such patterns never repeat, but they do have cyclic populations. Hence, most small starting patterns in Life halt under this definition but not under either of the previous three definitions.		* '''Oscillating population''': A cellular automaton is said to halt if it reaches a state where its population (number of cells which are not 0) is cyclic. If the actual state of the cellular automaton is not cyclic, it may be nontrivial to determine whether its population will remain cyclic. In the Game of Life, it is common for small and medium-sized patterns to resolve into a collection of small still-lifes, oscillators, and gliders which travel away from the center. Such patterns never repeat, but they do have cyclic populations. Hence, most small starting patterns in Life halt under this definition but not under either of the previous three definitions.

	* '''Oscillating population relative to a background pattern''': In rule 110, for any starting pattern with a finite number of on cells, the population will grow without bound. Hence, no finite patterns halt in rule 110 using any of the previous definitions.		* '''Oscillating population relative to a background pattern''': In rule 110, for any starting pattern with a finite number of on cells, the population will grow without bound. Hence, no finite patterns halt in rule 110 using any of the previous definitions. The construction of Turing-complete computation in rule 110 takes place on an infinitely repeating background pattern, which Matthew Cook calls the ''ether''. One could define the "population" of a pattern in rule 110 as the number of 1s in the symmetric difference with the ether. One could then say a pattern halts when its population relative to the ether becomes cyclic.

	* '''Halting rule''': A cellular automaton is said to halt if the next transition rule is undefined for at least one cell.		* '''Halting rule''': A cellular automaton is said to halt if the next transition rule is undefined for at least one cell.
	The construction of Turing-complete computation in rule 110 takes place on an infinitely repeating background pattern, which Matthew Cook calls the ''ether''. One could define the "population" of a pattern in rule 110 as the number of 1s in the symmetric difference with the ether. One could then say a pattern halts when its population relative to the ether becomes cyclic.

	== Sources ==		== Sources ==

Azerty: added enumerator and simulator links

2026-09-06T16:01:07Z

added enumerator and simulator links

← Older revision		Revision as of 16:01, 6 September 2026
Line 31:		Line 31:
	* '''Halting rule''': A cellular automaton is said to halt if the next transition rule is undefined for at least one cell.		* '''Halting rule''': A cellular automaton is said to halt if the next transition rule is undefined for at least one cell.
	The construction of Turing-complete computation in rule 110 takes place on an infinitely repeating background pattern, which Matthew Cook calls the ''ether''. One could define the "population" of a pattern in rule 110 as the number of 1s in the symmetric difference with the ether. One could then say a pattern halts when its population relative to the ether becomes cyclic.		The construction of Turing-complete computation in rule 110 takes place on an infinitely repeating background pattern, which Matthew Cook calls the ''ether''. One could define the "population" of a pattern in rule 110 as the number of 1s in the symmetric difference with the ether. One could then say a pattern halts when its population relative to the ether becomes cyclic.

			== Sources ==
			<references />

			* [https://github.com/AzertyWasTaken/Busy-Beaver/tree/main/Cellular%20Automaton Enumerator GitHub repo]
			* [https://azertywastaken.github.io/Busy-Beaver/Website/cellular-automaton.html Simulator website]

Azerty: /* Halting conditions */ added new halting condition

2026-09-04T11:59:46Z

Halting conditions: added new halting condition

← Older revision		Revision as of 11:59, 4 September 2026
Line 29:		Line 29:

	* '''Oscillating population relative to a background pattern''': In rule 110, for any starting pattern with a finite number of on cells, the population will grow without bound. Hence, no finite patterns halt in rule 110 using any of the previous definitions.		* '''Oscillating population relative to a background pattern''': In rule 110, for any starting pattern with a finite number of on cells, the population will grow without bound. Hence, no finite patterns halt in rule 110 using any of the previous definitions.
			* '''Halting rule''': A cellular automaton is said to halt if the next transition rule is undefined for at least one cell.
	The construction of Turing-complete computation in rule 110 takes place on an infinitely repeating background pattern, which Matthew Cook calls the ''ether''. One could define the "population" of a pattern in rule 110 as the number of 1s in the symmetric difference with the ether. One could then say a pattern halts when its population relative to the ether becomes cyclic.		The construction of Turing-complete computation in rule 110 takes place on an infinitely repeating background pattern, which Matthew Cook calls the ''ether''. One could define the "population" of a pattern in rule 110 as the number of 1s in the symmetric difference with the ether. One could then say a pattern halts when its population relative to the ether becomes cyclic.

Azerty: /* Halting conditions */

2026-08-19T06:58:20Z

Halting conditions

← Older revision		Revision as of 06:58, 19 August 2026
Line 28:		Line 28:
	* '''Oscillating population''': A cellular automaton is said to halt if it reaches a state where its population (number of cells which are not 0) is cyclic. If the actual state of the cellular automaton is not cyclic, it may be nontrivial to determine whether its population will remain cyclic. In the Game of Life, it is common for small and medium-sized patterns to resolve into a collection of small still-lifes, oscillators, and gliders which travel away from the center. Such patterns never repeat, but they do have cyclic populations. Hence, most small starting patterns in Life halt under this definition but not under either of the previous three definitions.		* '''Oscillating population''': A cellular automaton is said to halt if it reaches a state where its population (number of cells which are not 0) is cyclic. If the actual state of the cellular automaton is not cyclic, it may be nontrivial to determine whether its population will remain cyclic. In the Game of Life, it is common for small and medium-sized patterns to resolve into a collection of small still-lifes, oscillators, and gliders which travel away from the center. Such patterns never repeat, but they do have cyclic populations. Hence, most small starting patterns in Life halt under this definition but not under either of the previous three definitions.

	* '''Oscillating population relative to a background pattern''':		* '''Oscillating population relative to a background pattern''': In rule 110, for any starting pattern with a finite number of on cells, the population will grow without bound. Hence, no finite patterns halt in rule 110 using any of the previous definitions.
	In rule 110, for any starting pattern with a finite number of on cells, the population will grow without bound. Hence, no finite patterns halt in rule 110 using any of the previous definitions.

	The construction of Turing-complete computation in rule 110 takes place on an infinitely repeating background pattern, which Matthew Cook calls the ''ether''. One could define the "population" of a pattern in rule 110 as the number of 1s in the symmetric difference with the ether. One could then say a pattern halts when its population relative to the ether becomes cyclic.		The construction of Turing-complete computation in rule 110 takes place on an infinitely repeating background pattern, which Matthew Cook calls the ''ether''. One could define the "population" of a pattern in rule 110 as the number of 1s in the symmetric difference with the ether. One could then say a pattern halts when its population relative to the ether becomes cyclic.

C1: Fixed a typo./* Halting conditions */

2026-08-19T06:03:56Z

Fixed a typo.Halting conditions

← Older revision		Revision as of 06:03, 19 August 2026
Line 31:		Line 31:
	In rule 110, for any starting pattern with a finite number of on cells, the population will grow without bound. Hence, no finite patterns halt in rule 110 using any of the previous definitions.		In rule 110, for any starting pattern with a finite number of on cells, the population will grow without bound. Hence, no finite patterns halt in rule 110 using any of the previous definitions.

	The construction of Turing-complete computation in rule 110 takes place on an infinitely repeating background ~~patter~~, which Matthew Cook calls the ''ether''. One could define the "population" of a pattern in rule 110 as the number of 1s in the symmetric difference with the ether. One could then say a pattern halts when its population relative to the ether becomes cyclic.		The construction of Turing-complete computation in rule 110 takes place on an infinitely repeating background pattern, which Matthew Cook calls the ''ether''. One could define the "population" of a pattern in rule 110 as the number of 1s in the symmetric difference with the ether. One could then say a pattern halts when its population relative to the ether becomes cyclic.

1something at 01:33, 19 August 2026

2026-08-19T01:33:57Z

← Older revision		Revision as of 01:33, 19 August 2026
Line 7:		Line 7:
	The rule is defined by an 8-bit lookup table (bits for patterns 111 to 000), numbered 0 to 255. For instance:		The rule is defined by an 8-bit lookup table (bits for patterns 111 to 000), numbered 0 to 255. For instance:

	* Rule 110: Known to be Turing-complete.		* Rule 110: Known to be Turing-complete.<ref>https://wpmedia.wolfram.com/sites/13/2018/02/15-1-1.pdf</ref>
	* Rule 30: Produces chaotic, pseudorandom patterns.		* Rule 30: Produces chaotic, pseudorandom patterns.
	Cellular automata may have:		Cellular automata may have:
Line 27:		Line 27:

	* '''Oscillating population''': A cellular automaton is said to halt if it reaches a state where its population (number of cells which are not 0) is cyclic. If the actual state of the cellular automaton is not cyclic, it may be nontrivial to determine whether its population will remain cyclic. In the Game of Life, it is common for small and medium-sized patterns to resolve into a collection of small still-lifes, oscillators, and gliders which travel away from the center. Such patterns never repeat, but they do have cyclic populations. Hence, most small starting patterns in Life halt under this definition but not under either of the previous three definitions.		* '''Oscillating population''': A cellular automaton is said to halt if it reaches a state where its population (number of cells which are not 0) is cyclic. If the actual state of the cellular automaton is not cyclic, it may be nontrivial to determine whether its population will remain cyclic. In the Game of Life, it is common for small and medium-sized patterns to resolve into a collection of small still-lifes, oscillators, and gliders which travel away from the center. Such patterns never repeat, but they do have cyclic populations. Hence, most small starting patterns in Life halt under this definition but not under either of the previous three definitions.

			* '''Oscillating population relative to a background pattern''':
			In rule 110, for any starting pattern with a finite number of on cells, the population will grow without bound. Hence, no finite patterns halt in rule 110 using any of the previous definitions.

			The construction of Turing-complete computation in rule 110 takes place on an infinitely repeating background patter, which Matthew Cook calls the ''ether''. One could define the "population" of a pattern in rule 110 as the number of 1s in the symmetric difference with the ether. One could then say a pattern halts when its population relative to the ether becomes cyclic.

Azerty: added different automata types

2026-08-16T07:25:03Z

added different automata types

← Older revision		Revision as of 07:25, 16 August 2026
Line 9:		Line 9:
	* Rule 110: Known to be Turing-complete.		* Rule 110: Known to be Turing-complete.
	* Rule 30: Produces chaotic, pseudorandom patterns.		* Rule 30: Produces chaotic, pseudorandom patterns.
			Cellular automata may have:

			* Multiple number of dimensions.
			* Multiple "alive" cell states.
			* Various neighborhood radius and shape.

	== Busy Beaver function ==		== Busy Beaver function ==

			=== Halting conditions ===
	There is no single agreed-upon definition of "halting" for cellular automaton. Each possible definition of halting produces different busy beaver functions. Here are some examples.		There is no single agreed-upon definition of "halting" for cellular automaton. Each possible definition of halting produces different busy beaver functions. Here are some examples.

1something: /* Busy Beaver function */

2026-08-15T23:20:41Z

Busy Beaver function

← Older revision		Revision as of 23:20, 15 August 2026
Line 19:		Line 19:
	* '''Oscillator''': A cellular automaton is said to halt if it reaches a cycle of repeated states. Busy beaver functions for the "longest running" starting pattern or rule can measure the time until the first state which gets repeated, or the time until a state appears twice (which gives a bonus to cellular automata that end up in a long-period oscillator). Busy beaver functions counting the number of "on" states can measure the minimum population, or the maximum population, or the average population, or the population in the first repeating state.		* '''Oscillator''': A cellular automaton is said to halt if it reaches a cycle of repeated states. Busy beaver functions for the "longest running" starting pattern or rule can measure the time until the first state which gets repeated, or the time until a state appears twice (which gives a bonus to cellular automata that end up in a long-period oscillator). Busy beaver functions counting the number of "on" states can measure the minimum population, or the maximum population, or the average population, or the population in the first repeating state.

	* '''Oscillating population''': A cellular automaton is said to halt if it reaches a state where its population (number of cells which are not 0) is cyclic. If the actual state of the cellular automaton is not cyclic, it may be nontrivial to determine whether its population will remain cyclic.		* '''Oscillating population''': A cellular automaton is said to halt if it reaches a state where its population (number of cells which are not 0) is cyclic. If the actual state of the cellular automaton is not cyclic, it may be nontrivial to determine whether its population will remain cyclic. In the Game of Life, it is common for small and medium-sized patterns to resolve into a collection of small still-lifes, oscillators, and gliders which travel away from the center. Such patterns never repeat, but they do have cyclic populations. Hence, most small starting patterns in Life halt under this definition but not under either of the previous three definitions.

	In the Game of Life, it is common for small and medium-sized patterns to resolve into a collection of small still-lifes, oscillators, and gliders which travel away from the center. Such patterns never repeat, but they do have cyclic populations. Hence, most small starting patterns in Life halt under this definition but not under either of the previous three definitions.

1something: /* Busy Beaver function */

2026-08-15T23:20:28Z

Busy Beaver function

← Older revision		Revision as of 23:20, 15 August 2026
Line 11:		Line 11:

	== Busy Beaver function ==		== Busy Beaver function ==
	~~TODO~~		There is no single agreed-upon definition of "halting" for cellular automaton. Each possible definition of halting produces different busy beaver functions. Here are some examples.

			* '''All 0s''': A cellular automaton is said to halt if it reaches a state where every cell has state 0.

			* '''Still life''': A cellular automaton is said to halt if it reaches a fixed point in the rule's update function. This definition of halting allows busy beaver functions which count the maximum number of on cells a halting cellular automaton can produce.

			* '''Oscillator''': A cellular automaton is said to halt if it reaches a cycle of repeated states. Busy beaver functions for the "longest running" starting pattern or rule can measure the time until the first state which gets repeated, or the time until a state appears twice (which gives a bonus to cellular automata that end up in a long-period oscillator). Busy beaver functions counting the number of "on" states can measure the minimum population, or the maximum population, or the average population, or the population in the first repeating state.

			* '''Oscillating population''': A cellular automaton is said to halt if it reaches a state where its population (number of cells which are not 0) is cyclic. If the actual state of the cellular automaton is not cyclic, it may be nontrivial to determine whether its population will remain cyclic.

			In the Game of Life, it is common for small and medium-sized patterns to resolve into a collection of small still-lifes, oscillators, and gliders which travel away from the center. Such patterns never repeat, but they do have cyclic populations. Hence, most small starting patterns in Life halt under this definition but not under either of the previous three definitions.