Algebraic Circuits - Revision history

Admin: Fix typo: boolaen → boolean (via update-page on MediaWiki MCP Server)

2026-06-05T22:27:25Z

Fix typo: boolaen → boolean (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 22:27, 5 June 2026
Line 279:		Line 279:
	</math>		</math>

	is a nonlinear function. But any ~~boolaen~~ function can be uniquely expressed as a polynomial in GF(2) (Reed-Muller expansion). The polynomial that represents the local update rule is the algebraic core of the circuit of a single cell.		is a nonlinear function. But any boolean function can be uniquely expressed as a polynomial in GF(2) (Reed-Muller expansion). The polynomial that represents the local update rule is the algebraic core of the circuit of a single cell.

	==Galois Fields and Cellular Automata==		==Galois Fields and Cellular Automata==

Admin: Fix formula error: birth term should use (1 ⊕ c) not (1 · c); also fix typo we'e → we've (via update-page on MediaWiki MCP Server)

2026-06-05T22:27:20Z

Fix formula error: birth term should use (1 ⊕ c) not (1 · c); also fix typo we'e → we've (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 22:27, 5 June 2026
Line 234:		Line 234:

	<math>		<math>
	c^{\prime} = \left[ c \cdot \left( P_2 \oplus P_3 \right) \right] \oplus \left[ \left( 1 \~~cdot~~ c \right) \cdot P_3 \right]		c^{\prime} = \left[ c \cdot \left( P_2 \oplus P_3 \right) \right] \oplus \left[ \left( 1 \oplus c \right) \cdot P_3 \right]
	</math>		</math>

Line 252:		Line 252:
	** Use logic gates and/xor/not, or GF(2) equivalents like multiplication/addition, to get the next state		** Use logic gates and/xor/not, or GF(2) equivalents like multiplication/addition, to get the next state

	Now, we'e assembled an algebraic circuit for a single cell, and it can be connected to 8 other algebraic circuits for the neighbor cells, and if all circuits were driven by a common clock, they could all update synchronously.		Now, we've assembled an algebraic circuit for a single cell, and it can be connected to 8 other algebraic circuits for the neighbor cells, and if all circuits were driven by a common clock, they could all update synchronously.

	===Connecting to Turing Completeness and Life in Life===		===Connecting to Turing Completeness and Life in Life===

Unknown user: /* Chapter Summaries */

2026-04-13T23:59:27Z

Chapter Summaries

← Older revision		Revision as of 23:59, 13 April 2026
Line 26:		Line 26:
	** '''Appendix B: Polynomial Algebra:''' Focuses on the algebra of polynomials, paying particular attention to their different forms of representation.		** '''Appendix B: Polynomial Algebra:''' Focuses on the algebra of polynomials, paying particular attention to their different forms of representation.
	** '''Appendix C: Elliptic Curves:''' Includes all matters relating to elliptic curves that are used in the application examples of Galois fields developed in Chapter 7.		** '''Appendix C: Elliptic Curves:''' Includes all matters relating to elliptic curves that are used in the application examples of Galois fields developed in Chapter 7.


	=Details=		=Details=

Unknown user at 23:11, 10 May 2025

2025-05-10T23:11:59Z

Show changes

Unknown user: /* Summary */

2025-05-10T23:02:15Z

Summary

Show changes

Unknown user at 22:27, 10 May 2025

2025-05-10T22:27:58Z

← Older revision		Revision as of 22:27, 10 May 2025
Line 1:		Line 1:
	This page contains notes on ''Algebraic Circuits'' by Antonio Lloris Ruiz, Encarnación Castillo Morales, Luis Parrilla Roure, Antonio García Ríos		This page contains notes on ''Algebraic Circuits'' by Antonio Lloris Ruiz, Encarnación Castillo Morales, Luis Parrilla Roure, Antonio García Ríos

			[[Image:Algebraic Circuits Cover.png\|200px]]

	=Summary=		=Summary=

Unknown user at 22:26, 10 May 2025

2025-05-10T22:26:54Z

← Older revision		Revision as of 22:26, 10 May 2025
Line 1:		Line 1:
			This page contains notes on ''Algebraic Circuits'' by Antonio Lloris Ruiz, Encarnación Castillo Morales, Luis Parrilla Roure, Antonio García Ríos

	=Summary=		=Summary=

Line 226:		Line 228:

	In essence, the Galois Field provides the number system and arithmetic for the cell states. The polynomial representation captures the logic of the local update rule, which forms the basis of the algebraic circuit for each cell in the automaton, regardless of its linearity or dimensionality. Linear CAs over <math>\text{GF}(k)</math> just happen to have very elegant global algebraic descriptions via their characteristic polynomials.		In essence, the Galois Field provides the number system and arithmetic for the cell states. The polynomial representation captures the logic of the local update rule, which forms the basis of the algebraic circuit for each cell in the automaton, regardless of its linearity or dimensionality. Linear CAs over <math>\text{GF}(k)</math> just happen to have very elegant global algebraic descriptions via their characteristic polynomials.

			=Flags=

			{{ReadingFlag}}

Unknown user: /* Multi-State CAs with Cycling Dead States */

2025-05-10T22:25:22Z

Multi-State CAs with Cycling Dead States

← Older revision		Revision as of 22:25, 10 May 2025
Line 220:		Line 220:
	# '''Choose the appropriate Galois Field.''' If <math>k=4</math>, use <math>\text{GF}(2^2)</math>. Assign each state to an element of <math>\text{GF}(2^2)</math> (e.g., using a polynomial basis like <math>ax+b</math> over <math>\text{GF}(2)</math>, the states could be <math>(0,0), (0,1), (1,0), (1,1)</math>).		# '''Choose the appropriate Galois Field.''' If <math>k=4</math>, use <math>\text{GF}(2^2)</math>. Assign each state to an element of <math>\text{GF}(2^2)</math> (e.g., using a polynomial basis like <math>ax+b</math> over <math>\text{GF}(2)</math>, the states could be <math>(0,0), (0,1), (1,0), (1,1)</math>).
	# '''Write down the transition rules explicitly.''' For each possible state of the central cell and each possible configuration of its neighbors (or a summary like "sum of 'Alive' neighbors"), define the next state of the central cell. This defines the function <math>f</math>.		# '''Write down the transition rules explicitly.''' For each possible state of the central cell and each possible configuration of its neighbors (or a summary like "sum of 'Alive' neighbors"), define the next state of the central cell. This defines the function <math>f</math>.
	#* The "cycling through dead states" means if <math>c = \text{~~Dead_2~~}</math>, then <math>c' = \text{~~Dead_3~~}</math> (perhaps regardless of neighbors, or with some conditions).		#* The "cycling through dead states" means if <math>c = \text{Dead2}</math>, then <math>c' = \text{Dead3}</math> (perhaps regardless of neighbors, or with some conditions).
	#* The "cannot be reborn" condition means: if <math>c \in \{\text{~~Dead_2~~, ~~Dead_3~~}\}</math> AND (birth condition based on neighbors is met), then <math>c'</math> is ''not'' "Alive", but perhaps stays in its cycle or goes to Dead_1.		#* The "cannot be reborn" condition means: if <math>c \in \{\text{Dead2, Dead3}\}</math> AND (birth condition based on neighbors is met), then <math>c'</math> is ''not'' "Alive", but perhaps stays in its cycle or goes to Dead_1.
	# '''Convert this set of rules into a polynomial over <math>\text{GF}(k)</math> for <math>f</math>.''' This can be complex for many states and non-linear rules but is always theoretically possible. For programmatic implementation, this often translates to lookup tables or nested conditional statements which are themselves implementations of this polynomial.		# '''Convert this set of rules into a polynomial over <math>\text{GF}(k)</math> for <math>f</math>.''' This can be complex for many states and non-linear rules but is always theoretically possible. For programmatic implementation, this often translates to lookup tables or nested conditional statements which are themselves implementations of this polynomial.
	# The '''algebraic circuit''' for one cell is the implementation of this polynomial using adders, multipliers, and constants from <math>\text{GF}(k)</math>.		# The '''algebraic circuit''' for one cell is the implementation of this polynomial using adders, multipliers, and constants from <math>\text{GF}(k)</math>.

	In essence, the Galois Field provides the number system and arithmetic for the cell states. The polynomial representation captures the logic of the local update rule, which forms the basis of the algebraic circuit for each cell in the automaton, regardless of its linearity or dimensionality. Linear CAs over <math>\text{GF}(k)</math> just happen to have very elegant global algebraic descriptions via their characteristic polynomials.		In essence, the Galois Field provides the number system and arithmetic for the cell states. The polynomial representation captures the logic of the local update rule, which forms the basis of the algebraic circuit for each cell in the automaton, regardless of its linearity or dimensionality. Linear CAs over <math>\text{GF}(k)</math> just happen to have very elegant global algebraic descriptions via their characteristic polynomials.

Unknown user: /* GF(3) and Beyond */

2025-05-10T22:24:00Z

GF(3) and Beyond

@@ Line 169: / Line 169: @@
 The extensions the book does cover are for <math>GF(2^n)</math> or <math>GF(p)</math>, powers of 2 or prime numbers. In this case, we can think about the cellular automaton's state being updated by carrying out the update rules/operations over <math>GF(2^n)</math> or <math>GF(p)</math>.
-* Number of distinct states in a CA can directly determine the type of Galois Field that provides the natural algebraic framework for its circuit behavior
+====Role of Galois Fields and the Number of Cell States====
-* If a cell has p states, where p is a prime: the states can be mapped onto elements of the Galois field <math>GF(p) = 0, 1, \dots, p-1</math>. All arithmetic operations (addition, multiplication) are then performed modulo p
+The number of distinct states a cell in a CA can take directly determines the type of Galois Field (GF) that provides the natural algebraic framework for describing its behavior:
-* If a cell has k states, where k some power m of a prime p, <math>k = p^m</math>, then these states can be mapped onto the Galois Field <math>GF(p^m)</math>. Operations are defined by the arithmetic of this extension field.
+* '''If a cell has <math>k</math> states, and <math>k</math> is a prime number <math>p</math>:''' The states can be mapped to the elements of the Galois Field <math>\text{GF}(p) = \{0, 1, \dots, p-1\}</math>. All arithmetic operations (addition, multiplication) used in defining the CA's rules are then performed modulo <math>p</math>.
-** Example: suppose CA had 4 states. These map to the elements of <math>GF(2^2)</math>. Operations would involve polynomial arithmetic modulo an irreducible polynomial of degree 2 over GF(2)
+**Example:** If a CA has 3 states (e.g., "Alive," "Decaying," "Dead"), these can be mapped to the elements 0, 1, 2 of <math>\text{GF}(3)</math>.
-* The Galois Field provides the consistent mathematical system (the "algebra") within which the cell state transitions (the "circuit" logic) are defined.
+The Galois Field provides the consistent mathematical system (the "algebra") within which the cell state transitions (the "circuit" logic) are defined.

Unknown user: /* GF(3) and Beyond */

2025-05-10T22:14:09Z

GF(3) and Beyond

← Older revision		Revision as of 22:14, 10 May 2025
Line 164:		Line 164:

	===GF(3) and Beyond===		===GF(3) and Beyond===

			The provided book, "Algebraic Circuits," lays some groundwork for thinking about this case, although it mainly focuses on GF(2) (binary automata).

			The extensions the book does cover are for <math>GF(2^n)</math> or <math>GF(p)</math>, powers of 2 or prime numbers. In this case, we can think about the cellular automaton's state being updated by carrying out the update rules/operations over <math>GF(2^n)</math> or <math>GF(p)</math>.

			1. Role of Galois Field and Number of Cell States

			* Number of distinct states in a CA can directly determine the type of Galois Field that provides the natural algebraic framework for its circuit behavior

			* If a cell has p states, where p is a prime: the states can be mapped onto elements of the Galois field <math>GF(p) = 0, 1, \dots, p-1</math>. All arithmetic operations (addition, multiplication) are then performed modulo p
			** Example: Suppose there are 3 states (alive/decaying/dead) - these can be mapped to 0, 1, 2 in GF(3)

			* If a cell has k states, where k some power m of a prime p, <math>k = p^m</math>, then these states can be mapped onto the Galois Field <math>GF(p^m)</math>. Operations are defined by the arithmetic of this extension field.
			** Example: suppose CA had 4 states. These map to the elements of <math>GF(2^2)</math>. Operations would involve polynomial arithmetic modulo an irreducible polynomial of degree 2 over GF(2)

			* The Galois Field provides the consistent mathematical system (the "algebra") within which the cell state transitions (the "circuit" logic) are defined.