LifeWiki - User contributions [en]

Cottonmouth

2026-06-09T02:33:08Z

Rei: fix forum title

{{Spaceship
|name = Cottonmouth
|pname = cottonmouth
|type = Pushalong
|c = 78
|bx = 10
|by = 34
|dir = Orthogonal
|p = 10
|m = 10
|s = c/10
|z = c/10
|h = 82
|symmetry = -c
|discoverer = AforAmpere
|discoveryear = 2018
|rulemin = B3/S23
|rulemax = B38/S238
|rulespecial = [[Conway's Game of Life|Conway Life]]
|isorulemin = B3-ky/S23-ck
|isorulemax = B34ce5k6ae7c8/S234ce5ekn6-ae7e8
|plaintext = true
|rle = true
|synthesis = 118
|viewerconfig = #C [[ TRACKLOOP 10 0 -1/10 THUMBSIZE 3 GPS 5 WIDTH 480 HEIGHT 800 ]]
|apgcode = xq10_wo5995oz0gusoosugzst2y02tszwr4w4rzwos22soz08d0330d8zxc22c
}}
'''Cottonmouth''' is a [[c/10 orthogonal]] [[pushalong]] for the [[copperhead]] and [[fireship]] discovered by [[AforAmpere]] on 24 March {{year|2018}}.<ref>{{LinkForumThread|f=2|t=2031|p=58357|title=Re: Spaceship Discussion Thread|author=AforAmpere|date=24 March 2018|format=ref}}</ref> It is infinitely [[extensible]] because it has a copperhead-like formation in the front on which another cottonmouth can be placed.

{{EmbedViewer
|pname = cottonmouthextended
|viewerconfig = #C [[ AUTOSTART GPS 5 TRACKLOOP 10 0 -1/10 THUMBLAUNCH THUMBSIZE 2 THEME 6 ZOOM 8 WIDTH 480 HEIGHT 720 ]]
|position = center
|caption = The extended version of cottonmouth, attached to both a [[copperhead]] (left) and a [[fireship]] (right)
|style = width:360px;
}}

== Synthesis ==
On June 8, {{year|2026}}, [[vilc]] found a {{gliders|118}} synthesis of cottonmouth, starting from a copperhead and using 105 additional gliders to append the cottonmouth pushalong.<ref name="post229583"/><ref name="j14752485318"/>

== References ==

<references>
<ref name="j14752485318">{{CiteCatagolueJob|job=14752485318|date=June 8, 2026}}</ref>
<ref name="post229583">{{LinkForumThread
|format = ref
|p = 229583
|title = Re: Small Spaceship Syntheses
|author = vilc
|date = June 8, 2026
}}</ref>
</references>

== External links ==
* {{LinkCatagolue|xq10_wo5995oz0gusoosugzst2y02tszwr4w4rzwos22soz08d0330d8zxc22c}}
* {{LinkWikipedia|Cottonmouth}} (name origin)

[[Category:Patterns discovered by pseudonymous users]]

Universal computer

2026-04-19T15:26:17Z

Rei: Add the 323

{{Glossary}}
A '''universal computer''' in a [[cellular automaton]] is a system that can compute anything that a [http://en.wikipedia.org/wiki/Turing_machine Turing machine] can compute (another term for this is '''Turing-complete'''). A cellular automaton in which such a system exists is called '''universal'''. A universal computer may be either infinite or finite, but when combined with a [[universal constructor]], it is assumed to be finite.

==Universal computers in Life==
In 1982, [[John Conway]] proved in ''[[Winning Ways]]'' that the [[Game of Life]] has a (finite) universal computer, as well as a universal constructor. Proving the universality of a cellular automaton with simple rules was in fact Conway's aim in Life right from the start. The universal computer uses [[glider]] logic and a [[sliding block memory]], and the proof of its existence is also outlined in [[The Recursive Universe]].

In April 2000, [[Paul Rendell]] constructed a direct implementation of a [[Turing machine]].<ref>{{cite web|url=http://rendell-attic.org/gol/tm.htm|title=A Turing Machine in Conway's Game of Life|author=Paul Rendell|date=April 2, 2000}}</ref> This computer is infinite, as it requires an infinite length of tape for the Turing Machine.

In 2002, using [[Dean Hickerson]]'s [[sliding block memory]], [[Paul Chapman]] constructed an implementation of a Minsky Register Machine (a machine of the same capability as a Turing Machine), which he extended to a Universal Register Machine, a finite universal computer.<ref>{{cite web|url=http://www.igblan.free-online.co.uk/igblan/ca/|title=Life Universal Computer|author=Paul Chapman|date=November 11, 2002|archiveurl=https://web.archive.org/web/20230716132432/http://www.igblan.free-online.co.uk/igblan/ca/|archivedate=July 16, 2023}}</ref>

In 2009, [[Adam P. Goucher]] built a [[Spartan universal computer-constructor]], which has three infinite binary memory tapes (program tape, data tape and marker tape). This allows data to be stored in linear space, rather than the exponential space that a Register Machine uses.

In 2010, Paul Rendell completed a [[universal Turing machine|universal version]] of his Turing machine pattern, followed in 2011 by a [[fully universal Turing machine|fully universal]] version, removing the previous requirement (needed for true universality) that the initial Life pattern must have unbounded size and infinite population.

In 2016, [[Nicolas Loizeau]] created an [[8-bit programmable computer]] pattern, using only four basic parts: a [[twogun|period-60 glider gun]], a [[buckaroo|90° glider reflector]], a p30 [[glider duplicator]], and a [[eater1|glider eater]]. Later an improved scalable version was announced in 2021.

In December 2024, [[blah]] created the 323, a 32-bit load-store CPU designed for the [[HashLife]] algorithm.<ref name="post200720" /> It uses a von-Neumann architecture with 15 registers and the RAM.

==Universal computers in other cellular automata==
===In [[Life-like cellular automata]]===
For a universal computer to be finite, it must either be given sufficient memory for a computation prior, or employ a universal constructor. For the latter case, it must be able to escape its own bounding box and diamond, so in a non-strobing rule, its rulestring must contain at least one of the birth transitions <tt>{1,2,3}</tt>, or when [[isotropic non-totalistic]], at least one birth transition in each of the sets <tt>{1c,1e,2c,2a,3i}</tt> and <tt>{1c,1e,2e,2a,3a}</tt>, respectively, meaning there is an upper bound of <tt>2101+2100+(299+298+297)2/299=145*295</tt> INT rules with Turing-complete finite patterns on infinite planes.

For strobing rules, where <tt>~</tt> denotes the absence of a transition, these prerequisite sets are instead <tt>{~b1c,~b1e,~b2c,~b2a,~b3i,s7c,s7e,s6c,s6a,s5i}</tt> and <tt>{~b1c,~b1e,~b2e,~b2a,~b3a,s7c,s7e,s6e,s6a,s5a}</tt>.

[[David Eppstein]] and Dean Hickerson proved that {{rl|B35/S236}} has a universal computer and universal constructor, using the same method of proof that Conway used to prove that Life is universal.<ref>{{cite web|url=http://www.ics.uci.edu/~eppstein/ca/b35s236/|title=B35/S236|author=D. Eppstein}}</ref>

===In multi-state circuitry rules===
[[Tim Hutton]] has implemented [[Codd]]'s design for a universal computer in Codd's 8-state cellular automaton.<ref>{{cite web|url=https://github.com/GollyGang/ruletablerepository/wiki/CoddsDesign|title=Rule Table Repository|author=Tim Hutton}}</ref>

The well-known rule {{rl|WireWorld}} allows construction of very small and robust logic gates, triggers, memory banks etc. In September 2004 David Moore and Mark Owen released a Wireworld computer, in which the results of calculations are shown in seven-segment displays by running "electrons". The computer's instruction set is a highly orthogonal RISC architecture. The program, CPU status and data are stored in a bank of 64 16-bit registers. According to the authors, the computer was designed, with the help of many others, between 1990 and 1992. The version of it included in [[Golly]] is preprogrammed to compute and display the sequence of [[prime number]]s. Likely this was the first computer in a cellular automaton that looks like a computer from human perspective.

In 2021 [[Yoel Matveyev]] released the largest known cellular automation computer called [[Izhora]] based on his own 4-state rule FireWorld.<ref name="post136309" /> It has 256 kilobytes of memory, a {{times|256|128}} memory-mapped pixel display and a keyboard driven by a [[Golly]] script. Its 32-bit CPU uses a single operation, subtract and branch if zero or negative (SUBLEQ), from which all other operations can be synthesized. Examples include 256-bit factorials, primes and Fibonacci numbers. Tools such as an assembler and emulator are provided for programming it.

Other examples of cellular automation computers include a partial emulation of a real-world Picoblaze microcontroller and a custom multicore CPU.

==Universality of predecessor-finding==
On August 20, 2023, [[Ville Salo]] and [[Ilkka Törmä]] proved that arbitrary [[Boolean satisfiability problem]]s could be encoded to problems of finding predecessors of specific patterns, with the corollary that the process of reversing a single iteration (or otherwise proving that a pattern is a [[Garden of Eden]]) is computationally universal.<ref name="arxiv2308.10198" />

==References==
<references>
<ref name="post200720">{{LinkForumThread
|p = 200720
|format = ref
|title = The 323: A 32-bit computer
|author = blah
|date = December 31, 2024
}}</ref>
<ref name="post136309">{{LinkForumThread
|p = 136309
|format = ref
|title = Izhora (Fireworld2 computer)
|author = Yoel Matveyev
|date = October 5, 2021
}}</ref>
<ref name="arxiv2308.10198">[[Ville Salo]], [[Ilkka Törmä]], [https://arxiv.org/abs/2308.10198 ''Computing backwards with Game of Life, part 1: wires and circuits'']</ref>
</references>

==External links==
* {{LinkWikipedia|Turing_completeness|name=Turing completeness}}
* {{LinkLexicon|lex_u.htm#universalcomputer}}
* {{LinkForumThread|f=11|t=3362|title=Resources pertaining to computation in cellular automata}}

[[Category:Universal computation| ]]

APGsembly

2026-04-19T13:45:27Z

Rei: Add description for MUL action

The '''general purpose calculator''' ('''GPC''') is a way to implement computational tasks inside Conway's Game of Life. It is [[Turing complete]] and programmed by a special-purpose programming language called '''APGsembly'''. The first computational Life patterns using this technology were constructed by [[Adam P. Goucher]] in 2009 and 2010. The [[Spartan universal computer-constructor]], [[pi calculator]] and [[phi calculator]] patterns, and a related pattern programmed to grow at [[Osqrtlogt|O(sqrt(log(t)))]], had all the same basic general-purpose components that make up the GPC.

Goucher's original compiler/editor was written in DarkBasic, which became difficult to run on modern computers. In 2019 a Golly Python-script compiler was written by [[Dave Greene]] to create a Conway's Life pattern corresponding to APGsembly code, and a visual emulator and debugger was written by [[Michael Simkin]] and Dave Greene. At that time the logic circuitry was adjusted to include a standard set of components, and the resulting "GPC" was shown to be capable of supporting any of the three programs (pi, phi, or Osqrtlogt). In 2024, branoc created a version of the compiler and emulator based on the updated specifications from ''[[Conway's Game of Life: Mathematics and Construction]]'' textbook.<ref name="post199807" />

The base GPC pattern includes just the logic and memory circuitry; an additional subpattern representing an APGsembly program should be attached to a GPC to produce a complete calculator, printer, or other functional pattern. The additional subpattern is basically a finite-state machine. Each line in an APGsembly program corresponds to a state, and there are JUMP instructions for each possible return value (Z or NZ), pointing to the next state that the machine should enter. Each line of code can trigger one or more commands, or "actions", and it's important to make sure that each line includes exactly one action that returns a zero/nonzero value.

== Overview ==

The GPC includes a ticking clock in the form of two synchronized glider guns of period 2^17, 2^18 or higher, depending on the size of the program. These guns emit a glider each time an action has been executed with a return value of either Z or NZ, represented by a glider emitted on one of two possible output [[lane]]s, as a result of the most recent output-producing action. These actions are triggered by an input glider emitted by the calculator program pattern, sent into special computational units on specific lanes to trigger a specific action (ADD, SUB, WRITE, READ, INC, etc.) defined by the APGsembly code.

Thus the GPC has four major physical components:

# Clock.
# Program code.
# Computational unit array.
# Printer and B2D.

== The computational cycle ==

Every 2^N generations, a glider gun initiates an action based on the output from the previous cycle. The gun waits long enough that an output has most likely returned. If no output has in fact appeared (this can happen when retrieving data from a very long data tape, for example) the gun waits for another cycle and checks again, using a [[universal regulator]] mechanism.
* The return signal is always a one-bit output value, either Z or NZ.
* Each cycle is expected to return exactly one such output.

== Program code ==

APGsembly code consists of a list of actions to be performed for each ''state ID'', for each possible return value (Z or NZ). The program consists of lines of code; each state ID corresponds to two lines of code, one for Z and one for NZ.
#The program must start with INITIAL, and will halt if it ever executes HALT_OUT (or HALT) action.
#Two or more actions with Z/NZ responses for a single state are technically illegal, and will likely (though not inevitably) cause chaotic explosions in the calculator pattern.

Each line of code consists of 4 parts, separated by semicolons and optional whitespace:

'''StateID; Z/NZ; NextStateID; Action1, Action2, Action3, etc.'''

#'''StateID.''' Each line's first element is a state ID. This can be thought of as a line number, except that pairs of successive lines usually share the same state ID.
#'''Z/NZ.''' Each line's second element is either Z or NZ. Only the line matching the Z or NZ return value from the previous cycle will actually be executed.
#'''NextStateID.''' Each line's third element defines the state that will be executed on the next clock tick, if that line is executed.
#'''Action.''' Each line's fourth element defines a comma-separated list of actions to be executed. These actions are inputs to the computational units. Some actions will not return anything and only change the state of the computational unit; some will return either Z or NZ depending on the internal state of a particular unit. It is the programmer's task to make sure there is exactly one return value.

'''Example:'''

#COMPONENTS B0
INITIAL; Z; A2; NOP
INITIAL; NZ; A2; NOP
A1; Z; A2; INC B0, NOP
A1; NZ; A2; INC B0, NOP
A2; Z; A1; SET B0, NOP
A2; NZ; A1; SET B0, NOP

This loads the B0 register with an increasing number of '1' bits. Notice that each state ID '''INITIAL''', '''A1''', and '''A2''' appears twice in the program, once for each possible Z return and once for each NZ return.

A syntactic shortcut added in the new compiler is the use of "*" to mean "both Z and NZ", and "ZZ" to mean "only Z is possible" for a given state. The above sample program could be written more compactly as

#COMPONENTS B0
INITIAL; ZZ; A2; NOP
A1; *; A2; INC B0, NOP
A2; *; A1; SET B0, NOP

== Computational units ==

There are currently 6 types of logic units, though it is possible to add more. Each type of logic unit has one or more actions, triggered by glider inputs on specific lanes.

# ''NOP'' - The NOP action sends a Z output directly, and takes no other action.
# ''HALT'' - The HALT_OUT action halts the entire computation and emits a glider. The HALT action halts the entire computation without emitting a glider.
# ''U'' - sliding block register (holds a single integer value, stored in unary)
# ''B'' - binary string register (holds an arbitrary-length string of binary digits)
# ''ADD'' - adder
# ''SUB'' - subtractor
# ''MUL'' - multiplier
# ''B2D'' - a two-dimensional binary register.

The calculator can have an arbitrary number of U, B, ADD, SUB, and MUL units, one B2D unit, and one digit printer or character printer. Future versions of the compiler/emulator will support other components, such as an arbitrary number of fixed-width B2D units.

Before 2021, "U" was written as "R" (short for "register"), and "B2D" was written as "SQ" (short for "square"). The "T" (short for "tape") unit was an older version of the binary register, and differed in some ways from the B unit.<ref name="rename2021" />

=== U: Sliding block register ===

* Sliding block registers in APGsembly code are denoted by keywords starting with the letter U, short for "unary" -- for example, U0, U1, U2, etc.
* A sliding block register has very simple logic. It represents a single number, and all you can do with it is INC (increase by 1) and TDEC (test and decrease by 1).

'''U Actions:'''

* ''INC Ux'' will increase the register by 1. No return signal.
* ''TDEC Ux'' will decrease the register by 1. Returns NZ if the register > 0, otherwise Z.

=== B: Binary string register ===

* Binary string registers in APGsembly code are denoted by keywords starting with B, short for "binary" -- for example, B0, B1, B2, etc.
* A binary string register has a "reading head" that can be moved forward and backward along the tape with INC and TDEC, just like a sliding block register.
* A binary string register can store arbitrarily-large binary strings. A program can only retrieve one bit at a time using READ command. SET might be more clearly named "WRITE 1", but SET is the terms used in existing APGsembly.

'''B Actions'''

* ''INC Bx'' increases the position of reading head. No return signal.
* ''TDEC Bx'' decreases the position of reading head. Returns NZ unless at 0.
* ''READ Bx'' returns the state of the binary string value located at reading head and then sets it equal to 0. Returns Z if the value is 0 and NZ if 1.
* ''SET Bx'' sets the state of the current binary bit to 1 (breaks if the cell is set to 1). No return signal.

=== ADD: adder ===

One should think about the adder as having a 2-bit number. An A input just changes the state of the adder unit, whereas a B input returns the result.

* ''A0'' is not implemented as an input, because there is nothing to change.

'''ADD Actions'''
* ''ADD A1'' increments the number (modulo 4). No return signal.

{| class="wikitable"
! Current !! Next
|-
| 00 || 01
|-
| 01 || 10
|-
| 10 || 11
|-
| 11 || 00
|}

* ''ADD B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || Z
|-
| 01 || 00 || NZ
|-
| 10 || 01 || Z
|-
| 11 || 01 || NZ
|}

* ''ADD B1'' increments and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || NZ
|-
| 01 || 01 || Z
|-
| 10 || 01 || NZ
|-
| 11 || 00 || Z
|}

=== SUB: subtractor ===

The subtractor works same as the adder, but using 2-bit two's complement arithmetic.

'''SUB Actions'''
* ''SUB A1'' increments the number (modulo 4). No return signal.

{| class="wikitable"
! Current !! Next
|-
| 00 || 01
|-
| 01 || 10
|-
| 10 || 11
|-
| 11 || 00
|}

* ''SUB B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || Z
|-
| 01 || 00 || NZ
|-
| 10 || 11 || Z
|-
| 11 || 11 || NZ
|}

* ''SUB B1'' decrements and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 11 || NZ
|-
| 01 || 00 || Z
|-
| 10 || 00 || NZ
|-
| 11 || 11 || Z
|}

=== MUL ===

MUL keeps a number between 0 and 10 in an internal register. MUL 0 divides the number by 2 (i.e., bit shifts it by 1 bit), and MUL 1 adds 10 and ''then'' divides the number by 2. The point of doing this is that performing MUL commands in succession can be used to multiply binary numbers one bit at a time, with the internal memory of the MUL component keeping track of future carry bits. This is used in the digit extraction step of the [[pi calculator|pi]] and [[phi calculator]] programs.

'''MUL Actions'''
* ''MUL 0'' divides the number by 2. Returns Z if the value before the action is even and NZ if odd.
* ''MUL 1'' adds 10 and then divides the number by 2. Returns Z if the value before the action is even and NZ if odd.

=== B2D: 2d binary register ===

* B2D is two-dimensional binary register and is unbounded in positive X and Y directions.
* B2D can be used as memory array as well as 2d plotter.
* B2D register commands contain the string "B2D" in APGsembly code -- e.g., INC B2DX, TDEC B2DX, READ B2D, etc.
* The B2D has two arms X and Y. Each arm can be moved with INC and TDEC -- e.g., INC B2DX, TDEC B2DY.
* A program can retrieve a bit located at (X, Y) via the READ B2D command. READ B2D will always set the (X, Y) bit back to 0 (empty space). This means there is no need for a RESET B2D command, so only SET B2D is implemented.

'''B2D Actions'''
* ''INC B2DX'' increases the position of the X arm. No return signal.
* ''INC B2DY'' increases the position of the Y arm. No return signal.
* ''TDEC B2DX'' decreases the position of X arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''TDEC B2DY'' decreases the position of Y arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''READ B2D'' returns the state of the binary value located at (X, Y) and then sets it equal to 0. Returns Z if the value is 0 (empty), otherwise NZ.
* ''SET B2D'' sets the state at (X, Y) to 1 (breaks if the cell is set to 1). No return signal.

=== Digit printer ===

The ''digit printer'' can print "." and digits 0-9. No return signal.

'''Digit printer actions'''
* ''OUTPUT x'', for x = ., 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.

== Further details ==
* For further discussion and examples, or to ask questions, see [https://conwaylife.com/forums/viewtopic.php?f=2&t=4196 this conwaylife.com forum thread].
* [[Conway's Game of Life: Mathematics and Construction]], Chapter 9: Universal Computation
* [https://conwaylife.com/forums/viewtopic.php?p=221972#p221972 A compiler and emulator] written in Lua for use in Golly.
* [https://github.com/dvgrn/b3s23life/tree/main/calculator A compiler and debugger] for use in Golly. This is an old (1.0) version.
* [https://rei1024.github.io/apgsembly-emulator/ An emulator] that works in a web browser.

== References ==
<references>
<ref name="post199807">{{LinkForumThread
|format = ref
|p = 199807
|title = Re: Smaller Pi Calculator Challenge
|author = branoc
|date = December 14, 2024
|accessdate = June 29, 2025
}}</ref>
<ref name="rename2021">{{cite web
|url=https://github.com/rei1024/apgsembly-emulator/issues/1
|title=alternate identifier for R, T, and SQ units
|author=Dave Greene
|website=GitHub
|date=November 20, 2020
|accessdate = June 29, 2025
}}</ref>
</references>

[[Category:Everything else]]
[[Category:Universal computation]]

APGsembly

2026-04-18T13:57:52Z

Rei: Add #COMPONENTS

The '''general purpose calculator''' ('''GPC''') is a way to implement computational tasks inside Conway's Game of Life. It is [[Turing complete]] and programmed by a special-purpose programming language called '''APGsembly'''. The first computational Life patterns using this technology were constructed by [[Adam P. Goucher]] in 2009 and 2010. The [[Spartan universal computer-constructor]], [[pi calculator]] and [[phi calculator]] patterns, and a related pattern programmed to grow at [[Osqrtlogt|O(sqrt(log(t)))]], had all the same basic general-purpose components that make up the GPC.

Goucher's original compiler/editor was written in DarkBasic, which became difficult to run on modern computers. In 2019 a Golly Python-script compiler was written by [[Dave Greene]] to create a Conway's Life pattern corresponding to APGsembly code, and a visual emulator and debugger was written by [[Michael Simkin]] and Dave Greene. At that time the logic circuitry was adjusted to include a standard set of components, and the resulting "GPC" was shown to be capable of supporting any of the three programs (pi, phi, or Osqrtlogt). In 2024, branoc created a version of the compiler and emulator based on the updated specifications from ''[[Conway's Game of Life: Mathematics and Construction]]'' textbook.<ref name="post199807" />

The base GPC pattern includes just the logic and memory circuitry; an additional subpattern representing an APGsembly program should be attached to a GPC to produce a complete calculator, printer, or other functional pattern. The additional subpattern is basically a finite-state machine. Each line in an APGsembly program corresponds to a state, and there are JUMP instructions for each possible return value (Z or NZ), pointing to the next state that the machine should enter. Each line of code can trigger one or more commands, or "actions", and it's important to make sure that each line includes exactly one action that returns a zero/nonzero value.

== Overview ==

The GPC includes a ticking clock in the form of two synchronized glider guns of period 2^17, 2^18 or higher, depending on the size of the program. These guns emit a glider each time an action has been executed with a return value of either Z or NZ, represented by a glider emitted on one of two possible output [[lane]]s, as a result of the most recent output-producing action. These actions are triggered by an input glider emitted by the calculator program pattern, sent into special computational units on specific lanes to trigger a specific action (ADD, SUB, WRITE, READ, INC, etc.) defined by the APGsembly code.

Thus the GPC has four major physical components:

# Clock.
# Program code.
# Computational unit array.
# Printer and B2D.

== The computational cycle ==

Every 2^N generations, a glider gun initiates an action based on the output from the previous cycle. The gun waits long enough that an output has most likely returned. If no output has in fact appeared (this can happen when retrieving data from a very long data tape, for example) the gun waits for another cycle and checks again, using a [[universal regulator]] mechanism.
* The return signal is always a one-bit output value, either Z or NZ.
* Each cycle is expected to return exactly one such output.

== Program code ==

APGsembly code consists of a list of actions to be performed for each ''state ID'', for each possible return value (Z or NZ). The program consists of lines of code; each state ID corresponds to two lines of code, one for Z and one for NZ.
#The program must start with INITIAL, and will halt if it ever executes HALT_OUT (or HALT) action.
#Two or more actions with Z/NZ responses for a single state are technically illegal, and will likely (though not inevitably) cause chaotic explosions in the calculator pattern.

Each line of code consists of 4 parts, separated by semicolons and optional whitespace:

'''StateID; Z/NZ; NextStateID; Action1, Action2, Action3, etc.'''

#'''StateID.''' Each line's first element is a state ID. This can be thought of as a line number, except that pairs of successive lines usually share the same state ID.
#'''Z/NZ.''' Each line's second element is either Z or NZ. Only the line matching the Z or NZ return value from the previous cycle will actually be executed.
#'''NextStateID.''' Each line's third element defines the state that will be executed on the next clock tick, if that line is executed.
#'''Action.''' Each line's fourth element defines a comma-separated list of actions to be executed. These actions are inputs to the computational units. Some actions will not return anything and only change the state of the computational unit; some will return either Z or NZ depending on the internal state of a particular unit. It is the programmer's task to make sure there is exactly one return value.

'''Example:'''

#COMPONENTS B0
INITIAL; Z; A2; NOP
INITIAL; NZ; A2; NOP
A1; Z; A2; INC B0, NOP
A1; NZ; A2; INC B0, NOP
A2; Z; A1; SET B0, NOP
A2; NZ; A1; SET B0, NOP

This loads the B0 register with an increasing number of '1' bits. Notice that each state ID '''INITIAL''', '''A1''', and '''A2''' appears twice in the program, once for each possible Z return and once for each NZ return.

A syntactic shortcut added in the new compiler is the use of "*" to mean "both Z and NZ", and "ZZ" to mean "only Z is possible" for a given state. The above sample program could be written more compactly as

#COMPONENTS B0
INITIAL; ZZ; A2; NOP
A1; *; A2; INC B0, NOP
A2; *; A1; SET B0, NOP

== Computational units ==

There are currently 6 types of logic units, though it is possible to add more. Each type of logic unit has one or more actions, triggered by glider inputs on specific lanes.

# ''NOP'' - The NOP action sends a Z output directly, and takes no other action.
# ''HALT'' - The HALT_OUT action halts the entire computation and emits a glider. The HALT action halts the entire computation without emitting a glider.
# ''U'' - sliding block register (holds a single integer value, stored in unary)
# ''B'' - binary string register (holds an arbitrary-length string of binary digits)
# ''ADD'' - adder
# ''SUB'' - subtractor
# ''MUL'' - multiplier
# ''B2D'' - a two-dimensional binary register.

The calculator can have an arbitrary number of U, B, ADD, SUB, and MUL units, one B2D unit, and one digit printer or character printer. Future versions of the compiler/emulator will support other components, such as an arbitrary number of fixed-width B2D units.

Before 2021, "U" was written as "R" (short for "register"), and "B2D" was written as "SQ" (short for "square"). The "T" (short for "tape") unit was an older version of the binary register, and differed in some ways from the B unit.<ref name="rename2021" />

=== U: Sliding block register ===

* Sliding block registers in APGsembly code are denoted by keywords starting with the letter U, short for "unary" -- for example, U0, U1, U2, etc.
* A sliding block register has very simple logic. It represents a single number, and all you can do with it is INC (increase by 1) and TDEC (test and decrease by 1).

'''U Actions:'''

* ''INC Ux'' will increase the register by 1. No return signal.
* ''TDEC Ux'' will decrease the register by 1. Returns NZ if the register > 0, otherwise Z.

=== B: Binary string register ===

* Binary string registers in APGsembly code are denoted by keywords starting with B, short for "binary" -- for example, B0, B1, B2, etc.
* A binary string register has a "reading head" that can be moved forward and backward along the tape with INC and TDEC, just like a sliding block register.
* A binary string register can store arbitrarily-large binary strings. A program can only retrieve one bit at a time using READ command. SET might be more clearly named "WRITE 1", but SET is the terms used in existing APGsembly.

'''B Actions'''

* ''INC Bx'' increases the position of reading head. No return signal.
* ''TDEC Bx'' decreases the position of reading head. Returns NZ unless at 0.
* ''READ Bx'' returns the state of the binary string value located at reading head and then sets it equal to 0. Returns Z if the value is 0 and NZ if 1.
* ''SET Bx'' sets the state of the current binary bit to 1 (breaks if the cell is set to 1). No return signal.

=== ADD: adder ===

One should think about the adder as having a 2-bit number. An A input just changes the state of the adder unit, whereas a B input returns the result.

* ''A0'' is not implemented as an input, because there is nothing to change.

'''ADD Actions'''
* ''ADD A1'' increments the number (modulo 4). No return signal.

{| class="wikitable"
! Current !! Next
|-
| 00 || 01
|-
| 01 || 10
|-
| 10 || 11
|-
| 11 || 00
|}

* ''ADD B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || Z
|-
| 01 || 00 || NZ
|-
| 10 || 01 || Z
|-
| 11 || 01 || NZ
|}

* ''ADD B1'' increments and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || NZ
|-
| 01 || 01 || Z
|-
| 10 || 01 || NZ
|-
| 11 || 00 || Z
|}

=== SUB: subtractor ===

The subtractor works same as the adder, but using 2-bit two's complement arithmetic.

'''SUB Actions'''
* ''SUB A1'' increments the number (modulo 4). No return signal.

{| class="wikitable"
! Current !! Next
|-
| 00 || 01
|-
| 01 || 10
|-
| 10 || 11
|-
| 11 || 00
|}

* ''SUB B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || Z
|-
| 01 || 00 || NZ
|-
| 10 || 11 || Z
|-
| 11 || 11 || NZ
|}

* ''SUB B1'' decrements and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 11 || NZ
|-
| 01 || 00 || Z
|-
| 10 || 00 || NZ
|-
| 11 || 11 || Z
|}

=== MUL ===

MUL keeps a number between 0 and 10 in an internal register. MUL 0 divides the number by 2 (i.e., bit shifts it by 1 bit), and MUL 1 adds 10 and ''then'' divides the number by 2. The point of doing this is that performing MUL commands in succession can be used to multiply binary numbers one bit at a time, with the internal memory of the MUL component keeping track of future carry bits. This is used in the digit extraction step of the [[pi calculator|pi]] and [[phi calculator]] programs.

'''MUL Actions'''
* ''MUL 0''
* ''MUL 1''

=== B2D: 2d binary register ===

* B2D is two-dimensional binary register and is unbounded in positive X and Y directions.
* B2D can be used as memory array as well as 2d plotter.
* B2D register commands contain the string "B2D" in APGsembly code -- e.g., INC B2DX, TDEC B2DX, READ B2D, etc.
* The B2D has two arms X and Y. Each arm can be moved with INC and TDEC -- e.g., INC B2DX, TDEC B2DY.
* A program can retrieve a bit located at (X, Y) via the READ B2D command. READ B2D will always set the (X, Y) bit back to 0 (empty space). This means there is no need for a RESET B2D command, so only SET B2D is implemented.

'''B2D Actions'''
* ''INC B2DX'' increases the position of the X arm. No return signal.
* ''INC B2DY'' increases the position of the Y arm. No return signal.
* ''TDEC B2DX'' decreases the position of X arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''TDEC B2DY'' decreases the position of Y arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''READ B2D'' returns the state of the binary value located at (X, Y) and then sets it equal to 0. Returns Z if the value is 0 (empty), otherwise NZ.
* ''SET B2D'' sets the state at (X, Y) to 1 (breaks if the cell is set to 1). No return signal.

=== Digit printer ===

The ''digit printer'' can print "." and digits 0-9. No return signal.

'''Digit printer actions'''
* ''OUTPUT x'', for x = ., 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.

== Further details ==
* For further discussion and examples, or to ask questions, see [https://conwaylife.com/forums/viewtopic.php?f=2&t=4196 this conwaylife.com forum thread].
* [[Conway's Game of Life: Mathematics and Construction]], Chapter 9: Universal Computation
* [https://conwaylife.com/forums/viewtopic.php?p=221972#p221972 A compiler and emulator] written in Lua for use in Golly.
* [https://github.com/dvgrn/b3s23life/tree/main/calculator A compiler and debugger] for use in Golly. This is an old (1.0) version.
* [https://rei1024.github.io/apgsembly-emulator/ An emulator] that works in a web browser.

== References ==
<references>
<ref name="post199807">{{LinkForumThread
|format = ref
|p = 199807
|title = Re: Smaller Pi Calculator Challenge
|author = branoc
|date = December 14, 2024
|accessdate = June 29, 2025
}}</ref>
<ref name="rename2021">{{cite web
|url=https://github.com/rei1024/apgsembly-emulator/issues/1
|title=alternate identifier for R, T, and SQ units
|author=Dave Greene
|website=GitHub
|date=November 20, 2020
|accessdate = June 29, 2025
}}</ref>
</references>

[[Category:Everything else]]
[[Category:Universal computation]]

Wire

2026-04-14T14:56:33Z

Rei: Fix link

{{Glossary}}
A '''wire''' is a repeating pattern that a [[signal]] can travel along without making any permanent change to the pattern.<ref>{{citeCGoLMC|section=Section 4.5.1}}</ref> If instead the pattern is destroyed by the travelling signal (i.e. it [[burn]]s from one end) it is a [[fuse]].<ref>{{citeCGoLMC|section=Section 4.5.2|page=103}}</ref>

The first documented wire was discovered by [[Dean Hickerson]] in March {{year|1997}} while studying some period-3 [[oscillator]]s found by [[Achim Flammenkamp]]. It transmits signals that travel through the wire diagonally at two-thirds of the [[speed of light]]. This was the inspiration for Hickerson's [[drifter]] [[search program]], which led to the discovery of a 5c/9 wire a month later.

Hickerson also used his program to search for a wire signal elbow, hoping to use it to construct a fast signal loop and solve the [[omniperiodicity]] problem; this effort was unsuccessful for [[Life]], with the closest match being a 2c/3 [[signal elbow]] found in July {{year|1997}} that turned a single signal into a reflected double signal.

Signals on wires are harder to manipulate as compared to signals in a vacuum, especially in the form of [[glider]]s, for which there is a rich and growing [[toolkit]].<ref>{{citeCGoLMC|section=Section 4.7}}</ref>

==2c/3 wire==

'''2c/3 wire''' was discovered by Dean Hickerson in {{year|1997}}. It can be found in the ''misc'' section of [[jslife]] under the name ''signals 2c3d''.<ref name="jslife">{{CiteSummersPattern|name=jslife|accessdate=June 6, 2022}}</ref>

{{EmbedViewer
|position = center
|pname = 2c3wire
|caption = Diagonal 2c/3 wire
|viewerconfig = #C [[ AUTOSTART THUMBSIZE 2 HEIGHT 600 WIDTH 600 X 8 Y 4 ZOOM 8 GPS 10 LOOP 128 PAUSE 2 ]]
|style = width:300px;
}}

Each signal is made up of two half-signals that can be separated from each other by an arbitrary number of [[ticks]].

Considerable effort has been spent on finding a way to turn a [[2c/3]] signal 90 or 180 degrees, since this would have been one way to prove that Life was omniperiodic. There is a known 2c/3 [[converter]] shown under [[signal elbow]], which converts a standard 2c/3 signal into a double-length signal. This is usable in some situations, but unfortunately it fails when its input is a double-length signal, so it cannot be used to complete two or more consecutive turns. It could only produce zigzag wires in any case rather than completing a loop, since the wire coming out of the elbow is a mirror image of the input wire.

In February {{year|2004}}, [[Noam Elkies]] discovered a [[glider synthesis]] of a reaction that can repeatably insert a signal into the upper end of a 2c/3 wire. See [[stable pseudo-Heisenburp]] for details. In 2011, a [[p11 double-length signal injector]] was found that allows signals to be injected periodically.

On September 11, {{year|2017}}, [[Martin Grant]] reduced the cost of the synchronized input to five gliders, or three gliders plus a [[Herschel]].<ref name="post50807" /> In {{year|2024}}, a double [[beehive push catalyst]] variant was found that uses only 4 gliders to activate a 2c/3 wire, with a recovery time of 56,<ref name="post179988" /> or just two [[pi heptomino]]s following each other on the same track. (See [[Tutorials/Catalyses#Beehive push catalyst replacements]]). Compact engineered solutions requiring just one input Herschel have been completed with [[recovery time]] 151 ticks<ref name="post180139" /> and 171 ticks<ref name="post179942" /> in March 2024, and with recovery time 132 ticks in April 2024.<ref name="post181846" /> The current fastest 2c/3 signal injector has a repeat time of 126.<ref name="post181888" />

Devices that extract a signal from a 2c/3 wire have also been built. Before 2024, the lowest repeat time of a standard 2c/3 signal receiver was 964 ticks,<ref name="post135690" /> and that of a double-length signal was 970 ticks,<ref name="post137526" /> both of which were achieved by [[Goldtiger997]] in {{year|2021}} by using complex [[staged recovery]] systems. On March 31, {{year|2024}}, [[Entity Valkyrie]] constructed a new [[pseudo-Heisenburp]] device with a repeat time of 742 ticks at both the input end (the highway robber) and the output end (the 2c/3 to glider converter).<ref name="post181579" /> On July 4, {{year|2024}}, Entity Valkyrie improved the repeat time at the receiver end to 708 ticks using an alternate [[bait]] proposed by [[Simon Ekström]].<ref name="post189015" /> On August 1, {{year|2025}}, [[TigerCub414]] built a receiver with a repeat time of 629 ticks;<ref name="post215428"/> on August 3, [[Entity Valkyrie]] improved the repeat time to 570 ticks using the same bait object.<ref name="post215500"/> Two days later, TigerCub414 improved the repeat time even further, to 504 ticks.<ref name="post215632"/>

==5c/9 wire==

'''5c/9 wire''' was discovered by Dean Hickerson in 1997.

{{EmbedViewer
|position = center
|pname = 5c9wire
|caption = Diagonal 5c/9 wire
|viewerconfig = #C [[ AUTOSTART THUMBSIZE 2 HEIGHT 600 WIDTH 600 X 8 Y 4 ZOOM 6 GPS 10 LOOP 180 PAUSE 2 ]]
|style = width:300px;
}}

Oscillators have been found that inject signals of various periods including 9, 10, 11, and [[p47 lumps of muck hassler|47]] into a 5c/9 wire.<ref>{{cite web|url=https://conwaylife.com/ref/DRH/sig.inj.html|title=Dean Hickerson's signal-injector collection}}</ref>

It is possible to convert a 2c/3 wire signal into a 5c/9 signal; the viewer above shows the aforementioned five-glider input reaction for a 2c/3 signal and its subsequent conversion to 5c/9 signal. Another elementary 5c/9 signal injector involves a [[lumps of muck]] reaction,<ref name="post54568" /> which can be made from the synchronized [[2-glider collision]] at a repeat time of 62 ticks<ref name="post54617" />, a single Herschel with a much higher repeat time<ref name="post101243" />, or a fixed-period lumps of muck hassler that uses a specific catalyst (such as the p47).

No elementary converter has yet been found for 5c/9 to 2c/3 – or any other viable signal type, for that matter. However, in November 2025, [[James Pascua]] completed a multistage composite converter for 5c/9 signals, which allowed for the completion of the first closed loop containing a segment of 5c/9 wire.<ref name="post221926" />

==c/2 wire==

'''c/2 wire''' was discovered by [[Hartmut Holzwart]] in {{year|2003}}.

{{EmbedViewer
|position = center
|pname = c2wire
|caption = Diagonal c/2 wire
|viewerconfig = #C [[ AUTOSTART THUMBSIZE 2 HEIGHT 440 ZOOM 8 GPS 10 LOOP 40 PAUSE 2 ]]
|style = width:300px;
}}

Both halves of the signal (the non-uniform portion of the pattern) are needed, since the wire is offset by one cell between the two half signals.

It is technically possible to use [https://conwaylife.com/forums/viewtopic.php?f=2&t=3507 Extrementhusiast's construction and detection mechanisms from 2018] to complete a c/2 diagonal [[telegraph]] pattern that can send one bit of information every few thousand ticks. Or a somewhat higher transmission rate can be arranged with a mechanism similar to the one used in Louis-François Handfield's [[high-bandwidth telegraph]]. No complete c/2 diagonal telegraph has been built to date.

==Lightspeed wire==

The [[zebra stripes]] [[agar]] can be used to form a wire. Below are several signals which can travel through such a wire at [[lightspeed]] (one cell to the right per generation).

{{EmbedViewer
|position = center
|pname = zebrawiresignals
|caption = Several lightspeed signals travel through a zebra stripes wire
|viewerconfig = #C [[ AUTOSTART THUMBSIZE 2 HEIGHT 360 WIDTH 800 GPS 10 LOOP 138 ZOOM 6 ]]
|style = width:300px;
}}

Another type of lightspeed wire is "beehive wire": an orthogonal chain of beehives can be burned non-destructively at lightspeed, as described in the [[telegraph]] article.

==References==
<references>
<ref name="post50807">{{LinkForumThread
|format = ref
|title = Re: Stable signal converters
|p = 50807
|author = Martin Grant
|date = September 11, 2017
}}</ref>
<ref name="post135690">{{LinkForumThread
|format = ref
|title = Re: Faster 2c/3 Wires
|p = 135690
|author = Goldtiger997
|date = September 12, 2021
}}</ref>
<ref name="post137526">{{LinkForumThread
|format = ref
|title = Re: Faster 2c/3 Wires
|p = 137526
|author = Goldtiger997
|date = November 11, 2021
}}</ref>
<ref name="post54568">{{LinkForumThread
|format = ref
|title = Re: Interacting with LoM
|p = 54568
|author = Adam P. Goucher
|date = January 2, 2018
}}</ref>
<ref name="post54617">{{LinkForumThread
|format = ref
|title = Re: Interacting with LoM
|p = 54617
|author = Chris Cain
|date = January 3, 2018
}}</ref>
<ref name="post101243">{{LinkForumThread
|format = ref
|title = Re: The Hunting of the Elementary Conduits
|p = 101243
|author = Sphenocorona
|date = July 28, 2020
}}</ref>
<ref name="post179942">{{LinkForumThread
|format = ref
|title = Re: Faster 2c/3 Wires
|p = 179942
|author = Entity Valkyrie
|date = March 8, 2024
}}</ref>
<ref name="post179988">{{LinkForumThread
|format = ref
|title = Re: Faster 2c/3 Wires
|p = 179988
|author = EvinZL
|date = March 10, 2024
}}</ref>
<ref name="post180139">{{LinkForumThread
|format = ref
|title = Re: Faster 2c/3 Wires
|p = 180139
|author = Dave Greene
|date = March 12, 2024
}}</ref>
<ref name="post181579">{{LinkForumThread
|format = ref
|title = Re: Faster 2c/3 Wires
|p = 181579
|author = Entity Valkyrie
|date = March 31, 2024
}}</ref>
<ref name="post181846">{{LinkForumThread
|format = ref
|title = Re: Faster 2c/3 Wires
|p = 181846
|author = C. R. Hilton
|date = April 4, 2024
}}</ref>
<ref name="post181888">{{LinkForumThread
|format = ref
|title = Re: Faster 2c/3 Wires
|p = 181888
|author = Adam P. Goucher
|date = April 5, 2024
}}</ref>

<ref name="post189015">{{LinkForumThread
|format = ref
|title = Re: Faster 2c/3 Wires
|p = 189015
|author = Entity Valkyrie
|date = July 4, 2024
}}</ref>
<ref name="post215428">{{LinkForumThread
|format = ref
|title = Re: Faster 2c/3 Wires
|p = 215428
|author = TigerCub414
|date = August 1, 2025
}}</ref>
<ref name="post215500">{{LinkForumThread
|format = ref
|title = Re: Faster 2c/3 Wires
|p = 215500
|author = Entity Valkyrie
|date = August 3, 2025
}}</ref>
<ref name="post215632">{{LinkForumThread
|format = ref
|title = Re: Faster 2c/3 Wires
|p = 215632
|author = TigerCub414
|date = August 5, 2025
}}</ref>
<ref name="post221926">{{LinkForumThread
|format = ref
|title = Re: Stable signal converters
|p = 221926
|author = James Pascua
|date = November 27, 2025
}}</ref>
</references>

==External links==
* {{LinkGoLNews|2005/02/stable_2c3_signal_receiver.html|archivedate=20100523082242|title=Stable 2c/3 signal receiver|date=February 7, 2005|author=Dave Greene}}
* {{LinkLexicon|lex_w.htm#wire|name=Wire}}
* {{LinkLexicon|lex_1.htm#a-2c3wire|name=2c/3 wire}}
* {{LinkLexicon|lex_1.htm#a-5c9wire|name=5c/9 wire}}
* {{LinkLexicon|lex_l.htm#lightspeedwire|name=Lightspeed wire}}

__NOTOC__

WinLifeSearch

2026-02-20T15:00:58Z

Rei:

{{Software
|name = WinLifeSearch
|image = true
|url = http://entropymine.com/jason/life/software/
|purpose = Search for [[oscillator]]s and [[spaceship]]s
|createdby = [[Jason Summers]]
|platform = Windows
}}
'''WinLifeSearch''' (abbreviated as '''WLS''') is a graphical Windows port of [[David Bell]]'s [[lifesrc]] search program for finding new [[oscillator]]s and [[spaceship]]s, written by [[Jason Summers]].

==Known issues==
WLS has a rollover problem at around 2 billion calculations, where it rolls over to about -2 billion calculations.

==See also==
*[[JavaLifeSearch]]

==External links==
* [http://entropymine.com/jason/life/software/ WinLifeSearch homepage]
* [https://github.com/jsummers/winlifesearch WinLifeSearch on GitHub]
* {{LinkLexicon|lex_w.htm#winlifesearch}}

[[Category:Search software]]

0E0P metacell

2026-02-20T14:56:22Z

Rei: Add further reading

{{UnitCell
|name = 0E0P metacell
|pname = 0e0pmetacell
|c = ~ 18650000
|bx = 261841
|by = 261841
|sx = 262144
|sy = 262144
|p = 68719476736
|discoverer = Adam P. Goucher
|discoveryear = 2018
|nofile = true
}}
The '''0E0P metacell''' is a [[unit cell]] constructed by [[Adam P. Goucher]] between 2014 and 2018.<ref>{{cite web|url=https://cp4space.wordpress.com/2018/11/12/fully-self-directed-replication/ |title=Fully Self-Directed Replication |publisher=Adam P. Goucher |date=November 12, 2018|accessdate=January 8, 2019}}</ref> Like Goucher's previous [[p1 megacell]], it is capable of simulating any [[rule]] using the [[Moore neighborhood|standard eight cell neighborhood]], including [[non-totalistic rule]]s.

The new feature of the 0E0P metacell, and the one that explains its record-breaking large size, is the fact that a group of these metacells can be placed in an empty Life universe with no background grid of OFF metacells, and the entire universe then simulates the rule for which the 0E0P metacells are programmed, at a larger scale by a factor of {{eq|262144|2{{sup|18}}}}. The acronym "0E0P" is short for "[State] Zero Encoded by Zero Population", so the OFF state is simply a metacell-sized region of empty space.

When one of these metacells turns off, it self-destructs completely, and when a metacell birth occurs, it must be constructed from the ground up by one of its neighbors. This allows 0E0P metacell patterns, when viewed from very far away (e.g., at a size where an entire metacell takes up a single pixel in the display), to be indistinguishable from normal patterns that use the same rule -- except that the metacell patterns will run 2{{sup|36}} times more slowly, and if they're run at a step size lower than 2{{sup|36}}, intermediate states may be visible that will depart from a strict pixel-for-pixel match.

The {{POTY|year=2018|rank=2|behind=[[Sir Robin]]}}

==Details==
Each individual metacell behaves as an 8-state, 4-neighborhood BCC-automaton; the metacell receives a glider-based signal (a positive integer between 1 and 7, inclusive) from each of its (up to four) neighbours, and a 0 from any empty spaces if there are fewer than four neighbours. It then computes the quantity {{nowrap|8{{sup|3}} a + 8{{sup|2}} b + 8{{sup|1}} c + d}}, where {{nowrap|(a, b, c, d)}} are the four input signals, and indexes into a 4096-element lookup table to retrieve a value between 0 and 7 (the new ‘state’ of the metacell). If 0, it immediately self-destructs without constructing any children; if nonzero, it constructs a daughter machine in each vacant space. Finally, it broadcasts the new state as a signal to all four neighbours, before self-destructing. In doing so, the metacell behaves as a single cell in any 8-state 4-neighbor cellular automaton; as every 2-state 9-neighbour cellular automaton can be emulated at half the speed as an 8-state 4-neighbour cellular automaton, this allows the 0E0P metacell to emulate rules other than Life, which also allows it to act as a parity-rule [[replicator]], a [[reflectorless rotating oscillator]] (with some limits), and a [[SMOS]] if programmed correctly.

In a healthy 0E0P metacell pattern, metacells could be thought of as living on a diagonally-oriented checkerboard. They're allowed to be present on the dark squares of the checkerboard '''only''' during even 2{{sup|35}}-tick half-cycles, and on the light squares of the checkerboard only during odd half-cycles. At the beginning of each even half-cycle, or in other words at the beginning of each full metatick, the presence or absence of an 0E0P metacell on a dark square corresponds with the presence or absence of an ON cell in an equivalent Life grid (assuming the metacell is programmed to emulate B3/S23). At other times during the 0E0P's replication cycle, the correspondence with cells on a Life grid won't be as clean, but every 2{{sup|36}} ticks the 0E0P metapattern will come back into perfect alignment.

Every period-2{{sup|36}} cycle of an 0E0P metacell consists of two period-2{{sup|35}} half-cycles. In each half-cycle, all metacells make sure that there are child metacells all around them, on the other checkerboard square color -- either by building them, or by attempting to build them and having the construction recipe cleanly eaten by an eater that's part of an already existing child in that location.

Notice that with the 45-degree checkerboard orientation, each grid location in the emulated Life pattern is only half filled by a 0E0P metacell (if one is present). In other words, the metacells are diamond-shaped, not square; their sides don't line up with the emulated Life grid.

Switching checkerboard colors and expanding to four surrounding metacells twice (for two half-cycles) effectively ensures that all eight metacells surrounding any given ON metacell on the same checkerboard square color are occupied by child metacells. These are all the neighbor locations for that particular metacell. No effect can travel faster than lightspeed in the range-1 Moore-neighborhood rules that the 0E0P metacell can emulate, so at the end of two half-cycles, metacells are present in every location where a metacell could possibly be needed to turn ON in the next metatick.

There's no direct communication between an 0E0P metacell and its nearest possible living neighbor metacells to the north, south, east, and west -- i.e., the nearest same-color squares on the 45-degree-angled checkerboard -- let alone between it and the other possibly-living neighbor cells, two checkerboard squares away diagonally. However, by the end of each full cycle, communication between parent and child metacells during each half-cycle has effectively transmitted neighbor state information from one dark-square metacell to all its dark-square neighbors. This means that at the end of each half-cycle, every "potentially alive" 0E0P metacell has all the information it needs to decide whether it should transition to a "fully alive" state and start building child metacells, or if it should immediately self-destruct instead.

==LifeViewer demo==
To demonstrate the full 0E0P metacell cycle and the early self-destruct option, the [[LifeViewer]] demo below shows how a glider made of metacells proceeds through a full 2{{sup|36}} period (or "metatick"). Note that the gap between metacells where the equivalent cells would be diagonally adjacent will not be visible at the proper zoom level.
{{LV:Viewer|x = 233, y = 233, rule = none
206.I$205.3I$204.5I$203.7I$202.3IEIE3I$201.3IEIEIE3I$200.5IEIEIE3I$
201.5IEIE3I$202.3IEIE3I$203.3IE3I$204.5I$205.3I$206.I8$186.I39.I$185.
3I37.3I$184.5I35.5I$183.7I33.7I$182.3IDID3I31.9I$181.3IDIDID3I29.6IE
4I$180.5IDIDID3I27.8IE4I$181.5IDID3I29.4IEIE4I$182.3IDID3I31.6IE2I$
183.3ID3I33.7I$184.5I35.5I$185.3I37.3I$186.I39.I8$166.I39.I$165.3I37.
3I$164.5I35.5I$163.7I33.2IHIH2I$162.3ICIC3I31.2IHIHIH2I$161.3ICICIC3I
29.2IHIHIDIH2I$160.5ICICIC3I27.4IHIHIDIH2I$161.5ICIC3I29.4IDIDIH2I$
162.3ICIC3I31.2IHIHID2I$163.3IC3I33.2IHIH2I$164.5I35.2IH2I$165.3I37.
3I$166.I39.I8$146.I39.I$145.3I37.3I$144.5I35.5I$143.7I33.2ICIC2I$142.
3IBIB3I31.2ICICIC2I$141.3IBHBHB3I29.2ICICICIC2I$140.5IBIBHB3I27.4ICIC
ICIC2I$141.5IBHB3I29.4ICICIC2I$142.3IBHB3I31.2ICICIC2I$143.3IB3I33.2I
CIC2I$144.5I35.2IC2I$145.3I37.3I$146.I39.I8$126.I39.I$125.3I37.3I$
124.5I35.5I$123.7I33.2IBIB2I$122.3IAIA3I31.2IBHBHB2I$121.3IAGAGA3I29.
2IBHBHBHB2I$120.5IAIAGA3I27.4IBHBHBHB2I$121.5IAGA3I29.4IBHBHB2I$122.
3IAGA3I31.2IBHBHB2I$123.3IA3I33.2IBHB2I$124.5I35.2IB2I$125.3I37.3I$
126.I39.I8$106.I39.I$105.3I37.3I$104.5I35.5I$103.7I33.2IAIA2I$102.3IA
IA3I31.2IAGAGA2I$101.3IAFAFA3I29.2IAGAGAGA2I$100.5IAIAFA3I27.4IAGAGAG
A2I$101.5IAFA3I29.4IAGAGA2I$102.3IAFA3I31.2IAGAGA2I$103.3IA3I33.2IAGA
2I$104.5I35.2IA2I$105.3I37.3I$106.I39.I8$86.I39.I$85.3I37.3I$84.5I35.
5I$83.7I33.2IAIA2I$82.3IAIA3I31.2IAFAFA2I$81.3IAFAFA3I29.2IAFAFAFA2I$
80.7IAFA3I27.4IAFAFAFA2I$81.5IAFA3I29.4IAFAFA2I$82.3IAFA3I31.2IAFAFA
2I$83.7I33.2IAFA2I$84.5I35.2IA2I$85.3I37.3I$86.I39.I8$66.I39.I$65.3I
37.3I$64.5I35.5I$63.7I33.2IAIA2I$62.3IAIA3I31.2IAFAFA2I$61.4IFAFA3I
29.2IAFAFAFA2I$60.7IAFA3I27.4IAFAFAFA2I$61.5IAFA3I29.4IAFAFA2I$62.4IF
A3I31.2IAFAFA2I$63.7I33.2IAFA2I$64.5I35.5I$65.3I37.3I$66.I39.I8$46.I
39.I$45.3I37.3I$44.5I35.5I$43.7I33.2IAIA2I$42.9I31.2IAFAFA2I$41.4IFAF
A3I29.3IFAFAFA2I$40.8IFA3I27.5IFAFAFA2I$41.6IFA3I29.4IAFAFA2I$42.4IFA
3I31.3IFAFA2I$43.7I33.3IFA2I$44.5I35.5I$45.3I37.3I$46.I39.I8$26.I39.I
$25.3I37.3I$24.5I35.5I$23.7I33.7I$22.9I31.3IFAFA2I$21.4IFIF4I29.3IFAF
AFA2I$20.8IF4I27.5IFAFAFA2I$21.6IF4I29.5IFAFA2I$22.4IF4I31.3IFAFA2I$
23.7I33.3IFA2I$24.5I35.5I$25.3I37.3I$26.I39.I8$6.I39.I$5.3I37.3I$4.5I
35.5I$3.7I33.7I$2.9I31.3IFIF3I$.4IEIE4I29.3IFIFIF3I$8IE4I27.5IFIFIF3I
$.6IE4I29.5IFIF3I$2.4IE4I31.3IFIF3I$3.7I33.3IF3I$4.5I35.5I$5.3I37.3I$
6.I39.I8$26.I$25.3I$24.5I$23.7I$22.3IEIE3I$21.3IEIEIE3I$20.5IEIEIE3I$
21.5IEIE3I$22.3IEIE3I$23.3IE3I$24.5I$25.3I$26.I!
#C [[ COLOR 1 Yellow COLOR 2 Orange COLOR 3 Pink COLOR 4 Gray COLOR 5 Purple ]]
#C [[ COLOR 6 Blue COLOR 7 Cyan COLOR 8 Red COLOR 9 Green ]]
#C [[ LABELSIZE 12 LABELALPHA 1 LABELANGLE 315 COLOR LABEL White ]]
#C [[ GRID ANGLE 45 HEIGHT 600 THEME MCell GRIDMAJOR 0 ]]
#C [[ POI X -108 Y 92 Z 32 POITRANS 0 ]] Point of interest #1
#C [[ LABEL 11 211 16 "Here's where it all starts\n-- five metacells forming a glider, in Stage E\n(shown in purple)" ]]
#C [[ POI X -88 Y 72 Z 32 POITRANS 0 ]] POI #2
#C [[ LABEL 31 191 16 "Metacells move to Stage F (blue).\n-- ready to start constructing children, SE first" ]]
#C [[ POI X -68 Y 52 Z 32 POITRANS 0 ]] POI #3
#C [[ LABEL 51 171 16 "Metacells remain in Stage F (blue).\nChildren constructed SE of each metacell\n(yellow cells, Stage A)" ]]
#C [[ POI X -48 Y 32 Z 32 POITRANS 0 ]] POI #4
#C [[ LABEL 71 151 16 "Metacells remain in Stage F (blue).\nChildren constructed NE of each metacell\n(yellow cells, Stage A)" ]]
#C [[ POI X -28 Y 12 Z 32 POITRANS 0 ]] POI #5
#C [[ LABEL 91 131 16 "Metacells remain in Stage F (blue).\nChildren constructed NW of each metacell\n(yellow cells, Stage A)" ]]
#C [[ POI X -8 Y -8 Z 32 POITRANS 0 ]] POI #6
#C [[ LABEL 111 111 16 "Metacells remain in Stage F (blue).\nChildren constructed SW of each metacell\n(yellow cells, Stage A)" ]]
#C [[ POI X 12 Y -28 Z 32 POITRANS 0 ]] POI #7
#C [[ LABEL 130 90 16 "Original metacells move to Stage G (cyan).\nParent metacells send their own states\nto each immediate neighbor. All receiving neighbors\nare recently constructed child metacells." ]]
#C [[ POI X 32 Y -48 Z 32 POITRANS 0 ]] POI #8
#C [[ LABEL 150 70 16 "Metacells move to Stage H (red)\nThe cycle is complete. The original metacells self-destruct.\nState signals from the original metacells are collected and\nstored in registers in each neighboring child cell,\nwhich have all now moved to Stage B (orange)" ]]
#C [[ POI X 52 Y -68 Z 32 POITRANS 0 ]] POI #9
#C [[ LABEL 170 50 16 "Original metacells are gone now\n(green is the background state, completely empty).\nThe four child metacells move to Stage C (pink)\nIn each metacell, the collected state values from each\nneighbor are used to calculate the future state of the cell." ]]
#C [[ POI X 72 Y -88 Z 32 POITRANS 0 ]] POI #10
#C [[ LABEL 190 30 16 "The child metacells move to Stage D (gray)\nIf a child metacell's new calculated state is 0, it\nself-destructs. Here all 13 child metacells survive.\nThis is what always happens in the first\nhalf-cycle, when a Moore-neighborhood rule\nis being emulated." ]]
#C [[ POI X 92 Y -108 Z 32 POITRANS 0 ]] POI #11
#C [[ LABEL 211 11 16 "The thirteen child metacells move to Stage E (purple)\nThe construction/signal/collect/decide cycle begins again.\nThis cycle happens twice in each 2^36 0E0P metacell cycle." ]]
#C [[ POI X -88 Y 112 Z 32 POITRANS 0 ]] POI #12
#C [[ LABEL 30 230 16 "The cycle restarts.\nNow there are thirteen metacells, all in Stage E\n(shown in purple)" ]]
#C [[ POI X -68 Y 92 Z 32 POITRANS 0 ]] POI #13
#C [[ LABEL 50 210 16 "The thirteen metacells move to Stage F (blue)\n-- ready to start constructing children, SE first" ]]
#C [[ POI X -48 Y 72 Z 32 POITRANS 0 ]] POI #14
#C [[ LABEL 70 190 16 "The thirteen metacells remain in Stage F (blue).\nThirteen children are constructed in the SE\n(yellow metacells, Stage A)" ]]
#C [[ POI X -28 Y 52 Z 32 POITRANS 0 ]] POI #15
#C [[ LABEL 90 170 16 "The thirteen metacells remain in Stage F (blue).\nFour more children are constructed in the NE\n(yellow metacells, Stage A)" ]]
#C [[ POI X -8 Y 32 Z 32 POITRANS 0 ]] POI #16
#C [[ LABEL 110 150 16 "The thirteen metacells remain in Stage F (blue).\nFour more children are constructed in the NW\n(yellow metacells, Stage A)" ]]
#C [[ POI X 12 Y 12 Z 32 POITRANS 0 ]] POI #17
#C [[ LABEL 130 130 16 "The thirteen metacells remain in Stage F (blue).\nOne more child is constructed in the SW\n(yellow metacell, Stage A)" ]]
#C [[ POI X 32 Y -8 Z 32 POITRANS 0 ]] POI #18
#C [[ LABEL 150 110 16 "Metacells move to Stage G (cyan).\nEach parent metacell sends its own state to each neighbor." ]]
#C [[ POI X 52 Y -28 Z 32 POITRANS 0 ]] POI #19
#C [[ LABEL 170 90 16 "Parent metacells move to Stage H (red).\nChild metacells move to stage B (orange).\nThe parent metacells self-destruct, as always.\nState signals from the parent cell are stored in registers\nin the new child cells." ]]
#C [[ POI X 72 Y -48 Z 32 POITRANS 0 ]] POI #20
#C [[ LABEL 190 70 16 "The thirteen parent metacells are gone now -- back to the\ngreen background state, completely empty.\nThe twenty-two child metacells move to Stage C (pink)\nIn each metacell, the collected neighbor states\nare used to calculate the future state of the metacell." ]]
#C [[ POI X 92 Y -68 Z 32 POITRANS 0 ]] POI #21
#C [[ LABEL 210 50 16 "The twenty-two child metacells move to Stage D (gray)\nIf a child metacell's calculated state is 0, it self-destructs.\nIn this case, where a B3/S23 glider is being emulated,\nonly five of the twenty-two child metacells survive." ]]
#C [[ POI X 112 Y -88 Z 32 POITRANS 0 ]] POI #22
#C [[ LABEL 230 30 16 "The five remaining metacells move to Stage E (purple).\nEmpty background locations are shown in green." ]]
#C [[ POI INITIAL X 132 Y -108 Z 32 POITRANS 0 ]] POI #23 (initial position, because of INITIAL keyword)
#C [[ LABEL 245 6 16 "Press 'J' or 'Shift+J' keys, or < and > buttons,\nto move forward or backward through 0E0P stages." WIDTH 640 ]]}}

==Complexity==
The metacell's circuitry is sufficiently complex that a single Conway's Life meta-[[glider]] requires a compressed pattern file several megabytes in size.<ref name="post65737" /> It can be run in Golly at small step sizes with no difficulty, but simulating an entire replication cycle (half a metatick) is very difficult. On current computers it might take about half a CPU-year using Golly's standard HashLife algorithm.

An order of magnitude improvement over [[HashLife]] is available via Goucher's special-purpose [[StreamLife]] algorithm. However, even using StreamLife it might take several months to simulate the eight replication cycles (four full metaticks) needed to return a metaglider to its original phase. The original experimental verification of a single metatick (12:05 to 12:35 in Cabaret's video below), using rule where a single ON cell is a still life, took about a month.

==Videos==

{{#ev:youtube|CfRSVPhzN5M|640|left|Thomas Cabaret's video explaining various self-replicating machines in cellular automata, including a comprehensive explanation (from 7:35 to 13:05) of the operation of the 0E0P metacell}}



==See also==
*[[OTCA metapixel]]

== References ==
<references>
<ref name="post65737">{{LinkForumThread
|format = ref
|author = Dave Greene
|title = Re: Thread for basic questions
|date = November 8, 2018
|accessdate = January 9, 2019
|p = 65737
}}</ref>
</references>

==Further reading==
* [[Conway's Game of Life: Mathematics and Construction]], Chapter 12: The 0E0P Metacell

[[Category:Patterns with between 10,000,000 and 99,999,999 cells]]

APGsembly

2026-02-20T14:48:56Z

Rei: Add category

The '''general purpose calculator''' ('''GPC''') is a way to implement computational tasks inside Conway's Game of Life. It is [[Turing complete]] and programmed by a special-purpose programming language called '''APGsembly'''. The first computational Life patterns using this technology were constructed by [[Adam P. Goucher]] in 2009 and 2010. The [[Spartan universal computer-constructor]], [[pi calculator]] and [[phi calculator]] patterns, and a related pattern programmed to grow at [[Osqrtlogt|O(sqrt(log(t)))]], had all the same basic general-purpose components that make up the GPC.

Goucher's original compiler/editor was written in DarkBasic, which became difficult to run on modern computers. In 2019 a Golly Python-script compiler was written by [[Dave Greene]] to create a Conway's Life pattern corresponding to APGsembly code, and a visual emulator and debugger was written by [[Michael Simkin]] and Dave Greene. At that time the logic circuitry was adjusted to include a standard set of components, and the resulting "GPC" was shown to be capable of supporting any of the three programs (pi, phi, or Osqrtlogt). In 2024, branoc created a version of the compiler and emulator based on the updated specifications from ''[[Conway's Game of Life: Mathematics and Construction]]'' textbook.<ref name="post199807" />

The base GPC pattern includes just the logic and memory circuitry; an additional subpattern representing an APGsembly program should be attached to a GPC to produce a complete calculator, printer, or other functional pattern. The additional subpattern is basically a finite-state machine. Each line in an APGsembly program corresponds to a state, and there are JUMP instructions for each possible return value (Z or NZ), pointing to the next state that the machine should enter. Each line of code can trigger one or more commands, or "actions", and it's important to make sure that each line includes exactly one action that returns a zero/nonzero value.

== Overview ==

The GPC includes a ticking clock in the form of two synchronized glider guns of period 2^17, 2^18 or higher, depending on the size of the program. These guns emit a glider each time an action has been executed with a return value of either Z or NZ, represented by a glider emitted on one of two possible output [[lane]]s, as a result of the most recent output-producing action. These actions are triggered by an input glider emitted by the calculator program pattern, sent into special computational units on specific lanes to trigger a specific action (ADD, SUB, WRITE, READ, INC, etc.) defined by the APGsembly code.

Thus the GPC has four major physical components:

# Clock.
# Program code.
# Computational unit array.
# Printer and B2D.

== The computational cycle ==

Every 2^N generations, a glider gun initiates an action based on the output from the previous cycle. The gun waits long enough that an output has most likely returned. If no output has in fact appeared (this can happen when retrieving data from a very long data tape, for example) the gun waits for another cycle and checks again, using a [[universal regulator]] mechanism.
* The return signal is always a one-bit output value, either Z or NZ.
* Each cycle is expected to return exactly one such output.

== Program code ==

APGsembly code consists of a list of actions to be performed for each ''state ID'', for each possible return value (Z or NZ). The program consists of lines of code; each state ID corresponds to two lines of code, one for Z and one for NZ.
#The program must start with INITIAL, and will halt if it ever executes HALT_OUT (or HALT) action.
#Two or more actions with Z/NZ responses for a single state are technically illegal, and will likely (though not inevitably) cause chaotic explosions in the calculator pattern.

Each line of code consists of 4 parts, separated by semicolons and optional whitespace:

'''StateID; Z/NZ; NextStateID; Action1, Action2, Action3, etc.'''

#'''StateID.''' Each line's first element is a state ID. This can be thought of as a line number, except that pairs of successive lines usually share the same state ID.
#'''Z/NZ.''' Each line's second element is either Z or NZ. Only the line matching the Z or NZ return value from the previous cycle will actually be executed.
#'''NextStateID.''' Each line's third element defines the state that will be executed on the next clock tick, if that line is executed.
#'''Action.''' Each line's fourth element defines a comma-separated list of actions to be executed. These actions are inputs to the computational units. Some actions will not return anything and only change the state of the computational unit; some will return either Z or NZ depending on the internal state of a particular unit. It is the programmer's task to make sure there is exactly one return value.

'''Example:'''

INITIAL; Z; A2; NOP
INITIAL; NZ; A2; NOP
A1; Z; A2; INC B0, NOP
A1; NZ; A2; INC B0, NOP
A2; Z; A1; SET B0, NOP
A2; NZ; A1; SET B0, NOP

This loads the B0 register with an increasing number of '1' bits. Notice that each state ID '''INITIAL''', '''A1''', and '''A2''' appears twice in the program, once for each possible Z return and once for each NZ return.

A syntactic shortcut added in the new compiler is the use of "*" to mean "both Z and NZ", and "ZZ" to mean "only Z is possible" for a given state. The above sample program could be written more compactly as

INITIAL; ZZ; A2; NOP
A1; *; A2; INC B0, NOP
A2; *; A1; SET B0, NOP

== Computational units ==

There are currently 6 types of logic units, though it is possible to add more. Each type of logic unit has one or more actions, triggered by glider inputs on specific lanes.

# ''NOP'' - The NOP action sends a Z output directly, and takes no other action.
# ''HALT'' - The HALT_OUT action halts the entire computation and emits a glider. The HALT action halts the entire computation without emitting a glider.
# ''U'' - sliding block register (holds a single integer value, stored in unary)
# ''B'' - binary string register (holds an arbitrary-length string of binary digits)
# ''ADD'' - adder
# ''SUB'' - subtractor
# ''MUL'' - multiplier
# ''B2D'' - a two-dimensional binary register.

The calculator can have an arbitrary number of U, B, ADD, SUB, and MUL units, one B2D unit, and one digit printer or character printer. Future versions of the compiler/emulator will support other components, such as an arbitrary number of fixed-width B2D units.

Before 2021, "U" was written as "R" (short for "register"), and "B2D" was written as "SQ" (short for "square"). The "T" (short for "tape") unit was an older version of the binary register, and differed in some ways from the B unit.<ref name="rename2021" />

=== U: Sliding block register ===

* Sliding block registers in APGsembly code are denoted by keywords starting with the letter U, short for "unary" -- for example, U0, U1, U2, etc.
* A sliding block register has very simple logic. It represents a single number, and all you can do with it is INC (increase by 1) and TDEC (test and decrease by 1).

'''U Actions:'''

* ''INC Ux'' will increase the register by 1. No return signal.
* ''TDEC Ux'' will decrease the register by 1. Returns NZ if the register > 0, otherwise Z.

=== B: Binary string register ===

* Binary string registers in APGsembly code are denoted by keywords starting with B, short for "binary" -- for example, B0, B1, B2, etc.
* A binary string register has a "reading head" that can be moved forward and backward along the tape with INC and TDEC, just like a sliding block register.
* A binary string register can store arbitrarily-large binary strings. A program can only retrieve one bit at a time using READ command. SET might be more clearly named "WRITE 1", but SET is the terms used in existing APGsembly.

'''B Actions'''

* ''INC Bx'' increases the position of reading head. No return signal.
* ''TDEC Bx'' decreases the position of reading head. Returns NZ unless at 0.
* ''READ Bx'' returns the state of the binary string value located at reading head and then sets it equal to 0. Returns Z if the value is 0 and NZ if 1.
* ''SET Bx'' sets the state of the current binary bit to 1 (breaks if the cell is set to 1). No return signal.

=== ADD: adder ===

One should think about the adder as having a 2-bit number. An A input just changes the state of the adder unit, whereas a B input returns the result.

* ''A0'' is not implemented as an input, because there is nothing to change.

'''ADD Actions'''
* ''ADD A1'' increments the number (modulo 4). No return signal.

{| class="wikitable"
! Current !! Next
|-
| 00 || 01
|-
| 01 || 10
|-
| 10 || 11
|-
| 11 || 00
|}

* ''ADD B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || Z
|-
| 01 || 00 || NZ
|-
| 10 || 01 || Z
|-
| 11 || 01 || NZ
|}

* ''ADD B1'' increments and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || NZ
|-
| 01 || 01 || Z
|-
| 10 || 01 || NZ
|-
| 11 || 00 || Z
|}

=== SUB: subtractor ===

The subtractor works same as the adder, but using 2-bit two's complement arithmetic.

'''SUB Actions'''
* ''SUB A1'' increments the number (modulo 4). No return signal.

{| class="wikitable"
! Current !! Next
|-
| 00 || 01
|-
| 01 || 10
|-
| 10 || 11
|-
| 11 || 00
|}

* ''SUB B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || Z
|-
| 01 || 00 || NZ
|-
| 10 || 11 || Z
|-
| 11 || 11 || NZ
|}

* ''SUB B1'' decrements and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 11 || NZ
|-
| 01 || 00 || Z
|-
| 10 || 00 || NZ
|-
| 11 || 11 || Z
|}

=== MUL ===

MUL keeps a number between 0 and 10 in an internal register. MUL 0 divides the number by 2 (i.e., bit shifts it by 1 bit), and MUL 1 adds 10 and ''then'' divides the number by 2. The point of doing this is that performing MUL commands in succession can be used to multiply binary numbers one bit at a time, with the internal memory of the MUL component keeping track of future carry bits. This is used in the digit extraction step of the [[pi calculator|pi]] and [[phi calculator]] programs.

'''MUL Actions'''
* ''MUL 0''
* ''MUL 1''

=== B2D: 2d binary register ===

* B2D is two-dimensional binary register and is unbounded in positive X and Y directions.
* B2D can be used as memory array as well as 2d plotter.
* B2D register commands contain the string "B2D" in APGsembly code -- e.g., INC B2DX, TDEC B2DX, READ B2D, etc.
* The B2D has two arms X and Y. Each arm can be moved with INC and TDEC -- e.g., INC B2DX, TDEC B2DY.
* A program can retrieve a bit located at (X, Y) via the READ B2D command. READ B2D will always set the (X, Y) bit back to 0 (empty space). This means there is no need for a RESET B2D command, so only SET B2D is implemented.

'''B2D Actions'''
* ''INC B2DX'' increases the position of the X arm. No return signal.
* ''INC B2DY'' increases the position of the Y arm. No return signal.
* ''TDEC B2DX'' decreases the position of X arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''TDEC B2DY'' decreases the position of Y arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''READ B2D'' returns the state of the binary value located at (X, Y) and then sets it equal to 0. Returns Z if the value is 0 (empty), otherwise NZ.
* ''SET B2D'' sets the state at (X, Y) to 1 (breaks if the cell is set to 1). No return signal.

=== Digit printer ===

The ''digit printer'' can print "." and digits 0-9. No return signal.

'''Digit printer actions'''
* ''OUTPUT x'', for x = ., 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.

== Further details ==
* For further discussion and examples, or to ask questions, see [https://conwaylife.com/forums/viewtopic.php?f=2&t=4196 this conwaylife.com forum thread].
* [[Conway's Game of Life: Mathematics and Construction]], Chapter 9: Universal Computation
* [https://conwaylife.com/forums/viewtopic.php?p=221972#p221972 A compiler and emulator] written in Lua for use in Golly.
* [https://github.com/dvgrn/b3s23life/tree/main/calculator A compiler and debugger] for use in Golly. This is an old (1.0) version.
* [https://rei1024.github.io/apgsembly-emulator/ An emulator] that works in a web browser.

== References ==
<references>
<ref name="post199807">{{LinkForumThread
|format = ref
|p = 199807
|title = Re: Smaller Pi Calculator Challenge
|author = branoc
|date = December 14, 2024
|accessdate = June 29, 2025
}}</ref>
<ref name="rename2021">{{cite web
|url=https://github.com/rei1024/apgsembly-emulator/issues/1
|title=alternate identifier for R, T, and SQ units
|author=Dave Greene
|website=GitHub
|date=November 20, 2020
|accessdate = June 29, 2025
}}</ref>
</references>

[[Category:Everything else]]
[[Category:Universal computation]]

CatForce

2026-02-20T14:48:02Z

Rei:

{{Software
|name = CatForce
|url = https://github.com/simsim314/CatForce
|purpose = Finding oscillators and conduits
|createdby = [[Michael Simkin]]
|platform = Unix; Windows
}}
'''CatForce''' is an optimized [[search program]] written by [[Michael Simkin]] in {{year|2015}}, performing a brute-force enumeration of small [[Spartan]] objects in a limited area, instead of a depth-first tree search. One major purpose of CatForce is to find [[glider synthesis|glider-constructible]] completions for [[signal]] [[conduit]]s. An early CatForce discovery was the [[B60]] conduit, which enabled a [[Simkin glider gun|record-breaking new glider gun]].

In May {{year|2022}}, [[Mitchell Riley]] created a modification of CatForce, both significantly improving speed and adding a [[static symmetry|symmetry]] option.<ref name="post145414" /> This new version of the program was used to find numerous new oscillators, with some of the notable examples being the [[p84 honey farm hassler]], [[58P37]], [[Cribbage]] and [[74P34]].

==References==
<references>
<ref name="post145414">{{LinkForumThread
|format = ref
|title = Re: CatForce new catalyst search utility (LifeAPI based)
|p = 145414
|author = Mitchell Riley
|date = May 10, 2022
}}</ref>
</references>

==See also==
* [[LifeAPI]]
* [[QuFince]]

==External links==
* [https://github.com/simsim314/CatForce CatForce] on GitHub (original)
* [https://github.com/mvr/CatForce/tree/depth-first-periodic CatForce] on GitHub (Mitchell Riley's modification)
* {{LinkLexicon|lex_c.htm#catforce}}
* {{LinkForumThread|f=9|t=1678|title=CatForce new catalyst search utility (LifeAPI based)}}
* {{LinkForumThread|p=149317|title=Re: CatForce new catalyst search utility (LifeAPI based)}} (setup tutorial for symmetric CatForce)
* {{LinkForumThread|format=ref|f=12|t=6038|title=CatForce port to INT attempt}}

[[Category:Search software]]
[[Category:Catalysts and catalyses]]

Kinetic symmetry

2026-02-14T07:26:21Z

Rei: Fix typo

{{stub|The pattern with oscillators displaying the 43 temporal symmetry types needs fully explanatory text/caption; it might also be good to produce a version of that illustration showing Hickerson-format labels, instead of their pairs-of-Catagolue-symmetry-designator equivalents; and more details and/or references have been [https://conwaylife.com/forums/viewtopic.php?p=201738#p201738 requested] for the Spaceship section}}
A '''kinetic symmetry''' (contrast [[static symmetry]]) describes the spatial and temporal symmetries of [[still life]]s, [[oscillator]]s and [[spaceship]]s. It combines a pattern's spatial (rotational and reflectional) symmetries from the more general [[static symmetry]] with symmetrical transformations of said pattern arising from its evolution.<ref name="post138823" />

== On a square grid ==
[[File:kinetic_symmetry_diagram.png|center|672px]]
There are a total of 43 different kinetic symmetries possible on a usual [[square grid]], comprised of the 16 static symmetries (D8_2 is excluded) with 27 possible time transformations. The ratio of a pattern's [[mod]] to its [[period]], for rules on a square grid, can only be 1, 2 or 4.

Oscillators have a much wider range of possible kinetic symmetries than still lifes. It is easy to see that the 27 time transformations cannot apply to still lifes by definition, as they require the pattern to have distinct phases that can be compared to each other, and therefore the pattern has to evolve over time (which still lifes do not).

Both still lifes and oscillators can exhibit a wider range of symmetries than spaceships can, at least as far as isotropic rules are concerned. Many higher kinetic symmetries, notably those involving rotation or with reflection happening on more than one axis, would forbid the pattern from having a nonzero displacement, as the symmetry would either force it to move in two directly opposing directions or redirect it back to its starting point. Many spaceships can have glide symmetry, which oscillators cannot have due to having no overall displacement. However, glide symmetry very closely resembles certain mirror symmetries which oscillators do exhibit.

=== Kinetic symmetry naming system ===
[[Dean Hickerson]] invented a compact naming system for kinetic symmetries.<ref>{{CiteHickersonOscillators|accessdate=December 13, 2021}}</ref>

For still lifes, as well as oscillators and spaceships which have identical mods to periods, an initial symbol stands for a kind of transformation, and a symbol following it refers to the type of region where said transformation is centered.

Oscillators and spaceships of unequal period and mod will follow this string with another string detailing how the pattern's symmetry changes if all phases of the pattern are taken into account.

==== Symbols ====
{| class="wikitable"
! Symbol
! Meaning
|-
! n
| No symmetry
|-
! -
| One line of orthogonal mirror symmetry
|-
! /
| One line of diagonal mirror symmetry
|-
! +
| Two lines of orthogonal mirror symmetry
|-
! x
| Two lines of diagonal mirror symmetry
|-
! *
| Two lines each of orthogonal and diagonal mirror symmetry
|-
! r
| 90-degree rotational symmetry
|-
! .
| 180-degree rotational symmetry
|-
! c
| Transformation is centered on the center of a cell
|-
! e
| Transformation is centered on the edge of a cell
|-
! k
| Transformation is centered on the vertex of a cell
|}

=== Still lifes ===
These are equivalent to static symmetries (excluding D8_2). The corresponding static symmetries are detailed in the table for each type.

{{:Table of equivalent static symmetries}}

=== Oscillators ===
There are 43 oscillator symmetry types. In Hickerson's notation, each of those 43 types has a two-part identifier starting with generation 0's symmetry type, and appending the symmetry type of the full set of all phases of the oscillator.

16 out of those oscillator symmetry types consist of two identical parts, as in "xkxk" for example: the identifier is a doubled version of the single-phase symmetry type from the table above ("xk" in this case). An oscillator with any of these 16 symmetry types will have a mod that is equal to its period.

The remaining (27 = 43 - 16) oscillator symmetry types consist of two different parts (as in "-c+e" or "nrk").

Note that "xk" by itself refers to one of the 16 single-generation symmetry types, while "xkxk" refers to one of the 43 oscillator symmetry types. The sets of identifiers for still lifes and for oscillators are completely disjoint. This helpful property makes it easy to tell whether a descriptor refers to a single-generation symmetry type or an oscillator symmetry type.

In the table below, "composite symmetry" refers to the symmetry type of the collection of phases of the oscillator that can be matched up to each other:
* for patterns with a mod equal to half their period, the union of the pattern's initial state and the state it appears in at half its period
* for patterns with a mod equal to a quarter their period, the union of the pattern's initial phase, generation [period/4], generation [period/2] and generation [3period/4]

{| class="wikitable"
! rowspan="2" | Name
! colspan="2" | Symmetry
! rowspan="2" | Transform names
! rowspan="2" | <abbr title="Period divided by mod">p/m</abbr>
! rowspan="2" | Description

! rowspan="2" | Example
! rowspan="2" | [[Gutteroid]]s
|-
! Static
! Composite
|-
! n-c
! n C1
! -c D2_+1
! rowspan="2" | FlipX FlipY
| 2
| Pattern is asymmetric Appears flipped across an orthogonal line during (period/2) Line passes through cell centers and edges

| <center>[[File:xp2_466t186z6961696.png|64px]] [[xp2_466t186z6961696|unnamed]]</center>
| 1 orthogonal p/2
|-
! n-e
! n C1
! -e D2_+2
| 2
| Pattern is asymmetric Appears flipped across an orthogonal line during (period/2) Line passes through cell edges and vertices

| <center>[[File:Blockongriddle.png|64px]] [[Block on griddle]]</center>
| none
|-
! n/
! n C1
! / D2_x
! Flip⟍ Flip⟋
| 2
| Pattern is asymmetric Appears flipped across a diagonal line during (period/2)

| <center>[[File:Mutteringmoat1.png|64px]] [[Muttering moat 1]]</center>
| 1 diagonal p/2
|-
! n.c
! n C1
! .c C2_1
! rowspan="3" | Rot180
| 2
| Pattern is asymmetric Appears rotated 180 degrees during (period/2) Rotation is centered on the center of a cell

| <center>[[File:xp2_0ml1ik8z1259a6.png|64px]] [[xp2_0ml1ik8z1259a6|unnamed]]</center>
| central cell p/2
|-
! n.e
! n C1
! .e C2_2
| 2
| Pattern is asymmetric Appears rotated 180 degrees during (period/2) Rotation is centered on the edge of a cell

| <center>[[File:Laputa.png|64px]] [[Laputa]]</center>
| none
|-
! n.k
! n C1
! .k C2_4
| 2
| Pattern is asymmetric Appears rotated 180 degrees during (period/2) Rotation is centered on the vertex of a cell

| <center>[[File:2.3.3.png|64px]] [[2.3.3|unnamed]]</center>
| none
|-
! nrc
! n C1
! rc C4_1
! rowspan="2" | Rot90CW Rot90CCW
| 4
| Pattern is asymmetric Appears rotated 90 degrees every (period/4) Rotation is centered on the center of a cell

| <center>[[File:Dinnertable.png|64px]] [[Dinner table]]</center>
| central cell p/4
|-
! nrk
! n C1
! rk C4_4
| 4
| Pattern is asymmetric Appears rotated 90 degrees every (period/4) Rotation is centered on the vertex of a cell

| <center>[[File:Sixtynine.png|64px]] [[Sixty-nine]]</center>
| none
|-
! -c+c
! -c D2_+1
! +c D4_+1
! rowspan="4" | FlipXOrRot180 FlipYOrRot180
| 2
| Pattern has D2_+1 symmetry Appears flipped across a perpendicular orthogonal line during (period/2) Line passes through cell centers and edges

| <center>[[File:Piston.png|64px]] [[Piston]]</center>
| 1 orthogonal p/2
|-
! -c+e
! -c D2_+1
! +e D4_+2
| 2
| Pattern has D2_+1 symmetry Appears flipped across a perpendicular orthogonal line during (period/2) Line passes through cell edges and vertices

| <center>[[File:Byflops.png|64px]] [[by flops]]</center>
| none
|-
! -e+e
! -e D2_+2
! +e D4_+2
| 2
| Pattern has D2_+2 symmetry Appears flipped across a perpendicular orthogonal line during (period/2) Line passes through cell centers and edges

| <center>[[File:xp2_0giligz344k743zw121.png|64px]] [[xp2_0giligz344k743zw121|unnamed]]</center>
| 1 orthogonal p/2
|-
! -e+k
! -e D2_+2
! +k D4_+4
| 2
| Pattern has D2_+2 symmetry Appears flipped across a perpendicular orthogonal line during (period/2) Line passes through cell edges and vertices

| <center>[[File:2.5.6.png|64px]]{{br}}{{LinkCatagolue|code=xp2_g8j1qc6i0qdj8gz12pgb6c90bmp21|style=raw|patternname=unnamed}}</center>
| none
|-
! /xc
! / D2_x
! xc D4_x1
! rowspan="2" | Flip⟍OrRot180 Flip⟋OrRot180
| 2
| Pattern has D2_x symmetry Appears flipped across a perpendicular diagonal line during (period/2) Lines meet at the center of a cell

| <center>[[File:xp2_066oo4g53zc8502046.png|64px]] [[xp2_066oo4g53zc8502046|unnamed]]</center>
| 1 diagonal p/2
|-
! /xk
! / D2_x
! xk D4_x4
| 2
| Pattern has D2_x symmetry Appears flipped across a perpendicular diagonal line during (period/2) Lines meet at the vertex of a cell

| <center>[[File:Tripole.png|64px]] [[Tripole]]</center>
| 1 diagonal p/2
|-
! .c+c
! .c C2_1
! +c D4_+1
! FlipOrth
| 2
| Pattern has C2_1 symmetry Appears flipped across one of two perpendicular orthogonal lines during (period/2) Both lines pass through cell centers and edges

| <center>[[File:xp2_g8j1cdj8gz01cb38c1.png|64px]] [[xp2_g8j1cdj8gz01cb38c1|unnamed]]</center>
| 2 orthogonal p/2
|-
! .cxc
! .c C2_1
! xc D4_x1
! FlipDiag
| 2
| Pattern has C2_1 symmetry Appears flipped across one of two diagonal lines during (period/2) Lines meet at the center of a cell

| <center>[[File:Bipole.png|64px]] [[Bipole]]</center>
| 2 diagonal p/2
|-
! .crc
! .c C2_1
! rc C4_1
! Rot90
| 2
| Pattern has C2_1 symmetry Appears rotated 90 degrees either clockwise or anticlockwise during (period/2) Rotation is centered on the center of a cell

| <center>[[File:xp2_2aa08060922zgg50p050lkgzw1.png|64px]] [[xp2_2aa08060922zgg50p050lkgzw1|unnamed]]</center>
| central cell p/2
|-
! .e+e
! .e C2_2
! +e D4_+2
! rowspan="2" | FlipOrth
| 2
| Pattern has C2_2 symmetry Appears flipped across one of two perpendicular orthogonal lines during (period/2) Line may pass through either cell centers and edges, or cell edges and vertices

| <center>[[File:2.6.0.png|64px]]{{br}}{{LinkCatagolue|code=xp2_0o4cjia3s4oz5t2q3hcei2t5zw11622611|style=raw|patternname=unnamed}}</center>
| 1 orthogonal p/2
|-
! .k+k
! .k C2_4
! +k D4_+4
| 2
| Pattern has C2_4 symmetry Appears flipped across one of two perpendicular orthogonal lines during (period/2) Both lines pass through cell edges and vertices

| <center>[[File:xp2_0e0j0944z44i0p0e.png|64px]] [[xp2_0e0j0944z44i0p0e|unnamed]]</center>
| none
|-
! .kxk
! .k C2_4
! xk D4_x4
! FlipDiag
| 2
| Pattern has C2_4 symmetry Appears flipped across one of two diagonal lines during (period/2) Lines meet at the vertex of a cell

| <center>[[File:Clock.png|64px]] [[Clock]]</center>
| 2 diagonal p/2
|-
! .krk
! .k C2_4
! rk C4_4
! Rot90
| 2
| Pattern has C2_4 symmetry Appears rotated 90 degrees either clockwise or anticlockwise during (period/2) Rotation is centered on the vertex of a cell

| <center>[[File:2.6.3.png|64px]]{{br}}{{LinkCatagolue|code=xp2_g80c0gxcg2c0v1k4z11tp10244g084410gzx10g442014480gjnggzw45gv06816x106021|style=raw|patternname=unnamed}}</center>
| none
|-
! +c*c
! +c D4_+1
! *c D8_1
! rowspan="2" | FlipDiagOrRot90
| 2
| Pattern has D4_+1 symmetry Appears rotated 90 degrees either clockwise or anticlockwise during (period/2) Could also be interpreted as diagonal flipping on one of two lines Rotation is centered on/lines intersect at the center of a cell

| <center>[[File:Blinker.png|64px]] [[Blinker]]</center>
| 2 diagonal p/2
|-
! +k*k
! +k D4_+4
! *k D8_4
| 2
| Pattern has D4_+4 symmetry Appears rotated 90 degrees either clockwise or anticlockwise during (period/2) Could also be interpreted as diagonal flipping on one of two lines Rotation is centered on/lines intersect at the vertex of a cell

| <center>[[File:4.10.2.png|64px]]{{br}}{{LinkCatagolue|code=xp4_y1gs2ib8owo8bi2sgzgs2ib88g35i2222i53g88bi2sgzxji1wvwuwuwvw1ijz2egjk542h8iggggi8h245kjge2zy012egjl46w64ljge21zy51y21|style=raw|patternname=unnamed}}</center>
| 2 diagonal p/2
|-
! xc*c
! xc D4_x1
! *c D8_1
! rowspan="2" | FlipOrthOrRot90
| 2
| Pattern has D4_x1 symmetry Appears rotated 90 degrees either clockwise or anticlockwise during (period/2) Could also be interpreted as horizontal flipping on one of two lines Rotation is centered on/lines intersect at the center of a cell

| <center>[[File:Washingmachine.png|64px]] [[Washing machine]]</center>
| 2 orthogonal p/2
|-
! xk*k
! xk D4_x4
! *k D8_4
| 2
| Pattern has D4_x4 symmetry Appears rotated 90 degrees either clockwise or anticlockwise during (period/2) Could also be interpreted as horizontal flipping on one of two lines Rotation is centered on/lines intersect at the vertex of a cell

| <center>[[File:2.5.2.png|64px]]{{br}}{{LinkCatagolue|code=xp2_ggw392g5jwggzpi81k1g08281kpzy0ca049c|style=raw|patternname=unnamed}}</center>
| none
|-
! rc*c
! rc C4_1
! *c D8_1
! rowspan="2" | FlipOrthOrDiag
| 2
| Pattern has C4_1 symmetry Appears flipped across one of two perpendicular orthogonal lines during (period/2) Both lines pass through cell centers and edges

| <center>[[File:2.5.0.png|64px]]{{br}}{{LinkCatagolue|code=xp2_wc4oql2gkcz25ice08or1i52zw110252011|style=raw|patternname=unnamed}}</center>
| 2 orthogonal 2 diagonal p/2
|-
! rk*k
! rk C4_4
! *k D8_4
| 2
| Pattern has C4_4 symmetry Appears flipped across one of two perpendicular orthogonal lines during (period/2) Both lines pass through cell edges and vertices

| <center>[[File:Quad.png|64px]] [[Quad]]</center>
| 2 diagonal p/2
|}

The following shows oscillators displaying each of the 43 temporal symmetry types:
{| style="margin:auto;width:300px;"
{{EmbedViewer
| viewerconfig = #C [[ GPS 20 THUMBSIZE 2 ZOOM 4 WIDTH 1640 HEIGHT 1000 ]]
| pname = temporalsymmetrytypes
| position = center
}}
|}
row 1: [[Caterer]], [[Honey thieves]], [[Beluchenko's p40]], [[22P36]], [[Kok's galaxy]], [[48P22.1]], [[1-2-3-4]], [[Short keys]], [[Heart]], [[Gray counter]], [[Pentadecathlon]], [[101]], [[Merzenich's p11]], [[Jason's p6]], [[Diamond ring]], [[Octagon 2]]{{br}}
row 2: [[Baker's dozen]], [[Merzenich's p64]], [[Achim's p144]], [[Windmill]], [[Achim's p16]], [[44P10]], [[Tumbler]], [[Heavyweight emulator]], [[46P10]], [[68P32.1]], [[A for all]], [[Washing machine]], [[Unicycle ]]{{br}}
row 3: [[Trans-queen bee shuttle]], [[2.2.6]], [[Two pre-L hasslers]], [[Eureka]], [[Traffic light hasslers#p30|p30 traffic light hassler]], [[p24 shuttle]]{{br}}
row 4: [[Blocker]], [[Achim's p8]]{{br}}
row 5: [[Champagne glass]], [[p196 pi-heptomino hassler]]{{br}}
row 6: [[Rob's p16]]{{br}}
row 7: [[30P6.1]]{{br}}
row 8: [[Four eaters hassling lumps of muck]]{{br}}
row 9: [[Twirling T-tetsons 2]]

==== Array ====

{| class="wikitable" style="text-align:center"
|composite\static||C1||D2_+1||D2_+2||C2_2||D4_+2||D2_x||C2_1||C2_4||D4_+1||D4_+4||D4_x1||D4_x4||C4_1||C4_4||D8_1||D8_4
|-
|C1||[[File:eater1.png|64px]]
|-
|D2_+1||[[File:xp2_466t186z6961696.png|64px]]||[[File:hat.png|64px]]
|-
|D2_+2||[[File:Blockongriddle.png|64px]]||||[[File:capandtable.png|64px]]
|-
|C2_2||[[File:Laputa.png|64px]]||||||[[File:Aircraftcarrier.png|64px]]
|-
|D4_+2||||[[File:Byflops.png|64px]]||[[File:xp2_0giligz344k743zw121.png|64px]]||[[File:2.6.0.png|64px]]||[[File:beehive.png|64px]]
|-
|D2_x||[[File:Mutteringmoat1.png|64px]]||||||||||[[File:boat.png|64px]]
|-
|C2_1||[[File:xp2_0ml1ik8z1259a6.png|64px]]||||||||||||[[File:longsnake.png|64px]]
|-
|C2_4||[[File:2.3.3.png|64px]]||||||||||||||[[File:Snake.png|64px]]
|-
|D4_+1||||[[File:Piston.png|64px]]||||||||||[[File:xp2_g8j1cdj8gz01cb38c1.png|64px]]||||[[File:Hatcissiamesehat.png|64px]]
|-
|D4_+4||||||[[File:2.5.6.png|64px]]||||||||||[[File:xp2_0e0j0944z44i0p0e.png|64px]]||||[[File:xs32_8o6ll6o8z23cllc32.png|64px]]
|-
|D4_x1||||||||||||[[File:xp2_066oo4g53zc8502046.png|64px]]||[[File:Bipole.png|64px]]||||||||[[File:ship.png|64px]]
|-
|D4_x4||||||||||||[[File:Tripole.png|64px]]||||[[File:Clock.png|64px]]||||||||[[File:barge.png|64px]]
|-
|C4_1||[[File:Dinnertable.png|64px]]||||||||||||[[File:xp2_2aa08060922zgg50p050lkgzw1.png|64px]]||||||||||||[[File:spiral.png|64px]]
|-
|C4_4||[[File:Sixtynine.png|64px]]||||||||||||||[[File:2.6.3.png|64px]]||||||||||||[[File:xs36_354m88ge93zoie122d4ko.png|64px]]
|-
|D8_1||||||||||||||||||[[File:Blinker.png|64px]]|| ||[[File:Washingmachine.png|64px]]||||[[File:2.5.0.png|64px]]||||[[File:tub.png|64px]]
|-
|D8_4||||||||||||||||||||[[File:4.10.2.png|64px]]||||[[File:2.5.2.png|64px]]||||[[File:Quad.png|64px]]||||[[File:block.png|64px]]
|}

=== Spaceships ===
Due to the constraints of isotropy, spaceships in 2D cannot have rotational symmetry any higher than C1. This limits the possible symmetries for a spaceship to eight. The following four symmetries describe spaceships with no time symmetry:

{| class="wikitable"
! Name
! Catagolue equivalent
! Description
! Diagram
! Example
|-
! n
! C1
| No symmetry
| [[File:Symmetry C1.png|64px]]
| <center>[[File:25p3h1v0.1.png|64px]] [[25P3H1V0.1]]</center>
|-
! -c
! D2_+1
| One line of orthogonal mirror symmetry Line passes through cell centers and edges
| [[File:Symmetry D2_+1.png|64px]]
| <center>[[File:Dart.png|64px]] [[Dart]]</center>
|-
! -e
! D2_+2
| One line of orthogonal mirror symmetry Line passes through cell edges and vertices
| [[File:Symmetry D2_+2.png|64px]]
| <center>[[File:56p6h1v0.png|64px]] [[56P6H1V0]]</center>
|-
! /
! D2_x
| One line of diagonal mirror symmetry
| [[File:Symmetry D2_x.png|64px]]
| <center>[[File:37p4h1v1.2.png|64px]] [[37P4H1V1.2]]</center>
|}

The remaining four symmetries describe spaceships which are temporally symmetric:

{| class="wikitable"
! Name
! Static symmetry
! Composite symmetry
! period/mod
! Description

! Example
|-
! n-c
! n (C1)
! -c (D2_+1)
| 2
| Pattern is asymmetric Appears flipped across an orthogonal line during (period/2) Line passes through cell centers and edges

| <center>[[File:Lwss.png|64px]] [[Lightweight spaceship]]</center>
|-
! n-e
! n (C1)
! -e (D2_+2)
| 2
| Pattern is asymmetric Appears flipped across an orthogonal line during (period/2) Line passes through cell edges and vertices

| <center>[[File:Twohwssdraggingboat.png|64px]] [[Two HWSS dragging boat]]</center>
|-
! n/
! n (C1)
! / (D2_x)
| 2
| Pattern is asymmetric Appears flipped across a diagonal line during (period/2) Line passes through cell centers and vertices

| <center>[[File:P8swantagalong.png|64px]] [[p8 swan tagalong]]</center>
|-
! n/e
! n (C1)
! /e (no static equivalent)
| 2
| Pattern is asymmetric Appears flipped across a diagonal line during (period/2) Line passes through cell edges

| <center>[[File:Glider.png|64px]] [[Glider]]</center>
|}

n/e is a kinetic symmetry exclusive to spaceships in which the diagonal line of reflection passes through the midpoints of the edges of cells, but never the vertices or cell centers. Only spaceships which move an odd number of cells diagonally in a period cycle can have this kinetic symmetry; those which move an even distance will have standard n/ symmetry.<ref>https://conwaylife.com/forums/viewtopic.php?f=7&t=1898&p=158648#p158648</ref> Indeed, oscillators with n/ symmetry translate by a total of 0 cells diagonally, an even number.

=== Related terms ===

==== Flipper ====
''''Flipper'''' can refer to any oscillator that appears reflected across an orthogonal or diagonal line halfway through its period cycle. There are many kinetic symmetries in which an oscillator flips halfway through its period:

* n-c, n-e, n/, -c+c, -c+e, -e+e, -e+k, /xc and /xk: flip across one line
* .c+c, .cxc, .e+e, .k+k and .kxk: flip across one of two perpendicular lines
* rc*c and rk*k: flip across one of four lines
* +c*c, +k*k, xc*c and xk*k: can be considered as either flipping across one of two perpendicular lines or as rotating 90 degrees around their center

==== Glide symmetry ====
A spaceship is said to be '''glide symmetric''' if it exhibits [https://en.wikipedia.org/wiki/Glide_reflection glide reflection] - that is, it becomes its mirror image halfway through its period cycle, alongside moving in its direction of travel. In practice, this means that the spaceship has either the n-c, n-e, n/ or n/e kinetic symmetries.

The term "flipper" is also sometimes used for these spaceships. The two terms are equivalent to some extent, as any glide symmetric spaceship is a flipper and any spaceship that is a flipper is glide symmetric.

== On other grids ==

=== Euclidean ===
See [[Hexagonal tiling#Symmetries|here]] for a list of all oscillator time symmetries on [[Hexagonal tiling|{6,3}]] or [[Triangular tiling|{3,6}]].

The time symmetries on [[Cubic honeycomb|{4,3,4}]] are listed [[Cubic grid symmetries#Kinetic symmetries|here]].

Symmetries on [[Tesseractic honeycomb|{4,3,3,4}]], [[16-cell honeycomb|{3,3,4,3}]] and [[24-cell honeycomb|{3,4,3,3}]] have been enumerated and given quaternion-based names, but have not been assigned human-readable names so far, likely due to the sheer quantity of even the static symmetries.

Symmetries on [[Penteractic honeycomb|{4,3,3,3,4}]] and higher are yet to be investigated at all.

Rules and symmetries on dense Euclidean tilings such as {5/2,10} and {8/3,8} have not been investigated so far due to their chaotic nature.

{| class="wikitable" style="text-align:center"
|+ Symmetry types per grid
! rowspan="2" | [[Schläfli symbol]]
! rowspan="2" | Static
! colspan="6" | Kinetic
! colspan="4" | Spaceship
! colspan="2" | Totals
|-
! p/2
! p/3
! p/4
! p/6
! p/8
! p/12
! p
! p/2
! p/3
! p/4
! Osc
! Ship
|-
! colspan="14" | Exceptional regular tilings
|-
! [[Triangular tiling|{3,6}]]
| rowspan="2" | 14
| rowspan="2" | 17
| rowspan="2" | 3
| rowspan="2" | -
| rowspan="2" | 1
| rowspan="2" | -
| rowspan="2" | -
| rowspan="2" | 3
| rowspan="2" | 4
| rowspan="2" | -
| rowspan="2" | -
| rowspan="2" | 35
| rowspan="2" | 7
|-
! [[Hexagonal tiling|{6,3}]]
|-
! [[16-cell honeycomb|{3,3,4,3}]]
| rowspan="2" | 501
| rowspan="2" | 1569
| rowspan="2" | 77
| rowspan="2" | 143
| rowspan="2" | 70
| rowspan="2" | 4
| rowspan="2" | 1
| rowspan="2" style="background-color:#ffc7ce" | ?
| rowspan="2" style="background-color:#ffc7ce" | ?
| rowspan="2" style="background-color:#ffc7ce" | ?
| rowspan="2" style="background-color:#ffc7ce" | ?
| rowspan="2" | 2365
| rowspan="2" style="background-color:#ffc7ce" | ?
|-
! [[24-cell honeycomb|{3,4,3,3}]]
|-
! colspan="14" | ''n''-hypercubic honeycombs
|-
! [[Apeirogon|{∞}]]
| 3
| 2
| -
| -
| -
| -
| -
| 1
| -
| -
| -
| 5
| 1
|-
! [[Square tiling|{4,4}]]
| 16
| 25
| -
| 2
| -
| -
| -
| 4
| 4
| -
| -
| 43
| 8
|-
! [[Cubic honeycomb|{4,3,4}]]
| 92
| 220
| 7
| 14
| 4
| -
| -
| 22
| 39
| 2
| 2
| 337
| 65
|-
! [[Tesseractic honeycomb|{4,3,3,4}]]
| 686
| 2535
| 38
| 235
| 46
| 2
| -
| style="background-color:#ffc7ce" | ?
| style="background-color:#ffc7ce" | ?
| style="background-color:#ffc7ce" | ?
| style="background-color:#ffc7ce" | ?
| 3542
| style="background-color:#ffc7ce" | ?
|-
! [[Penteractic honeycomb|{4,3,3,3,4}]]
| colspan="13" style="background-color:#aaaaaa" | unknown
|-
! [[Hexeractic honeycomb|{4,3,3,3,3,4}]]
| colspan="13" style="background-color:#aaaaaa" | unknown
|}

In general, an ''n''-dimensional cubic honeycomb will have kinetic symmetries where the mod is the period divided by ''n'' as well as symmetries where it is divided by 2''n''.

=== Hyperbolic ===
Cellular automata have been investigated on compact hyperbolic tilings; paracompact and noncompact tilings are generally not considered due to the existence of ideal an ultra-ideal elements. There are an infinite number of possible compact tilings in 2D hyperbolic space.

For a tiling {p,q} where both p and q are prime, there are eight possible symmetries.<ref>https://conwaylife.com/forums/viewtopic.php?f=11&t=6640&p=220362#p220640</ref>

== See also ==
* [[LifeWiki:Project OmniOsci]]

== References ==
<references>
<ref name="post138823">{{LinkForumThread
|format = ref
|title = Re: Help with symmetries
|p = 138823
|author = GUYTU6J
|date = December 13, 2021
}}</ref>
</references>

== External links ==
{{LinkLexicon|lex_f.htm#flipper|name=Flipper}}

[[Category:Everything else]]

APGsembly

2026-02-05T15:56:34Z

Rei: faster B2D

The '''general purpose calculator''' ('''GPC''') is a way to implement computational tasks inside Conway's Game of Life. It is [[Turing complete]] and programmed by a special-purpose programming language called '''APGsembly'''. The first computational Life patterns using this technology were constructed by [[Adam P. Goucher]] in 2009 and 2010. The [[Spartan universal computer-constructor]], [[pi calculator]] and [[phi calculator]] patterns, and a related pattern programmed to grow at [[Osqrtlogt|O(sqrt(log(t)))]], had all the same basic general-purpose components that make up the GPC.

Goucher's original compiler/editor was written in DarkBasic, which became difficult to run on modern computers. In 2019 a Golly Python-script compiler was written by [[Dave Greene]] to create a Conway's Life pattern corresponding to APGsembly code, and a visual emulator and debugger was written by [[Michael Simkin]] and Dave Greene. At that time the logic circuitry was adjusted to include a standard set of components, and the resulting "GPC" was shown to be capable of supporting any of the three programs (pi, phi, or Osqrtlogt). In 2024, branoc created a version of the compiler and emulator based on the updated specifications from ''[[Conway's Game of Life: Mathematics and Construction]]'' textbook.<ref name="post199807" />

The base GPC pattern includes just the logic and memory circuitry; an additional subpattern representing an APGsembly program should be attached to a GPC to produce a complete calculator, printer, or other functional pattern. The additional subpattern is basically a finite-state machine. Each line in an APGsembly program corresponds to a state, and there are JUMP instructions for each possible return value (Z or NZ), pointing to the next state that the machine should enter. Each line of code can trigger one or more commands, or "actions", and it's important to make sure that each line includes exactly one action that returns a zero/nonzero value.

== Overview ==

The GPC includes a ticking clock in the form of two synchronized glider guns of period 2^17, 2^18 or higher, depending on the size of the program. These guns emit a glider each time an action has been executed with a return value of either Z or NZ, represented by a glider emitted on one of two possible output [[lane]]s, as a result of the most recent output-producing action. These actions are triggered by an input glider emitted by the calculator program pattern, sent into special computational units on specific lanes to trigger a specific action (ADD, SUB, WRITE, READ, INC, etc.) defined by the APGsembly code.

Thus the GPC has four major physical components:

# Clock.
# Program code.
# Computational unit array.
# Printer and B2D.

== The computational cycle ==

Every 2^N generations, a glider gun initiates an action based on the output from the previous cycle. The gun waits long enough that an output has most likely returned. If no output has in fact appeared (this can happen when retrieving data from a very long data tape, for example) the gun waits for another cycle and checks again, using a [[universal regulator]] mechanism.
* The return signal is always a one-bit output value, either Z or NZ.
* Each cycle is expected to return exactly one such output.

== Program code ==

APGsembly code consists of a list of actions to be performed for each ''state ID'', for each possible return value (Z or NZ). The program consists of lines of code; each state ID corresponds to two lines of code, one for Z and one for NZ.
#The program must start with INITIAL, and will halt if it ever executes HALT_OUT (or HALT) action.
#Two or more actions with Z/NZ responses for a single state are technically illegal, and will likely (though not inevitably) cause chaotic explosions in the calculator pattern.

Each line of code consists of 4 parts, separated by semicolons and optional whitespace:

'''StateID; Z/NZ; NextStateID; Action1, Action2, Action3, etc.'''

#'''StateID.''' Each line's first element is a state ID. This can be thought of as a line number, except that pairs of successive lines usually share the same state ID.
#'''Z/NZ.''' Each line's second element is either Z or NZ. Only the line matching the Z or NZ return value from the previous cycle will actually be executed.
#'''NextStateID.''' Each line's third element defines the state that will be executed on the next clock tick, if that line is executed.
#'''Action.''' Each line's fourth element defines a comma-separated list of actions to be executed. These actions are inputs to the computational units. Some actions will not return anything and only change the state of the computational unit; some will return either Z or NZ depending on the internal state of a particular unit. It is the programmer's task to make sure there is exactly one return value.

'''Example:'''

INITIAL; Z; A2; NOP
INITIAL; NZ; A2; NOP
A1; Z; A2; INC B0, NOP
A1; NZ; A2; INC B0, NOP
A2; Z; A1; SET B0, NOP
A2; NZ; A1; SET B0, NOP

This loads the B0 register with an increasing number of '1' bits. Notice that each state ID '''INITIAL''', '''A1''', and '''A2''' appears twice in the program, once for each possible Z return and once for each NZ return.

A syntactic shortcut added in the new compiler is the use of "*" to mean "both Z and NZ", and "ZZ" to mean "only Z is possible" for a given state. The above sample program could be written more compactly as

INITIAL; ZZ; A2; NOP
A1; *; A2; INC B0, NOP
A2; *; A1; SET B0, NOP

== Computational units ==

There are currently 6 types of logic units, though it is possible to add more. Each type of logic unit has one or more actions, triggered by glider inputs on specific lanes.

# ''NOP'' - The NOP action sends a Z output directly, and takes no other action.
# ''HALT'' - The HALT_OUT action halts the entire computation and emits a glider. The HALT action halts the entire computation without emitting a glider.
# ''U'' - sliding block register (holds a single integer value, stored in unary)
# ''B'' - binary string register (holds an arbitrary-length string of binary digits)
# ''ADD'' - adder
# ''SUB'' - subtractor
# ''MUL'' - multiplier
# ''B2D'' - a two-dimensional binary register.

The calculator can have an arbitrary number of U, B, ADD, SUB, and MUL units, one B2D unit, and one digit printer or character printer. Future versions of the compiler/emulator will support other components, such as an arbitrary number of fixed-width B2D units.

Before 2021, "U" was written as "R" (short for "register"), and "B2D" was written as "SQ" (short for "square"). The "T" (short for "tape") unit was an older version of the binary register, and differed in some ways from the B unit.<ref name="rename2021" />

=== U: Sliding block register ===

* Sliding block registers in APGsembly code are denoted by keywords starting with the letter U, short for "unary" -- for example, U0, U1, U2, etc.
* A sliding block register has very simple logic. It represents a single number, and all you can do with it is INC (increase by 1) and TDEC (test and decrease by 1).

'''U Actions:'''

* ''INC Ux'' will increase the register by 1. No return signal.
* ''TDEC Ux'' will decrease the register by 1. Returns NZ if the register > 0, otherwise Z.

=== B: Binary string register ===

* Binary string registers in APGsembly code are denoted by keywords starting with B, short for "binary" -- for example, B0, B1, B2, etc.
* A binary string register has a "reading head" that can be moved forward and backward along the tape with INC and TDEC, just like a sliding block register.
* A binary string register can store arbitrarily-large binary strings. A program can only retrieve one bit at a time using READ command. SET might be more clearly named "WRITE 1", but SET is the terms used in existing APGsembly.

'''B Actions'''

* ''INC Bx'' increases the position of reading head. No return signal.
* ''TDEC Bx'' decreases the position of reading head. Returns NZ unless at 0.
* ''READ Bx'' returns the state of the binary string value located at reading head and then sets it equal to 0. Returns Z if the value is 0 and NZ if 1.
* ''SET Bx'' sets the state of the current binary bit to 1 (breaks if the cell is set to 1). No return signal.

=== ADD: adder ===

One should think about the adder as having a 2-bit number. An A input just changes the state of the adder unit, whereas a B input returns the result.

* ''A0'' is not implemented as an input, because there is nothing to change.

'''ADD Actions'''
* ''ADD A1'' increments the number (modulo 4). No return signal.

{| class="wikitable"
! Current !! Next
|-
| 00 || 01
|-
| 01 || 10
|-
| 10 || 11
|-
| 11 || 00
|}

* ''ADD B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || Z
|-
| 01 || 00 || NZ
|-
| 10 || 01 || Z
|-
| 11 || 01 || NZ
|}

* ''ADD B1'' increments and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || NZ
|-
| 01 || 01 || Z
|-
| 10 || 01 || NZ
|-
| 11 || 00 || Z
|}

=== SUB: subtractor ===

The subtractor works same as the adder, but using 2-bit two's complement arithmetic.

'''SUB Actions'''
* ''SUB A1'' increments the number (modulo 4). No return signal.

{| class="wikitable"
! Current !! Next
|-
| 00 || 01
|-
| 01 || 10
|-
| 10 || 11
|-
| 11 || 00
|}

* ''SUB B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || Z
|-
| 01 || 00 || NZ
|-
| 10 || 11 || Z
|-
| 11 || 11 || NZ
|}

* ''SUB B1'' decrements and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 11 || NZ
|-
| 01 || 00 || Z
|-
| 10 || 00 || NZ
|-
| 11 || 11 || Z
|}

=== MUL ===

MUL keeps a number between 0 and 10 in an internal register. MUL 0 divides the number by 2 (i.e., bit shifts it by 1 bit), and MUL 1 adds 10 and ''then'' divides the number by 2. The point of doing this is that performing MUL commands in succession can be used to multiply binary numbers one bit at a time, with the internal memory of the MUL component keeping track of future carry bits. This is used in the digit extraction step of the [[pi calculator|pi]] and [[phi calculator]] programs.

'''MUL Actions'''
* ''MUL 0''
* ''MUL 1''

=== B2D: 2d binary register ===

* B2D is two-dimensional binary register and is unbounded in positive X and Y directions.
* B2D can be used as memory array as well as 2d plotter.
* B2D register commands contain the string "B2D" in APGsembly code -- e.g., INC B2DX, TDEC B2DX, READ B2D, etc.
* The B2D has two arms X and Y. Each arm can be moved with INC and TDEC -- e.g., INC B2DX, TDEC B2DY.
* A program can retrieve a bit located at (X, Y) via the READ B2D command. READ B2D will always set the (X, Y) bit back to 0 (empty space). This means there is no need for a RESET B2D command, so only SET B2D is implemented.

'''B2D Actions'''
* ''INC B2DX'' increases the position of the X arm. No return signal.
* ''INC B2DY'' increases the position of the Y arm. No return signal.
* ''TDEC B2DX'' decreases the position of X arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''TDEC B2DY'' decreases the position of Y arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''READ B2D'' returns the state of the binary value located at (X, Y) and then sets it equal to 0. Returns Z if the value is 0 (empty), otherwise NZ.
* ''SET B2D'' sets the state at (X, Y) to 1 (breaks if the cell is set to 1). No return signal.

=== Digit printer ===

The ''digit printer'' can print "." and digits 0-9. No return signal.

'''Digit printer actions'''
* ''OUTPUT x'', for x = ., 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.

== Further details ==
* For further discussion and examples, or to ask questions, see [https://conwaylife.com/forums/viewtopic.php?f=2&t=4196 this conwaylife.com forum thread].
* [[Conway's Game of Life: Mathematics and Construction]] Chapter 9. Universal Computation
* [https://conwaylife.com/forums/viewtopic.php?p=221972#p221972 A compiler and emulator] written in Lua for use in Golly.
* [https://github.com/dvgrn/b3s23life/tree/main/calculator A compiler and debugger] for use in Golly. This is an old (1.0) version.
* [https://rei1024.github.io/apgsembly-emulator/ An emulator] that works in a web browser.

== References ==
<references>
<ref name="post199807">{{LinkForumThread
|format = ref
|p = 199807
|title = Re: Smaller Pi Calculator Challenge
|author = branoc
|date = December 14, 2024
|accessdate = June 29, 2025
}}</ref>
<ref name="rename2021">{{cite web
|url=https://github.com/rei1024/apgsembly-emulator/issues/1
|title=alternate identifier for R, T, and SQ units
|author=Dave Greene
|website=GitHub
|date=November 20, 2020
|accessdate = June 29, 2025
}}</ref>
</references>

[[Category:Everything else]]

APGsembly

2025-11-30T00:55:53Z

Rei: update link

The '''general purpose calculator''' ('''GPC''') is a way to implement computational tasks inside Conway's Game of Life. It is [[Turing complete]] and programmed by a special-purpose programming language called '''APGsembly'''. The first computational Life patterns using this technology were constructed by [[Adam P. Goucher]] in 2009 and 2010. The [[Spartan universal computer-constructor]], [[pi calculator]] and [[phi calculator]] patterns, and a related pattern programmed to grow at [[Osqrtlogt|O(sqrt(log(t)))]], had all the same basic general-purpose components that make up the GPC.

Goucher's original compiler/editor was written in DarkBasic, which became difficult to run on modern computers. In 2019 a Golly Python-script compiler was written by [[Dave Greene]] to create a Conway's Life pattern corresponding to APGsembly code, and a visual emulator and debugger was written by [[Michael Simkin]] and Dave Greene. At that time the logic circuitry was adjusted to include a standard set of components, and the resulting "GPC" was shown to be capable of supporting any of the three programs (pi, phi, or Osqrtlogt). In 2024, branoc created a version of the compiler and emulator based on the updated specifications from ''[[Conway's Game of Life: Mathematics and Construction]]'' textbook.<ref name="post199807" />

The base GPC pattern includes just the logic and memory circuitry; an additional subpattern representing an APGsembly program should be attached to a GPC to produce a complete calculator, printer, or other functional pattern. The additional subpattern is basically a finite-state machine. Each line in an APGsembly program corresponds to a state, and there are JUMP instructions for each possible return value (Z or NZ), pointing to the next state that the machine should enter. Each line of code can trigger one or more commands, or "actions", and it's important to make sure that each line includes exactly one action that returns a zero/nonzero value.

== Overview ==

The GPC includes a ticking clock in the form of two synchronized glider guns of period 2^20, 2^22 or higher, depending on what components are being used (see '''B2D''' below). These guns emit a glider each time an action has been executed with a return value of either Z or NZ, represented by a glider emitted on one of two possible output [[lane]]s, as a result of the most recent output-producing action. These actions are triggered by an input glider emitted by the calculator program pattern, sent into special computational units on specific lanes to trigger a specific action (ADD, SUB, WRITE, READ, INC, etc.) defined by the APGsembly code.

Thus the GPC has four major physical components:

# Clock.
# Program code.
# Computational unit array.
# Printer and B2D.

== The computational cycle ==

Every 2^N generations, a glider gun initiates an action based on the output from the previous cycle. The gun waits long enough that an output has most likely returned. If no output has in fact appeared (this can happen when retrieving data from a very long data tape, for example) the gun waits for another cycle and checks again, using a [[universal regulator]] mechanism.
* The return signal is always a one-bit output value, either Z or NZ.
* Each cycle is expected to return exactly one such output.

== Program code ==

APGsembly code consists of a list of actions to be performed for each ''state ID'', for each possible return value (Z or NZ). The program consists of lines of code; each state ID corresponds to two lines of code, one for Z and one for NZ.
#The program must start with INITIAL, and will halt if it ever executes HALT_OUT (or HALT) action.
#Two or more actions with Z/NZ responses for a single state are technically illegal, and will likely (though not inevitably) cause chaotic explosions in the calculator pattern.

Each line of code consists of 4 parts, separated by semicolons and optional whitespace:

'''StateID; Z/NZ; NextStateID; Action1, Action2, Action3, etc.'''

#'''StateID.''' Each line's first element is a state ID. This can be thought of as a line number, except that pairs of successive lines usually share the same state ID.
#'''Z/NZ.''' Each line's second element is either Z or NZ. Only the line matching the Z or NZ return value from the previous cycle will actually be executed.
#'''NextStateID.''' Each line's third element defines the state that will be executed on the next clock tick, if that line is executed.
#'''Action.''' Each line's fourth element defines a comma-separated list of actions to be executed. These actions are inputs to the computational units. Some actions will not return anything and only change the state of the computational unit; some will return either Z or NZ depending on the internal state of a particular unit. It is the programmer's task to make sure there is exactly one return value.

'''Example:'''

INITIAL; Z; A2; NOP
INITIAL; NZ; A2; NOP
A1; Z; A2; INC B0, NOP
A1; NZ; A2; INC B0, NOP
A2; Z; A1; SET B0, NOP
A2; NZ; A1; SET B0, NOP

This loads the B0 register with an increasing number of '1' bits. Notice that each state ID '''INITIAL''', '''A1''', and '''A2''' appears twice in the program, once for each possible Z return and once for each NZ return.

A syntactic shortcut added in the new compiler is the use of "*" to mean "both Z and NZ", and "ZZ" to mean "only Z is possible" for a given state. The above sample program could be written more compactly as

INITIAL; ZZ; A2; NOP
A1; *; A2; INC B0, NOP
A2; *; A1; SET B0, NOP

== Computational units ==

There are currently 6 types of logic units, though it is possible to add more. Each type of logic unit has one or more actions, triggered by glider inputs on specific lanes.

# ''NOP'' - The NOP action sends a Z output directly, and takes no other action.
# ''HALT'' - The HALT_OUT action halts the entire computation and emits a glider. The HALT action halts the entire computation without emitting a glider.
# ''U'' - sliding block register (holds a single integer value, stored in unary)
# ''B'' - binary string register (holds an arbitrary-length string of binary digits)
# ''ADD'' - adder
# ''SUB'' - subtractor
# ''MUL'' - multiplier
# ''B2D'' - a two-dimensional binary register.

The calculator can have an arbitrary number of U, B, ADD, SUB, and MUL units, one B2D unit, and one digit printer or character printer. Future versions of the compiler/emulator will support other components, such as an arbitrary number of fixed-width B2D units.

Before 2021, "U" was written as "R" (short for "register"), and "B2D" was written as "SQ" (short for "square"). The "T" (short for "tape") unit was an older version of the binary register, and differed in some ways from the B unit.<ref name="rename2021" />

=== U: Sliding block register ===

* Sliding block registers in APGsembly code are denoted by keywords starting with the letter U, short for "unary" -- for example, U0, U1, U2, etc.
* A sliding block register has very simple logic. It represents a single number, and all you can do with it is INC (increase by 1) and TDEC (test and decrease by 1).

'''U Actions:'''

* ''INC Ux'' will increase the register by 1. No return signal.
* ''TDEC Ux'' will decrease the register by 1. Returns NZ if the register > 0, otherwise Z.

=== B: Binary string register ===

* Binary string registers in APGsembly code are denoted by keywords starting with B, short for "binary" -- for example, B0, B1, B2, etc.
* A binary string register has a "reading head" that can be moved forward and backward along the tape with INC and TDEC, just like a sliding block register.
* A binary string register can store arbitrarily-large binary strings. A program can only retrieve one bit at a time using READ command. SET might be more clearly named "WRITE 1", but SET is the terms used in existing APGsembly.

'''B Actions'''

* ''INC Bx'' increases the position of reading head. No return signal.
* ''TDEC Bx'' decreases the position of reading head. Returns NZ unless at 0.
* ''READ Bx'' returns the state of the binary string value located at reading head and then sets it equal to 0. Returns Z if the value is 0 and NZ if 1.
* ''SET Bx'' sets the state of the current binary bit to 1 (breaks if the cell is set to 1). No return signal.

=== ADD: adder ===

One should think about the adder as having a 2-bit number. An A input just changes the state of the adder unit, whereas a B input returns the result.

* ''A0'' is not implemented as an input, because there is nothing to change.

'''ADD Actions'''
* ''ADD A1'' increments the number (modulo 4). No return signal.

{| class="wikitable"
! Current !! Next
|-
| 00 || 01
|-
| 01 || 10
|-
| 10 || 11
|-
| 11 || 00
|}

* ''ADD B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || Z
|-
| 01 || 00 || NZ
|-
| 10 || 01 || Z
|-
| 11 || 01 || NZ
|}

* ''ADD B1'' increments and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || NZ
|-
| 01 || 01 || Z
|-
| 10 || 01 || NZ
|-
| 11 || 00 || Z
|}

=== SUB: subtractor ===

The subtractor works same as the adder, but using 2-bit two's complement arithmetic.

'''SUB Actions'''
* ''SUB A1'' increments the number (modulo 4). No return signal.

{| class="wikitable"
! Current !! Next
|-
| 00 || 01
|-
| 01 || 10
|-
| 10 || 11
|-
| 11 || 00
|}

* ''SUB B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || Z
|-
| 01 || 00 || NZ
|-
| 10 || 11 || Z
|-
| 11 || 11 || NZ
|}

* ''SUB B1'' decrements and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 11 || NZ
|-
| 01 || 00 || Z
|-
| 10 || 00 || NZ
|-
| 11 || 11 || Z
|}

=== MUL ===

MUL keeps a number between 0 and 10 in an internal register. MUL 0 divides the number by 2 (i.e., bit shifts it by 1 bit), and MUL 1 adds 10 and ''then'' divides the number by 2. The point of doing this is that performing MUL commands in succession can be used to multiply binary numbers one bit at a time, with the internal memory of the MUL component keeping track of future carry bits. This is used in the digit extraction step of the [[pi calculator|pi]] and [[phi calculator]] programs.

'''MUL Actions'''
* ''MUL 0''
* ''MUL 1''

=== B2D: 2d binary register ===

* B2D is two-dimensional binary register and is unbounded in positive X and Y directions.
* B2D can be used as memory array as well as 2d plotter.
* B2D register commands contain the string "B2D" in APGsembly code -- e.g., INC B2DX, TDEC B2DX, READ B2D, etc.
* The B2D has two arms X and Y. Each arm can be moved with INC and TDEC -- e.g., INC B2DX, TDEC B2DY.
* A program can retrieve a bit located at (X, Y) via the READ B2D command. READ B2D will always set the (X, Y) bit back to 0 (empty space). This means there is no need for a RESET B2D command, so only SET B2D is implemented.
* This B2D unit's internal circuitry operates fairly slowly. If an APGsembly program makes use of this component, a clock gun of at least period 2^22 is required.

'''B2D Actions'''
* ''INC B2DX'' increases the position of the X arm. No return signal.
* ''INC B2DY'' increases the position of the Y arm. No return signal.
* ''TDEC B2DX'' decreases the position of X arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''TDEC B2DY'' decreases the position of Y arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''READ B2D'' returns the state of the binary value located at (X, Y) and then sets it equal to 0. Returns Z if the value is 0 (empty), otherwise NZ.
* ''SET B2D'' sets the state at (X, Y) to 1 (breaks if the cell is set to 1). No return signal.

=== Digit printer ===

The ''digit printer'' can print "." and digits 0-9. No return signal.

'''Digit printer actions'''
* ''OUTPUT x'', for x = ., 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.

== Further details ==
* For further discussion and examples, or to ask questions, see [https://conwaylife.com/forums/viewtopic.php?f=2&t=4196 this conwaylife.com forum thread].
* [[Conway's Game of Life: Mathematics and Construction]] Chapter 9. Universal Computation
* [https://conwaylife.com/forums/viewtopic.php?p=221972#p221972 A compiler and emulator] written in Lua for use in Golly.
* [https://github.com/dvgrn/b3s23life/tree/main/calculator A compiler and debugger] for use in Golly. This is an old (1.0) version.
* [https://rei1024.github.io/apgsembly-emulator/ An emulator] that works in a web browser.

== References ==
<references>
<ref name="post199807">{{LinkForumThread
|format = ref
|p = 199807
|title = Re: Smaller Pi Calculator Challenge
|author = branoc
|date = December 14, 2024
|accessdate = June 29, 2025
}}</ref>
<ref name="rename2021">{{cite web
|url=https://github.com/rei1024/apgsembly-emulator/issues/1
|title=alternate identifier for R, T, and SQ units
|author=Dave Greene
|website=GitHub
|date=November 20, 2020
|accessdate = June 29, 2025
}}</ref>
</references>

[[Category:Everything else]]

APGsembly

2025-09-29T09:51:48Z

Rei: Add READ B2D sets 0

The '''general purpose calculator''' ('''GPC''') is a way to implement computational tasks inside Conway's Game of Life. It is [[Turing complete]] and programmed by a special-purpose programming language called '''APGsembly'''. The first computational Life patterns using this technology were constructed by [[Adam P. Goucher]] in 2009 and 2010. The [[Spartan universal computer-constructor]], [[pi calculator]] and [[phi calculator]] patterns, and a related pattern programmed to grow at [[Osqrtlogt|O(sqrt(log(t)))]], had all the same basic general-purpose components that make up the GPC.

Goucher's original compiler/editor was written in DarkBasic, which became difficult to run on modern computers. In 2019 a Golly Python-script compiler was written by [[Dave Greene]] to create a Conway's Life pattern corresponding to APGsembly code, and a visual emulator and debugger was written by [[Michael Simkin]] and Dave Greene. At that time the logic circuitry was adjusted to include a standard set of components, and the resulting "GPC" was shown to be capable of supporting any of the three programs (pi, phi, or Osqrtlogt). In 2024, branoc created a version of the compiler and emulator based on the updated specifications from ''[[Conway's Game of Life: Mathematics and Construction]]'' textbook.<ref name="post199807" />

The base GPC pattern includes just the logic and memory circuitry; an additional subpattern representing an APGsembly program should be attached to a GPC to produce a complete calculator, printer, or other functional pattern. The additional subpattern is basically a finite-state machine. Each line in an APGsembly program corresponds to a state, and there are JUMP instructions for each possible return value (Z or NZ), pointing to the next state that the machine should enter. Each line of code can trigger one or more commands, or "actions", and it's important to make sure that each line includes exactly one action that returns a zero/nonzero value.

== Overview ==

The GPC includes a ticking clock in the form of two synchronized glider guns of period 2^20, 2^22 or higher, depending on what components are being used (see '''B2D''' below). These guns emit a glider each time an action has been executed with a return value of either Z or NZ, represented by a glider emitted on one of two possible output [[lane]]s, as a result of the most recent output-producing action. These actions are triggered by an input glider emitted by the calculator program pattern, sent into special computational units on specific lanes to trigger a specific action (ADD, SUB, WRITE, READ, INC, etc.) defined by the APGsembly code.

Thus the GPC has four major physical components:

# Clock.
# Program code.
# Computational unit array.
# Printer and B2D.

== The computational cycle ==

Every 2^N generations, a glider gun initiates an action based on the output from the previous cycle. The gun waits long enough that an output has most likely returned. If no output has in fact appeared (this can happen when retrieving data from a very long data tape, for example) the gun waits for another cycle and checks again, using a [[universal regulator]] mechanism.
* The return signal is always a one-bit output value, either Z or NZ.
* Each cycle is expected to return exactly one such output.

== Program code ==

APGsembly code consists of a list of actions to be performed for each ''state ID'', for each possible return value (Z or NZ). The program consists of lines of code; each state ID corresponds to two lines of code, one for Z and one for NZ.
#The program must start with INITIAL, and will halt if it ever executes HALT_OUT (or HALT) action.
#Two or more actions with Z/NZ responses for a single state are technically illegal, and will likely (though not inevitably) cause chaotic explosions in the calculator pattern.

Each line of code consists of 4 parts, separated by semicolons and optional whitespace:

'''StateID; Z/NZ; NextStateID; Action1, Action2, Action3, etc.'''

#'''StateID.''' Each line's first element is a state ID. This can be thought of as a line number, except that pairs of successive lines usually share the same state ID.
#'''Z/NZ.''' Each line's second element is either Z or NZ. Only the line matching the Z or NZ return value from the previous cycle will actually be executed.
#'''NextStateID.''' Each line's third element defines the state that will be executed on the next clock tick, if that line is executed.
#'''Action.''' Each line's fourth element defines a comma-separated list of actions to be executed. These actions are inputs to the computational units. Some actions will not return anything and only change the state of the computational unit; some will return either Z or NZ depending on the internal state of a particular unit. It is the programmer's task to make sure there is exactly one return value.

'''Example:'''

INITIAL; Z; A2; NOP
INITIAL; NZ; A2; NOP
A1; Z; A2; INC B0, NOP
A1; NZ; A2; INC B0, NOP
A2; Z; A1; SET B0, NOP
A2; NZ; A1; SET B0, NOP

This loads the B0 register with an increasing number of '1' bits. Notice that each state ID '''INITIAL''', '''A1''', and '''A2''' appears twice in the program, once for each possible Z return and once for each NZ return.

A syntactic shortcut added in the new compiler is the use of "*" to mean "both Z and NZ", and "ZZ" to mean "only Z is possible" for a given state. The above sample program could be written more compactly as

INITIAL; ZZ; A2; NOP
A1; *; A2; INC B0, NOP
A2; *; A1; SET B0, NOP

== Computational units ==

There are currently 6 types of logic units, though it is possible to add more. Each type of logic unit has one or more actions, triggered by glider inputs on specific lanes.

# ''NOP'' - The NOP action sends a Z output directly, and takes no other action.
# ''HALT'' - The HALT_OUT action halts the entire computation and emits a glider. The HALT action halts the entire computation without emitting a glider.
# ''U'' - sliding block register (holds a single integer value, stored in unary)
# ''B'' - binary string register (holds an arbitrary-length string of binary digits)
# ''ADD'' - adder
# ''SUB'' - subtractor
# ''MUL'' - multiplier
# ''B2D'' - a two-dimensional binary register.

The calculator can have an arbitrary number of U, B, ADD, SUB, and MUL units, one B2D unit, and one digit printer or character printer. Future versions of the compiler/emulator will support other components, such as an arbitrary number of fixed-width B2D units.

Before 2021, "U" was written as "R" (short for "register"), and "B2D" was written as "SQ" (short for "square"). The "T" (short for "tape") unit was an older version of the binary register, and differed in some ways from the B unit.<ref name="rename2021" />

=== U: Sliding block register ===

* Sliding block registers in APGsembly code are denoted by keywords starting with the letter U, short for "unary" -- for example, U0, U1, U2, etc.
* A sliding block register has very simple logic. It represents a single number, and all you can do with it is INC (increase by 1) and TDEC (test and decrease by 1).

'''U Actions:'''

* ''INC Ux'' will increase the register by 1. No return signal.
* ''TDEC Ux'' will decrease the register by 1. Returns NZ if the register > 0, otherwise Z.

=== B: Binary string register ===

* Binary string registers in APGsembly code are denoted by keywords starting with B, short for "binary" -- for example, B0, B1, B2, etc.
* A binary string register has a "reading head" that can be moved forward and backward along the tape with INC and TDEC, just like a sliding block register.
* A binary string register can store arbitrarily-large binary strings. A program can only retrieve one bit at a time using READ command. SET might be more clearly named "WRITE 1", but SET is the terms used in existing APGsembly.

'''B Actions'''

* ''INC Bx'' increases the position of reading head. No return signal.
* ''TDEC Bx'' decreases the position of reading head. Returns NZ unless at 0.
* ''READ Bx'' returns the state of the binary string value located at reading head and then sets it equal to 0. Returns Z if the value is 0 and NZ if 1.
* ''SET Bx'' sets the state of the current binary bit to 1 (breaks if the cell is set to 1). No return signal.

=== ADD: adder ===

One should think about the adder as having a 2-bit number. An A input just changes the state of the adder unit, whereas a B input returns the result.

* ''A0'' is not implemented as an input, because there is nothing to change.

'''ADD Actions'''
* ''ADD A1'' increments the number (modulo 4). No return signal.

{| class="wikitable"
! Current !! Next
|-
| 00 || 01
|-
| 01 || 10
|-
| 10 || 11
|-
| 11 || 00
|}

* ''ADD B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || Z
|-
| 01 || 00 || NZ
|-
| 10 || 01 || Z
|-
| 11 || 01 || NZ
|}

* ''ADD B1'' increments and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || NZ
|-
| 01 || 01 || Z
|-
| 10 || 01 || NZ
|-
| 11 || 00 || Z
|}

=== SUB: subtractor ===

The subtractor works same as the adder, but using 2-bit two's complement arithmetic.

'''SUB Actions'''
* ''SUB A1'' increments the number (modulo 4). No return signal.

{| class="wikitable"
! Current !! Next
|-
| 00 || 01
|-
| 01 || 10
|-
| 10 || 11
|-
| 11 || 00
|}

* ''SUB B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || Z
|-
| 01 || 00 || NZ
|-
| 10 || 11 || Z
|-
| 11 || 11 || NZ
|}

* ''SUB B1'' decrements and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 11 || NZ
|-
| 01 || 00 || Z
|-
| 10 || 00 || NZ
|-
| 11 || 11 || Z
|}

=== MUL ===

MUL keeps a number between 0 and 10 in an internal register. MUL 0 divides the number by 2 (i.e., bit shifts it by 1 bit), and MUL 1 adds 10 and ''then'' divides the number by 2. The point of doing this is that performing MUL commands in succession can be used to multiply binary numbers one bit at a time, with the internal memory of the MUL component keeping track of future carry bits. This is used in the digit extraction step of the [[pi calculator|pi]] and [[phi calculator]] programs.

'''MUL Actions'''
* ''MUL 0''
* ''MUL 1''

=== B2D: 2d binary register ===

* B2D is two-dimensional binary register and is unbounded in positive X and Y directions.
* B2D can be used as memory array as well as 2d plotter.
* B2D register commands contain the string "B2D" in APGsembly code -- e.g., INC B2DX, TDEC B2DX, READ B2D, etc.
* The B2D has two arms X and Y. Each arm can be moved with INC and TDEC -- e.g., INC B2DX, TDEC B2DY.
* A program can retrieve a bit located at (X, Y) via the READ B2D command. READ B2D will always set the (X, Y) bit back to 0 (empty space). This means there is no need for a RESET B2D command, so only SET B2D is implemented.
* This B2D unit's internal circuitry operates fairly slowly. If an APGsembly program makes use of this component, a clock gun of at least period 2^22 is required.

'''B2D Actions'''
* ''INC B2DX'' increases the position of the X arm. No return signal.
* ''INC B2DY'' increases the position of the Y arm. No return signal.
* ''TDEC B2DX'' decreases the position of X arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''TDEC B2DY'' decreases the position of Y arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''READ B2D'' returns the state of the binary value located at (X, Y) and then sets it equal to 0. Returns Z if the value is 0 (empty), otherwise NZ.
* ''SET B2D'' sets the state at (X, Y) to 1 (breaks if the cell is set to 1). No return signal.

=== Digit printer ===

The ''digit printer'' can print "." and digits 0-9. No return signal.

'''Digit printer actions'''
* ''OUTPUT x'', for x = ., 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.

== Further details ==
* For further discussion and examples, or to ask questions, see [https://conwaylife.com/forums/viewtopic.php?f=2&t=4196 this conwaylife.com forum thread].
* [[Conway's Game of Life: Mathematics and Construction]] Chapter 9. Universal Computation
* [https://conwaylife.com/forums/viewtopic.php?p=202346#p202346 A compiler and emulator] written in Lua for use in Golly.
* [https://github.com/dvgrn/b3s23life/tree/main/calculator A compiler and debugger] for use in Golly. This is an old (1.0) version.
* [https://rei1024.github.io/apgsembly-emulator/ An emulator] that works in a web browser.

== References ==
<references>
<ref name="post199807">{{LinkForumThread
|format = ref
|p = 199807
|title = Re: Smaller Pi Calculator Challenge
|author = branoc
|date = December 14, 2024
|accessdate = June 29, 2025
}}</ref>
<ref name="rename2021">{{cite web
|url=https://github.com/rei1024/apgsembly-emulator/issues/1
|title=alternate identifier for R, T, and SQ units
|author=Dave Greene
|website=GitHub
|date=November 20, 2020
|accessdate = June 29, 2025
}}</ref>
</references>

[[Category:Everything else]]

APGsembly

2025-07-27T05:45:51Z

Rei: Add transition table for ADD and SUB

The '''general purpose calculator''' ('''GPC''') is a way to implement computational tasks inside Conway's Game of Life. It is [[Turing complete]] and programmed by a special-purpose programming language called '''APGsembly'''. The first computational Life patterns using this technology were constructed by [[Adam P. Goucher]] in 2009 and 2010. The [[Spartan universal computer-constructor]], [[pi calculator]] and [[phi calculator]] patterns, and a related pattern programmed to grow at [[Osqrtlogt|O(sqrt(log(t)))]], had all the same basic general-purpose components that make up the GPC.

Goucher's original compiler/editor was written in DarkBasic, which became difficult to run on modern computers. In 2019 a Golly Python-script compiler was written by [[Dave Greene]] to create a Conway's Life pattern corresponding to APGsembly code, and a visual emulator and debugger was written by [[Michael Simkin]] and Dave Greene. At that time the logic circuitry was adjusted to include a standard set of components, and the resulting "GPC" was shown to be capable of supporting any of the three programs (pi, phi, or Osqrtlogt). In 2024, branoc created a version of the compiler and emulator based on the updated specifications from ''[[Conway's Game of Life: Mathematics and Construction]]'' textbook.<ref name="post199807" />

The base GPC pattern includes just the logic and memory circuitry; an additional subpattern representing an APGsembly program should be attached to a GPC to produce a complete calculator, printer, or other functional pattern. The additional subpattern is basically a finite-state machine. Each line in an APGsembly program corresponds to a state, and there are JUMP instructions for each possible return value (Z or NZ), pointing to the next state that the machine should enter. Each line of code can trigger one or more commands, or "actions", and it's important to make sure that each line includes exactly one action that returns a zero/nonzero value.

== Overview ==

The GPC includes a ticking clock in the form of two synchronized glider guns of period 2^20, 2^22 or higher, depending on what components are being used (see '''B2D''' below). These guns emit a glider each time an action has been executed with a return value of either Z or NZ, represented by a glider emitted on one of two possible output [[lane]]s, as a result of the most recent output-producing action. These actions are triggered by an input glider emitted by the calculator program pattern, sent into special computational units on specific lanes to trigger a specific action (ADD, SUB, WRITE, READ, INC, etc.) defined by the APGsembly code.

Thus the GPC has four major physical components:

# Clock.
# Program code.
# Computational unit array.
# Printer and B2D.

== The computational cycle ==

Every 2^N generations, a glider gun initiates an action based on the output from the previous cycle. The gun waits long enough that an output has most likely returned. If no output has in fact appeared (this can happen when retrieving data from a very long data tape, for example) the gun waits for another cycle and checks again, using a [[universal regulator]] mechanism.
* The return signal is always a one-bit output value, either Z or NZ.
* Each cycle is expected to return exactly one such output.

== Program code ==

APGsembly code consists of a list of actions to be performed for each ''state ID'', for each possible return value (Z or NZ). The program consists of lines of code; each state ID corresponds to two lines of code, one for Z and one for NZ.
#The program must start with INITIAL, and will halt if it ever executes HALT_OUT (or HALT) action.
#Two or more actions with Z/NZ responses for a single state are technically illegal, and will likely (though not inevitably) cause chaotic explosions in the calculator pattern.

Each line of code consists of 4 parts, separated by semicolons and optional whitespace:

'''StateID; Z/NZ; NextStateID; Action1, Action2, Action3, etc.'''

#'''StateID.''' Each line's first element is a state ID. This can be thought of as a line number, except that pairs of successive lines usually share the same state ID.
#'''Z/NZ.''' Each line's second element is either Z or NZ. Only the line matching the Z or NZ return value from the previous cycle will actually be executed.
#'''NextStateID.''' Each line's third element defines the state that will be executed on the next clock tick, if that line is executed.
#'''Action.''' Each line's fourth element defines a comma-separated list of actions to be executed. These actions are inputs to the computational units. Some actions will not return anything and only change the state of the computational unit; some will return either Z or NZ depending on the internal state of a particular unit. It is the programmer's task to make sure there is exactly one return value.

'''Example:'''

INITIAL; Z; A2; NOP
INITIAL; NZ; A2; NOP
A1; Z; A2; INC B0, NOP
A1; NZ; A2; INC B0, NOP
A2; Z; A1; SET B0, NOP
A2; NZ; A1; SET B0, NOP

This loads the B0 register with an increasing number of '1' bits. Notice that each state ID '''INITIAL''', '''A1''', and '''A2''' appears twice in the program, once for each possible Z return and once for each NZ return.

A syntactic shortcut added in the new compiler is the use of "*" to mean "both Z and NZ", and "ZZ" to mean "only Z is possible" for a given state. The above sample program could be written more compactly as

INITIAL; ZZ; A2; NOP
A1; *; A2; INC B0, NOP
A2; *; A1; SET B0, NOP

== Computational units ==

There are currently 6 types of logic units, though it is possible to add more. Each type of logic unit has one or more actions, triggered by glider inputs on specific lanes.

# ''NOP'' - The NOP action sends a Z output directly, and takes no other action.
# ''HALT'' - The HALT_OUT action halts the entire computation and emits a glider. The HALT action halts the entire computation without emitting a glider.
# ''U'' - sliding block register (holds a single integer value, stored in unary)
# ''B'' - binary string register (holds an arbitrary-length string of binary digits)
# ''ADD'' - adder
# ''SUB'' - subtractor
# ''MUL'' - multiplier
# ''B2D'' - a two-dimensional binary register.

The calculator can have an arbitrary number of U, B, ADD, SUB, and MUL units, one B2D unit, and one digit printer or character printer. Future versions of the compiler/emulator will support other components, such as an arbitrary number of fixed-width B2D units.

Before 2021, "U" was written as "R" (short for "register"), and "B2D" was written as "SQ" (short for "square"). The "T" (short for "tape") unit was an older version of the binary register, and differed in some ways from the B unit.<ref name="rename2021" />

=== U: Sliding block register ===

* Sliding block registers in APGsembly code are denoted by keywords starting with the letter U, short for "unary" -- for example, U0, U1, U2, etc.
* A sliding block register has very simple logic. It represents a single number, and all you can do with it is INC (increase by 1) and TDEC (test and decrease by 1).

'''U Actions:'''

* ''INC Ux'' will increase the register by 1. No return signal.
* ''TDEC Ux'' will decrease the register by 1. Returns NZ if the register > 0, otherwise Z.

=== B: Binary string register ===

* Binary string registers in APGsembly code are denoted by keywords starting with B, short for "binary" -- for example, B0, B1, B2, etc.
* A binary string register has a "reading head" that can be moved forward and backward along the tape with INC and TDEC, just like a sliding block register.
* A binary string register can store arbitrarily-large binary strings. A program can only retrieve one bit at a time using READ command. SET might be more clearly named "WRITE 1", but SET is the terms used in existing APGsembly.

'''B Actions'''

* ''INC Bx'' increases the position of reading head. No return signal.
* ''TDEC Bx'' decreases the position of reading head. Returns NZ unless at 0.
* ''READ Bx'' returns the state of the binary string value located at reading head and then sets it equal to 0. Returns Z if the value is 0 and NZ if 1.
* ''SET Bx'' sets the state of the current binary bit to 1 (breaks if the cell is set to 1). No return signal.

=== ADD: adder ===

One should think about the adder as having a 2-bit number. An A input just changes the state of the adder unit, whereas a B input returns the result.

* ''A0'' is not implemented as an input, because there is nothing to change.

'''ADD Actions'''
* ''ADD A1'' increments the number (modulo 4). No return signal.

{| class="wikitable"
! Current !! Next
|-
| 00 || 01
|-
| 01 || 10
|-
| 10 || 11
|-
| 11 || 00
|}

* ''ADD B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || Z
|-
| 01 || 00 || NZ
|-
| 10 || 01 || Z
|-
| 11 || 01 || NZ
|}

* ''ADD B1'' increments and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || NZ
|-
| 01 || 01 || Z
|-
| 10 || 01 || NZ
|-
| 11 || 00 || Z
|}

=== SUB: subtractor ===

The subtractor works same as the adder, but using 2-bit two's complement arithmetic.

'''SUB Actions'''
* ''SUB A1'' increments the number (modulo 4). No return signal.

{| class="wikitable"
! Current !! Next
|-
| 00 || 01
|-
| 01 || 10
|-
| 10 || 11
|-
| 11 || 00
|}

* ''SUB B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 00 || Z
|-
| 01 || 00 || NZ
|-
| 10 || 11 || Z
|-
| 11 || 11 || NZ
|}

* ''SUB B1'' decrements and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

{| class="wikitable"
! Current !! Next !! Output
|-
| 00 || 11 || NZ
|-
| 01 || 00 || Z
|-
| 10 || 00 || NZ
|-
| 11 || 11 || Z
|}

=== MUL ===

MUL keeps a number between 0 and 10 in an internal register. MUL 0 divides the number by 2 (i.e., bit shifts it by 1 bit), and MUL 1 adds 10 and ''then'' divides the number by 2. The point of doing this is that performing MUL commands in succession can be used to multiply binary numbers one bit at a time, with the internal memory of the MUL component keeping track of future carry bits. This is used in the digit extraction step of the [[pi calculator|pi]] and [[phi calculator]] programs.

'''MUL Actions'''
* ''MUL 0''
* ''MUL 1''

=== B2D: 2d binary register ===

* B2D is two-dimensional binary register and is unbounded in positive X and Y directions.
* B2D can be used as memory array as well as 2d plotter.
* B2D register commands contain the string "B2D" in APGsembly code -- e.g., INC B2DX, TDEC B2DX, READ B2D, etc.
* The B2D has two arms X and Y. Each arm can be moved with INC and TDEC -- e.g., INC B2DX, TDEC B2DY.
* A program can retrieve a bit located at (X, Y) via the READ B2D command. READ B2D will always set the (X, Y) bit back to 0 (empty space). This means there is no need for a RESET B2D command, so only SET B2D is implemented.
* This B2D unit's internal circuitry operates fairly slowly. If an APGsembly program makes use of this component, a clock gun of at least period 2^22 is required.

'''B2D Actions'''
* ''INC B2DX'' increases the position of the X arm. No return signal.
* ''INC B2DY'' increases the position of the Y arm. No return signal.
* ''TDEC B2DX'' decreases the position of X arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''TDEC B2DY'' decreases the position of Y arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''READ B2D'' returns the state of the binary value located at (X, Y). Returns Z if the current state is 0 (empty), otherwise NZ.
* ''SET B2D'' sets the state at (X, Y) to 1 (breaks if the cell is set to 1). No return signal.

=== Digit printer ===

The ''digit printer'' can print "." and digits 0-9. No return signal.

'''Digit printer actions'''
* ''OUTPUT x'', for x = ., 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.

== Further details ==
* For further discussion and examples, or to ask questions, see [https://conwaylife.com/forums/viewtopic.php?f=2&t=4196 this conwaylife.com forum thread].
* [[Conway's Game of Life: Mathematics and Construction]] Chapter 9. Universal Computation
* [https://conwaylife.com/forums/viewtopic.php?p=202346#p202346 A compiler and emulator] written in Lua for use in Golly.
* [https://github.com/dvgrn/b3s23life/tree/main/calculator A compiler and debugger] for use in Golly. This is an old (1.0) version.
* [https://rei1024.github.io/apgsembly-emulator/ An emulator] that works in a web browser.

== References ==
<references>
<ref name="post199807">{{LinkForumThread
|format = ref
|p = 199807
|title = Re: Smaller Pi Calculator Challenge
|author = branoc
|date = December 14, 2024
|accessdate = June 29, 2025
}}</ref>
<ref name="rename2021">{{cite web
|url=https://github.com/rei1024/apgsembly-emulator/issues/1
|title=alternate identifier for R, T, and SQ units
|author=Dave Greene
|website=GitHub
|date=November 20, 2020
|accessdate = June 29, 2025
}}</ref>
</references>

[[Category:Everything else]]

Conway's Game of Life: Mathematics and Construction

2025-07-18T15:09:14Z

Rei:

{{Book
|name = Conway's Game of Life: Mathematics and Construction
|image = true
|iname = isbn9781794816961
|type = Book
|authors = Nathaniel Johnston and Dave Greene
|isbn = 978-1794816961
|link = https://conwaylife.com/book/
}}
'''''Conway's Game of Life: Mathematics and Construction''''' is a textbook about Life by [[Nathaniel Johnston]] and [[Dave Greene]]. In development since April 2016, it was released for beta readers on September 23, 2021 and officially launched on March 11, 2022.

==Chapters==
#Early Life
#[[Still life|Still Lifes]]
#[[Oscillator]]s
#[[Spaceship]]s and Moving Objects
#[[Glider synthesis|Glider Synthesis]]
#[[Periodic circuit|Periodic Circuitry]]
#[[Stable circuit|Stable Circuitry]]
#[[Gun]]s and [[Glider stream|Glider Stream]]s
#[[Universal computer|Universal Computation]]
#[[Self-supporting|Self-Supporting]] Spaceships
#[[Universal constructor|Universal Construction]]
#The [[0E0P metacell|0E0P Metacell]]

==See also==
* [[Conway's Game of Life: Mathematics and Construction/Errata|Errata and Anachronisms]] in the book
* [[LifeWiki:Bookshelf]]

==External links==
* [https://conwaylife.com/book/ PDF and relevant RLE files]
* [https://www.lulu.com/en/us/shop/dave-greene-and-nathaniel-johnston/conways-game-of-life/hardcover/product-ev72jn.html?page=1&pageSize=4 Hardcover] from Lulu.com
* [https://www.kickstarter.com/projects/777855805/conways-game-of-life-textbook-launch Kickstarter] for special-edition copies
* [https://github.com/nathanieljohnston/game-of-life-book GitHub repository]
* {{LinkForumThread|f=7|t=5418|title=Beta Reader Thread for Game of Life Textbook}}
* {{LinkForumThread|f=7|t=5591|title=Conway's Game of Life Textbook Launch}}

[[Category:Everything else]]
[[Category:Books and articles]]
{{DISPLAYTITLE:''Conway's Game of Life: Mathematics and Construction''}}

APGsembly

2025-07-01T11:50:24Z

Rei: Fix description and typo

The '''general purpose calculator''' ('''GPC''') is a way to implement computational tasks inside Conway's Game of Life. It is [[Turing complete]] and programmed by a special-purpose programming language called '''APGsembly'''. The first computational Life patterns using this technology were constructed by [[Adam P. Goucher]] in 2009 and 2010. The [[Spartan universal computer-constructor]], [[pi calculator]] and [[phi calculator]] patterns, and a related pattern programmed to grow at [[Osqrtlogt|O(sqrt(log(t)))]], had all the same basic general-purpose components that make up the GPC.

Goucher's original compiler/editor was written in DarkBasic, which became difficult to run on modern computers. In 2019 a Golly Python-script compiler was written by [[Dave Greene]] to create a Conway's Life pattern corresponding to APGsembly code, and a visual emulator and debugger was written by [[Michael Simkin]] and Dave Greene. At that time the logic circuitry was adjusted to include a standard set of components, and the resulting "GPC" was shown to be capable of supporting any of the three programs (pi, phi, or Osqrtlogt). In 2024, branoc created a version of the compiler and emulator based on the updated specifications from ''[[Conway's Game of Life: Mathematics and Construction]]'' textbook.<ref name="post199807" />

The base GPC pattern includes just the logic and memory circuitry; an additional subpattern representing an APGsembly program should be attached to a GPC to produce a complete calculator, printer, or other functional pattern. The additional subpattern is basically a finite-state machine. Each line in an APGsembly program corresponds to a state, and there are JUMP instructions for each possible return value (Z or NZ), pointing to the next state that the machine should enter. Each line of code can trigger one or more commands, or "actions", and it's important to make sure that each line includes exactly one action that returns a zero/nonzero value.

== Overview ==

The GPC includes a ticking clock in the form of two synchronized glider guns of period 2^20, 2^22 or higher, depending on what components are being used (see '''B2D''' below). These guns emit a glider each time an action has been executed with a return value of either Z or NZ, represented by a glider emitted on one of two possible output [[lane]]s, as a result of the most recent output-producing action. These actions are triggered by an input glider emitted by the calculator program pattern, sent into special computational units on specific lanes to trigger a specific action (ADD, SUB, WRITE, READ, INC, etc.) defined by the APGsembly code.

Thus the GPC has four major physical components:

# Clock.
# Program code.
# Computational unit array.
# Printer and B2D.

== The computational cycle ==

Every 2^N generations, a glider gun initiates an action based on the output from the previous cycle. The gun waits long enough that an output has most likely returned. If no output has in fact appeared (this can happen when retrieving data from a very long data tape, for example) the gun waits for another cycle and checks again, using a [[universal regulator]] mechanism.
* The return signal is always a one-bit output value, either Z or NZ.
* Each cycle is expected to return exactly one such output.

== Program code ==

APGsembly code consists of a list of actions to be performed for each ''state ID'', for each possible return value (Z or NZ). The program consists of lines of code; each state ID corresponds to two lines of code, one for Z and one for NZ.
#The program must start with INITIAL, and will halt if it ever executes HALT_OUT (or HALT) action.
#Two or more actions with Z/NZ responses for a single state are technically illegal, and will likely (though not inevitably) cause chaotic explosions in the calculator pattern.

Each line of code consists of 4 parts, separated by semicolons and optional whitespace:

'''StateID; Z/NZ; NextStateID; Action1, Action2, Action3, etc.'''

#'''StateID.''' Each line's first element is a state ID. This can be thought of as a line number, except that pairs of successive lines usually share the same state ID.
#'''Z/NZ.''' Each line's second element is either Z or NZ. Only the line matching the Z or NZ return value from the previous cycle will actually be executed.
#'''NextStateID.''' Each line's third element defines the state that will be executed on the next clock tick, if that line is executed.
#'''Action.''' Each line's fourth element defines a comma-separated list of actions to be executed. These actions are inputs to the computational units. Some actions will not return anything and only change the state of the computational unit; some will return either Z or NZ depending on the internal state of a particular unit. It is the programmer's task to make sure there is exactly one return value.

'''Example:'''

INITIAL; Z; A2; NOP
INITIAL; NZ; A2; NOP
A1; Z; A2; INC B0, NOP
A1; NZ; A2; INC B0, NOP
A2; Z; A1; SET B0, NOP
A2; NZ; A1; SET B0, NOP

This loads the B0 register with an increasing number of '1' bits. Notice that each state ID '''INITIAL''', '''A1''', and '''A2''' appears twice in the program, once for each possible Z return and once for each NZ return.

A syntactic shortcut added in the new compiler is the use of "*" to mean "both Z and NZ", and "ZZ" to mean "only Z is possible" for a given state. The above sample program could be written more compactly as

INITIAL; ZZ; A2; NOP
A1; *; A2; INC B0, NOP
A2; *; A1; SET B0, NOP

== Computational units ==

There are currently 6 types of logic units, though it is possible to add more. Each type of logic unit has one or more actions, triggered by glider inputs on specific lanes.

# ''NOP'' - The NOP action sends a Z output directly, and takes no other action.
# ''HALT'' - The HALT_OUT action halts the entire computation and emits a glider. The HALT action halts the entire computation without emitting a glider.
# ''U'' - sliding block register (holds a single integer value, stored in unary)
# ''B'' - binary string register (holds an arbitrary-length string of binary digits)
# ''ADD'' - adder
# ''SUB'' - subtractor
# ''MUL'' - multiplier
# ''B2D'' - a two-dimensional binary register.

The calculator can have an arbitrary number of U, B, ADD, SUB, and MUL units, one B2D unit, and one digit printer or character printer. Future versions of the compiler/emulator will support other components, such as an arbitrary number of fixed-width B2D units.

Before 2021, "U" was written as "R" (short for "register"), and "B2D" was written as "SQ" (short for "square"). The "T" (short for "tape") unit was an older version of the binary register, and differed in some ways from the B unit.<ref name="rename2021" />

=== U: Sliding block register ===

* Sliding block registers in APGsembly code are denoted by keywords starting with the letter U, short for "unary" -- for example, U0, U1, U2, etc.
* A sliding block register has very simple logic. It represents a single number, and all you can do with it is INC (increase by 1) and TDEC (test and decrease by 1).

'''U Actions:'''

* ''INC Ux'' will increase the register by 1. No return signal.
* ''TDEC Ux'' will decrease the register by 1. Returns NZ if the register > 0, otherwise Z.

=== B: Binary string register ===

* Binary string registers in APGsembly code are denoted by keywords starting with B, short for "binary" -- for example, B0, B1, B2, etc.
* A binary string register has a "reading head" that can be moved forward and backward along the tape with INC and TDEC, just like a sliding block register.
* A binary string register can store arbitrarily-large binary strings. A program can only retrieve one bit at a time using READ command. SET might be more clearly named "WRITE 1", but SET is the terms used in existing APGsembly.

'''B Actions'''

* ''INC Bx'' increases the position of reading head. No return signal.
* ''TDEC Bx'' decreases the position of reading head. Returns NZ unless at 0.
* ''READ Bx'' returns the state of the binary string value located at reading head and then sets it equal to 0. Returns Z if the value is 0 and NZ if 1.
* ''SET Bx'' sets the state of the current binary bit to 1 (breaks if the cell is set to 1). No return signal.

=== ADD: adder ===

One should think about the adder as having a 2-bit number. An A input just changes the state of the adder unit, whereas a B input returns the result.

* ''A0'' is not implemented as an input, because there is nothing to change.

'''ADD Actions'''
* ''ADD A1'' increments the number (modulo 4). No return signal.
* ''ADD B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.
* ''ADD B1'' increments and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

=== SUB: subtractor ===

The subtractor works same as the adder, but using 2-bit two's complement arithmetic.

'''SUB Actions'''
* ''SUB A1'' increments the number (modulo 4). No return signal.
* ''SUB B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.
* ''SUB B1'' decrements and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

=== MUL ===

MUL keeps a number between 0 and 10 in an internal register. MUL 0 divides the number by 2 (i.e., bit shifts it by 1 bit), and MUL 1 adds 10 and ''then'' divides the number by 2. The point of doing this is that performing MUL commands in succession can be used to multiply binary numbers one bit at a time, with the internal memory of the MUL component keeping track of future carry bits. This is used in the digit extraction step of the [[pi calculator|pi]] and [[phi calculator]] programs.

'''MUL Actions'''
* ''MUL 0''
* ''MUL 1''

=== B2D: 2d binary register ===

* B2D is two-dimensional binary register and is unbounded in positive X and Y directions.
* B2D can be used as memory array as well as 2d plotter.
* B2D register commands contain the string "B2D" in APGsembly code -- e.g., INC B2DX, TDEC B2DX, READ B2D, etc.
* The B2D has two arms X and Y. Each arm can be moved with INC and TDEC -- e.g., INC B2DX, TDEC B2DY.
* A program can retrieve a bit located at (X, Y) via the READ B2D command. READ B2D will always set the (X, Y) bit back to 0 (empty space). This means there is no need for a RESET B2D command, so only SET B2D is implemented.
* This B2D unit's internal circuitry operates fairly slowly. If an APGsembly program makes use of this component, a clock gun of at least period 2^22 is required.

'''B2D Actions'''
* ''INC B2DX'' increases the position of the X arm. No return signal.
* ''INC B2DY'' increases the position of the Y arm. No return signal.
* ''TDEC B2DX'' decreases the position of X arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''TDEC B2DY'' decreases the position of Y arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''READ B2D'' returns the state of the binary value located at (X, Y). Returns Z if the current state is 0 (empty), otherwise NZ.
* ''SET B2D'' sets the state at (X, Y) to 1 (breaks if the cell is set to 1). No return signal.

=== Digit printer ===

The ''digit printer'' can print "." and digits 0-9. No return signal.

'''Digit printer actions'''
* ''OUTPUT x'', for x = ., 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.

== Further details ==
* For further discussion and examples, or to ask questions, see [https://conwaylife.com/forums/viewtopic.php?f=2&t=4196 this conwaylife.com forum thread].
* [[Conway's Game of Life: Mathematics and Construction]] Chapter 9. Universal Computation
* [https://conwaylife.com/forums/viewtopic.php?p=202346#p202346 A compiler and emulator] written in Lua for use in Golly.
* [https://github.com/dvgrn/b3s23life/tree/main/calculator A compiler and debugger] for use in Golly. This is an old (1.0) version.
* [https://rei1024.github.io/apgsembly-emulator/ An emulator] that works in a web browser.

== References ==
<references>
<ref name="post199807">{{LinkForumThread
|format = ref
|p = 199807
|title = Re: Smaller Pi Calculator Challenge
|author = branoc
|date = December 14, 2024
|accessdate = June 29, 2025
}}</ref>
<ref name="rename2021">{{cite web
|url=https://github.com/rei1024/apgsembly-emulator/issues/1
|title=alternate identifier for R, T, and SQ units
|author=Dave Greene
|website=GitHub
|date=November 20, 2020
|accessdate = June 29, 2025
}}</ref>
</references>

[[Category:Everything else]]

Universal computer

2025-06-30T05:14:02Z

Rei: Archived URL

{{Glossary}}
A '''universal computer''' in a [[cellular automaton]] is a system that can compute anything that a [http://en.wikipedia.org/wiki/Turing_machine Turing machine] can compute (another term for this is '''Turing-complete'''). A cellular automaton in which such a system exists is called '''universal'''. A universal computer may be either infinite or finite, but when combined with a [[universal constructor]], it is assumed to be finite.

==Universal computers in Life==
In 1982, [[John Conway]] proved in ''[[Winning Ways]]'' that the [[Game of Life]] has a (finite) universal computer, as well as a universal constructor. Proving the universality of a cellular automaton with simple rules was in fact Conway's aim in Life right from the start. The universal computer uses [[glider]] logic and a [[sliding block memory]], and the proof of its existence is also outlined in [[The Recursive Universe]].

In April 2000, [[Paul Rendell]] constructed a direct implementation of a [[Turing machine]].<ref>{{cite web|url=http://rendell-attic.org/gol/tm.htm|title=A Turing Machine in Conway's Game of Life|author=Paul Rendell|date=April 2, 2000}}</ref> This computer is infinite, as it requires an infinite length of tape for the Turing Machine.

In 2002, using [[Dean Hickerson]]'s [[sliding block memory]], [[Paul Chapman]] constructed an implementation of a Minsky Register Machine (a machine of the same capability as a Turing Machine), which he extended to a Universal Register Machine, a finite universal computer.<ref>{{cite web|url=http://www.igblan.free-online.co.uk/igblan/ca/|title=Life Universal Computer|author=Paul Chapman|date=November 11, 2002|archiveurl=https://web.archive.org/web/20230716132432/http://www.igblan.free-online.co.uk/igblan/ca/|archivedate=July 16, 2023}}</ref>

In 2009, [[Adam P. Goucher]] built a [[Spartan universal computer-constructor]], which has three infinite binary memory tapes (program tape, data tape and marker tape). This allows data to be stored in linear space, rather than the exponential space that a Register Machine uses.

In 2010, Paul Rendell completed a [[universal Turing machine|universal version]] of his Turing machine pattern, followed in 2011 by a [[fully universal Turing machine|fully universal]] version, removing the previous requirement (needed for true universality) that the initial Life pattern must have unbounded size and infinite population.

In 2016, [[Nicolas Loizeau]] created an [[8-bit programmable computer]] pattern, using only four basic parts: a [[twogun|period-60 glider gun]], a [[buckaroo|90° glider reflector]], a p30 [[glider duplicator]], and a [[eater1|glider eater]]. Later an improved scalable version was announced in 2021.

==Universal computers in other cellular automata==
===In [[Life-like cellular automata]]===
For a universal computer to be finite, it must either be given sufficient memory for a computation prior, or employ a universal constructor. For the latter case, it must be able to escape its own bounding box and diamond, so in a non-strobing rule, its rulestring must contain at least one of the birth transitions <tt>{1,2,3}</tt>, or when [[isotropic non-totalistic]], at least one birth transition in each of the sets <tt>{1c,1e,2c,2a,3i}</tt> and <tt>{1c,1e,2e,2a,3a}</tt>, respectively, meaning there is an upper bound of <tt>2101+2100+(299+298+297)2/299=145*295</tt> INT rules with Turing-complete finite patterns on infinite planes.

For strobing rules, where <tt>~</tt> denotes the absence of a transition, these prerequisite sets are instead <tt>{~b1c,~b1e,~b2c,~b2a,~b3i,s7c,s7e,s6c,s6a,s5i}</tt> and <tt>{~b1c,~b1e,~b2e,~b2a,~b3a,s7c,s7e,s6e,s6a,s5a}</tt>.

[[David Eppstein]] and Dean Hickerson proved that {{rl|B35/S236}} has a universal computer and universal constructor, using the same method of proof that Conway used to prove that Life is universal.<ref>{{cite web|url=http://www.ics.uci.edu/~eppstein/ca/b35s236/|title=B35/S236|author=D. Eppstein}}</ref>

===In multi-state circuitry rules===
[[Tim Hutton]] has implemented [[Codd]]'s design for a universal computer in Codd's 8-state cellular automaton.<ref>{{cite web|url=https://github.com/GollyGang/ruletablerepository/wiki/CoddsDesign|title=Rule Table Repository|author=Tim Hutton}}</ref>

The well-known rule {{rl|WireWorld}} allows construction of very small and robust logic gates, triggers, memory banks etc. In September 2004 David Moore and Mark Owen released a Wireworld computer, in which the results of calculations are shown in seven-segment displays by running "electrons". The computer's instruction set is a highly orthogonal RISC architecture. The program, CPU status and data are stored in a bank of 64 16-bit registers. According to the authors, the computer was designed, with the help of many others, between 1990 and 1992. The version of it included in [[Golly]] is preprogrammed to compute and display the sequence of [[prime number]]s. Likely this was the first computer in a cellular automaton that looks like a computer from human perspective.

In 2021 [[Yoel Matveyev]] released the largest known cellular automation computer called [[Izhora]] based on his own 4-state rule FireWorld.<ref name="post136309" /> It has 256 kilobytes of memory, a {{times|256|128}} memory-mapped pixel display and a keyboard driven by a [[Golly]] script. Its 32-bit CPU uses a single operation, subtract and branch if zero or negative (SUBLEQ), from which all other operations can be synthesized. Examples include 256-bit factorials, primes and Fibonacci numbers. Tools such as an assembler and emulator are provided for programming it.

Other examples of cellular automation computers include a partial emulation of a real-world Picoblaze microcontroller and a custom multicore CPU.

==Universality of predecessor-finding==
On August 20, 2023, [[Ville Salo]] and [[Ilkka Törmä]] proved that arbitrary [[Boolean satisfiability problem]]s could be encoded to problems of finding predecessors of specific patterns, with the corollary that the process of reversing a single iteration (or otherwise proving that a pattern is a [[Garden of Eden]]) is computationally universal.<ref name="arxiv2308.10198" />

==References==
<references>
<ref name="post136309">{{LinkForumThread
|p = 136309
|format = ref
|title = Izhora (Fireworld2 computer)
|author = Yoel Matveyev
|date = October 5, 2021
}}</ref>
<ref name="arxiv2308.10198">[[Ville Salo]], [[Ilkka Törmä]], [https://arxiv.org/abs/2308.10198 ''Computing backwards with Game of Life, part 1: wires and circuits'']</ref>
</references>

==External links==
* {{LinkWikipedia|Turing_completeness|name=Turing completeness}}
* {{LinkLexicon|lex_u.htm#universalcomputer}}
* {{LinkForumThread|f=11|t=3362|title=Resources pertaining to computation in cellular automata}}

[[Category:Universal computation| ]]

APGsembly

2025-06-29T15:53:29Z

Rei: Update to APGsembly 2.0

The '''general purpose calculator''' ('''GPC''') is a way to implement computational tasks inside Conway's Game of Life. It is [[Turing complete]] and programmed by a special-purpose programming language called '''APGsembly'''. The first computational Life patterns using this technology were constructed by [[Adam P. Goucher]] in 2009 and 2010. The [[Spartan universal computer-constructor]], [[pi calculator]] and [[phi calculator]] patterns, and a related pattern programmed to grow at [[Osqrtlogt|O(sqrt(log(t)))]], had all the same basic general-purpose components that make up the GPC.

Goucher's original compiler/editor was written in DarkBasic, which became difficult to run on modern computers. In 2019 a Golly Python-script compiler was written by [[Dave Greene]] to create a Conway's Life pattern corresponding to APGsembly code, and a visual emulator and debugger was written by [[Michael Simkin]] and Dave Greene. At that time the logic circuitry was adjusted to include a standard set of components, and the resulting "GPC" was shown to be capable of supporting any of the three programs (pi, phi, or Osqrtlogt). In 2024, branoc created a version of the compiler and emulator based on the updated specifications from ''[[Conway's Game of Life: Mathematics and Construction]]'' textbook.<ref name="post199807" />

The base GPC pattern includes just the logic and memory circuitry; an additional subpattern representing an APGsembly program should be attached to a GPC to produce a complete calculator, printer, or other functional pattern. The additional subpattern is basically a finite-state machine. Each line in an APGsembly program corresponds to a state, and there are JUMP instructions for each possible return value (Z or NZ), pointing to the next state that the machine should enter. Each line of code can trigger one or more commands, or "actions", and it's important to make sure that each line includes exactly one action that returns a zero/nonzero value.

== Overview ==

The GPC includes a ticking clock in the form of two synchronized glider guns of period 2^20, 2^22 or higher, depending on what components are being used (see '''B2D''' below). These guns emit a glider each time an action has been executed with a return value of either Z or NZ, represented by a glider emitted on one of two possible output [[lane]]s, as a result of the most recent output-producing action. These actions are triggered by an input glider emitted by the calculator program pattern, sent into special computational units on specific lanes to trigger a specific action (ADD, SUB, WRITE, READ, INC, etc.) defined by the APGsembly code.

Thus the GPC has four major physical components:

# Clock.
# Program code.
# Computational unit array.
# Printer and B2D.

== The computational cycle ==

Every 2^N generations, a glider gun initiates an action based on the output from the previous cycle. The gun waits long enough that an output has most likely returned. If no output has in fact appeared (this can happen when retrieving data from a very long data tape, for example) the gun waits for another cycle and checks again, using a [[universal regulator]] mechanism.
* The return signal is always a one-bit output value, either Z or NZ.
* Each cycle is expected to return exactly one such output.

== Program code ==

APGsembly code consists of a list of actions to be performed for each ''state ID'', for each possible return value (Z or NZ). The program consists of lines of code; each state ID corresponds to two lines of code, one for Z and one for NZ.
#The program must start with INITIAL, and will halt if it ever executes HALT_OUT (or HALT) action.
#Two or more actions with Z/NZ responses for a single state are technically illegal, and will likely (though not inevitably) cause chaotic explosions in the calculator pattern.

Each line of code consists of 4 parts, separated by semicolons and optional whitespace:

'''StateID; Z/NZ; NextStateID; Action1, Action2, Action3, etc.'''

#'''StateID.''' Each line's first element is a state ID. This can be thought of as a line number, except that pairs of successive lines usually share the same state ID.
#'''Z/NZ.''' Each line's second element is either Z or NZ. Only the line matching the Z or NZ return value from the previous cycle will actually be executed.
#'''NextStateID.''' Each line's third element defines the state that will be executed on the next clock tick, if that line is executed.
#'''Action.''' Each line's fourth element defines a comma-separated list of actions to be executed. These actions are inputs to the computational units. Some actions will not return anything and only change the state of the computational unit; some will return either Z or NZ depending on the internal state of a particular unit. It is the programmer's task to make sure there is exactly one return value.

'''Example:'''

INITIAL; Z; A2; NOP
INITIAL; NZ; A2; NOP
A1; Z; A2; INC B0, NOP
A1; NZ; A2; INC B0, NOP
A2; Z; A1; SET B0, NOP
A2; NZ; A1; SET B0, NOP

This loads the B0 register with an increasing number of '1' bits. Notice that each state ID '''INITIAL''', '''A1''', and '''A2''' appears twice in the program, once for each possible Z return and once for each NZ return.

A syntactic shortcut added in the new compiler is the use of "*" to mean "both Z and NZ", and "ZZ" to mean "only Z is possible" for a given state. The above sample program could be written more compactly as

INITIAL; ZZ; A2; NOP
A1; *; A2; INC B0, NOP
A2; *; A1; SET B0, NOP

== Computational units ==

There are currently 6 types of logic units, though it is possible to add more. Each type of logic unit has one or more actions, triggered by glider inputs on specific lanes.

# ''NOP'' - The NOP action sends a Z output directly, and takes no other action.
# ''HALT'' - The HALT_OUT action halts the entire computation and emits a glider. The HALT action halts the entire computation without emitting a glider.
# ''U'' - sliding block register (holds a single integer value, stored in unary)
# ''B'' - binary string register (holds an arbitrary-length string of binary digits)
# ''ADD'' - adder
# ''SUB'' - subtractor
# ''MUL'' - multiplier
# ''B2D'' - a two-dimensional binary register.

The calculator can have an arbitrary number of U, B, ADD, SUB, and MUL units, one B2D unit, and one digit printer or character printer. Future versions of the compiler/emulator will support other components, such as an arbitrary number of fixed-width B2D units.

Before 2021, "U" was written as "R" (short for "register"), and "B2D" was written as "SQ" (short for "square"). The "T" (short for "tape") unit was an older version of the binary register, and differed in some ways from the B unit.<ref name="rename2021" />

=== U: Sliding block register ===

* Sliding block registers in APGsembly code are denoted by keywords starting with the letter U, short for "unary" -- for example, U0, U1, U2, etc.
* A sliding block register has very simple logic. It represents a single number, and all you can do with it is INC (increase by 1) and TDEC (test and decrease by 1).

'''U Actions:'''

* ''INC Ux'' will increase the register by 1. No return signal.
* ''TDEC Ux'' will decrease the register by 1. Returns NZ if the register > 0, otherwise Z.

=== B: Binary string register ===

* Binary string registers in APGsembly code are denoted by keywords starting with B, short for "binary" -- for example, B0, B1, B2, etc.
* A binary string register has a "reading head" that can be moved forward and backward along the tape with INC and TDEC, just like a sliding block register.
* A binary string register can store arbitrarily-large binary strings. A program can only retrieve one bit at a time using READ command. SET might be more clearly named "WRITE 1", but SET is the terms used in existing APGsembly.

'''B Actions'''

* ''INC Bx'' increases the position of reading head. No return signal.
* ''TDEC Bx'' decreases the position of reading head. Returns NZ unless at 0.
* ''READ Bx'' returns the state of the binary string value located at reading head and then sets it equal to 0. Returns Z if the value is 0 and NZ if 1.
* ''SET Bx'' sets the state of the current binary bit to 1 (breaks if the cell is set to 1). No return signal.

=== ADD: adder ===

One should think about the adder as having a 2-bit number. An A input just changes the state of the adder unit, whereas a B input returns the result.

* ''A0'' is not implemented as an input, because there is nothing to change.

'''ADD Actions'''
* ''ADD A1'' incrementes the number (modulo 4). No return signal.
* ''ADD B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.
* ''ADD B1'' incrementes and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

=== SUB: subtractor ===

The subtractor works same as the adder, but using 2-bit two's complement arithmetic.

'''SUB Actions'''
* ''SUB A1'' incrementes the number (modulo 4). No return signal.
* ''SUB B0'' right-shifts the number. Returns Z if the value before the action is even and NZ if odd.
* ''SUB B1'' decrements and then right-shifts the number. Returns Z if the value before the action is odd and NZ if even.

=== MUL ===

MUL keeps a number between 0 and 10 in an internal register. MUL 0 divides the number by 2 (i.e., bit shifts it by 1 bit), and MUL 1 adds 10 and ''then'' divides the number by 2. The point of doing this is that performing MUL commands in succession can be used to multiply binary numbers one bit at a time, with the internal memory of the MUL component keeping track of future carry bits. This is used in the digit extraction step of the [[pi calculator|pi]] and [[phi calculator]] programs.

'''MUL Actions'''
* ''MUL 0''
* ''MUL 1''

=== B2D: 2d binary register ===

* B2D is two-dimensional binary register and is unbounded in positive X and Y directions.
* B2D can be used as memory array as well as 2d plotter.
* B2D register commands contain the string "B2D" in APGsembly code -- e.g., INC B2DX, TDEC B2DX, READ B2D, etc.
* The B2D has two arms X and Y. Each arm can be moved with INC and TDEC -- e.g., INC B2DX, TDEC B2DY.
* A program can retrieve a bit located at (X, Y) via the READ B2D command. Unlike B where you must follow with SET or RESET, READ B2D will always set the (X, Y) bit back to 0 (empty space). This means there is no need for a RESET B2D command, so only SET B2D is implemented.
* This B2D unit's internal circuitrly operates fairly slowly. If an APGsembly program makes use of this component, a clock gun of at least period 2^22 is required.

'''B2D Actions'''
* ''INC B2DX'' increases the position of the X arm. No return signal.
* ''INC B2DY'' increases the position of the Y arm. No return signal.
* ''TDEC B2DX'' decreases the position of X arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''TDEC B2DY'' decreases the position of Y arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''READ B2D'' returns the state of the binary value located at (X, Y). Returns Z if the current state is 0 (empty), otherwise NZ.
* ''SET B2D'' sets the state at (X, Y) to 1 (breaks if the cell is set to 1). No return signal.

=== Digit printer ===

The ''digit printer'' can print "." and digits 0-9. No return signal.

'''Digit printer actions'''
* ''OUTPUT x'', for x = ., 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.

== Further details ==
* For further discussion and examples, or to ask questions, see [https://conwaylife.com/forums/viewtopic.php?f=2&t=4196 this conwaylife.com forum thread].
* [[Conway's Game of Life: Mathematics and Construction]] Chapter 9. Universal Computation
* [https://conwaylife.com/forums/viewtopic.php?p=202346#p202346 A compiler and emulator] written in Lua for use in Golly.
* [https://github.com/dvgrn/b3s23life/tree/main/calculator A compiler and debugger] for use in Golly. This is an old (1.0) version.
* [https://rei1024.github.io/apgsembly-emulator/ An emulator] that works in a web browser.

== References ==
<references>
<ref name="post199807">{{LinkForumThread
|format = ref
|p = 199807
|title = Re: Smaller Pi Calculator Challenge
|author = branoc
|date = December 14, 2024
|accessdate = June 29, 2025
}}</ref>
<ref name="rename2021">{{cite web
|url=https://github.com/rei1024/apgsembly-emulator/issues/1
|title=alternate identifier for R, T, and SQ units
|author=Dave Greene
|website=GitHub
|date=November 20, 2020
|accessdate = June 29, 2025
}}</ref>
</references>

[[Category:Everything else]]

APGsembly

2025-06-29T10:27:06Z

Rei: new URL for the web emulator

The '''general purpose calculator''' ('''GPC''') is a way to implement computational tasks inside Conway's Game of Life. It is [[Turing complete]] and programmed by a special-purpose programming language called '''APGsembly'''. The first computational Life patterns using this technology were constructed by [[Adam P. Goucher]] in 2009 and 2010. The [[Spartan universal computer-constructor]], [[pi calculator]] and [[phi calculator]] patterns, and a related pattern programmed to grow at [[Osqrtlogt|O(sqrt(log(t)))]], had all the same basic general-purpose components that make up the GPC.

Goucher's original compiler/editor was written in DarkBasic, which became difficult to run on modern computers. In 2019 a Golly Python-script compiler was written by [[Dave Greene]] to create a Conway's Life pattern corresponding to APGsembly code, and a visual emulator and debugger was written by [[Michael Simkin]] and Dave Greene. At that time the logic circuitry was adjusted to include a standard set of components, and the resulting "GPC" was shown to be capable of supporting any of the three programs (pi, phi, or Osqrtlogt).

The base GPC pattern includes just the logic and memory circuitry; an additional subpattern representing an APGsembly program should be attached to a GPC to produce a complete calculator, printer, or other functional pattern. The additional subpattern is basically a finite-state machine. Each line in an APGsembly program corresponds to a state, and there are JUMP instructions for each possible return value (Z or NZ), pointing to the next state that the machine should enter. Each line of code can trigger one or more commands, or "actions", and it's important to make sure that each line includes exactly one action that returns a zero/nonzero value.

== Overview ==

The GPC includes a ticking clock in the form of two synchronized glider guns of period 2^20, 2^22 or higher, depending on what components are being used (see '''SQ''' below). These guns emit a glider each time an action has been executed with a return value of either Z or NZ, represented by a glider emitted on one of two possible output [[lane]]s, as a result of the most recent output-producing action. These actions are triggered by an input glider emitted by the calculator program pattern, sent into special computational units on specific lanes to trigger a specific action (ADD, SUB, WRITE, READ, INC, etc.) defined by the APGsembly code.

Thus the GPC has four major physical components:

# Clock.
# Program code.
# Computational unit array.
# Printer and SQ

== The computational cycle ==

Every 2^N generations, a glider gun initiates an action based on the output from the previous cycle. The gun waits long enough that an output has most likely returned. If no output has in fact appeared (this can happen when retrieving data from a very long data tape, for example) the gun waits for another cycle and checks again, using a [[universal regulator]] mechanism.
* The return signal is always a one-bit output value, either Z or NZ.
* Each cycle is expected to return exactly one such output.

== Program code ==

APGsembly code consists of a list of actions to be performed for each ''state ID'', for each possible return value (Z or NZ). The program consists of lines of code; each state ID corresponds to two lines of code, one for Z and one for NZ.
#The program must start with INITIAL, and will halt if it ever reaches a state where none of the actions return a Z/NZ response.
#If the program is written according the usual rules (i.e. a single return signal per line), it will run indefinitely.
#Two or more actions with Z/NZ responses for a single state are technically illegal, and will likely (though not inevitably) cause chaotic explosions in the calculator pattern.

Each line of code consists of 4 parts, separated by semicolons and optional whitespace:

'''StateID; Z/NZ; NextStateID; Op1, Op2, Op3, etc.'''

#'''StateID.''' Each line's first element is a state ID. This can be thought of as a line number, except that pairs of successive lines usually share the same state ID.
#'''Z/NZ.''' Each line's second element is either Z or NZ. Only the line matching the Z or NZ return value from the previous cycle will actually be executed.
#'''NextStateID''' Each line's third element defines the state that will be executed on the next clock tick, if that line is executed.
#'''Op.''' Each line's fourth element defines a comma-separated list of operations, or "actions", to be executed. These actions are inputs to the computational units. Some actions will not return anything and only change the state of the computational unit; some will return either Z or NZ depending on the internal state of a particular unit. It is the programmer's task to make sure there is exactly one return value.

'''Example:'''

INITIAL; Z; A2; NOP
INITIAL; NZ; A2; NOP
A1; Z; A2; INC T0
A1; NZ; A2; INC T0
A2; Z; A1; READ T0, SET T0
A2; NZ; A1; READ T0, SET T0

This loads the T0 register with an increasing number of '1' bits. Notice that each state ID '''INITIAL''', '''A1''', and '''A2''' appears twice in the program, once for each possible Z return and once for each NZ return.

A syntactic shortcut added in the new compiler is the use of "*" to mean "both Z and NZ", and "ZZ" to mean "only Z is possible" for a given state. The above sample program could be written more compactly as

INITIAL; ZZ; A2; NOP
A1; *; A2; INC T0
A2; *; A1; READ T0, SET T0

== Computational units ==

There are currently 6 types of logic units, though it is possible to add more. Each type of logic unit has one or more actions, triggered by glider inputs on specific lanes.

# ''NOP'' - The NOP action sends a Z output directly, and takes no other action.
# ''R'' - sliding block register (holds a single integer value, stored in unary)
# ''T'' - binary string register (holds an arbitrary-length string of binary digits)
# ''ADD'' - adder
# ''SUB'' - subtractor
# ''MUL'' - ... we're not sure how to use this, but it shows up in the pi and phi calculator code, apparently as a binary-to-decimal converter.
# ''SQ'' - a two-dimensional (''square'') array of data.

The calculator can have an arbitrary number of R, T, ADD, SUB, and MUL units, one SQ unit, and one digit printer or character printer. Future versions of the compiler/emulator will support other components, such as an arbitrary number of fixed-width SQ units.

===R: Sliding block===

* Sliding block registers in APGsembly code are denoted by keywords starting with the letter R, short for "register" -- for example, R0, R1, R2, etc.
* A sliding block register has very simple logic. It represents a single number, and all you can do with it is INC (increase by 1) and TDEC (test and decrease by 1).

'''R Actions:'''

* ''INC Rx'' will increase the register by 1. No return signal.
* ''TDEC Rx'' will decrease the register by 1. Returns NZ if the register > 0, otherwise Z.

===T: Binary string register===

* Binary string registers in APGsembly code are denoted by keywords starting with T, short for "tape" -- for example, T0, T1, T2, etc.
* A binary string register has a "reading head" that can be moved forward and backward along the tape with INC and DEC, just like a sliding block register.
* A binary string register can store arbitrarily-large binary strings. A program can only retrieve one bit at a time using READ command, followed by SET or RESET actions. SET and RESET might be more clearly named "WRITE 1" and "WRITE 0", but SET and RESET are the terms used in existing APGsembly.

'''T Actions'''

* ''INC Tx'' increases the position of reading head. Returns Z unless the space is empty then it returns NZ.
* ''DEC Tx'' decreases the position of reading head. Returns NZ unless at 0.
* ''READ Tx'' return the state of the binary string value located at reading head. Returns Z if the value is 0 and NZ if 1.
* ''SET Tx'' sets the state of the current binary bit to 1. Must be after READ action which removes the previous state. No return signal.
* ''RESET Tx'' sets the state of the current binary bit to 0. Must be after READ action which removes the previous state. No return signal.

===ADD: adder===

One should think about the adder as having two bits, A and B. Each of them can be either 0 or 1, and each of these options is an input to the adder. An A input just changes the state of the adder unit, whereas a B input returns the result.

* ''A0'' is not implemented as an input, because there is nothing to change.
* ''A1'' is a valid input
* ''B0'', ''B1'' should come after A is initialized.
* The adder returns (Ax + By + Memory) % 2
* The adder stores Memory = (Ax + By + Prev Memory >= 2)
* The "carry" memory bit is stored in the unit until the next use of the adder.
* If you are not sure about the state of the adder, just send B0 and you can be sure the memory is cleared.

'''ADD Actions'''
* ''ADD A1''
* ''ADD B0''
* ''ADD B1''

===SUB: subtractor===

The subtractor works exactly the same as the adder, except for subtracting two numbers bit by bit, keeping in internal memory a 0 or 1 "carry" value.

'''SUB Actions'''
* ''SUB A1''
* ''SUB B0''
* ''SUB B1''

===MUL===

MUL keeps a number between 0 and 10 in an internal register. MUL 0 divides the number by 2 (i.e., bit shifts it by 1 bit), and MUL 1 adds 10 and ''then'' divides the number by 2. The point of doing this is that performing MUL commands in succession can be used to multiply binary numbers one bit at a time, with the internal memory of the MUL component keeping track of future carry bits. This is used in the digit extraction step of the [[pi calculator|pi]] and [[phi calculator]] programs.

'''MUL Actions'''
* ''MUL 0''
* ''MUL 1''

===SQ: 2d binary register ===

* SQ is two-dimensional binary register and is unbounded in positive X and Y directions.
* SQ can be used as memory array as well as 2d plotter.
* SQ register commands contain the string "SQ" in APGsembly code -- e.g., INC SQ, DEC SQ, READ SQ, etc.
* The SQ has two arms X and Y. Each arm can be moved with INC and DEC -- e.g., INC SQX, DEC SQY.
* A program can retrieve a bit located at (X, Y) via the READ SQ command. Unlike T where you must follow with SET or RESET, READ SQ will always set the (X, Y) bit back to 0 (empty space). This means there is no need for a RESET SQ command, so only SET SQ is implemented.
* This SQ unit's internal circuitrly operates fairly slowly. If an APGsembly program makes use of this component, a clock gun of at least period 2^22 is required.

'''SQ Actions'''
* ''INC SQX'' increases the position of the X arm. No return signal.
* ''INC SQY'' increases the position of the Y arm. No return signal.
* ''DEC SQX'' decreases the position of X arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''DEC SQY'' decreases the position of Y arm, or if it's at 0 already, keeps it there. Returns Z if already at 0, otherwise NZ.
* ''READ SQ'' returns the state of the binary value located at (X, Y). Returns Z if the current state is 0 (empty), otherwise NZ.
* ''SET SQ'' sets the state at (X, Y) to 1 (breaks if the cell is set to 1). No return signal.

===Digit printer===

The ''digit printer'' can print "." and digits 0-9. No return signal.

'''Digit printer actions'''
* ''OUTPUT x'', for x = ., 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.

== Further details ==

* For further discussion and examples, or to ask questions, see [https://conwaylife.com/forums/viewtopic.php?f=2&t=4196 this conwaylife.com forum thread].
* [https://github.com/dvgrn/b3s23life/tree/main/calculator A compiler and debugger] for use in Golly.
* [https://rei1024.github.io/apgsembly-emulator/ An emulator] that works in a web browser.

[[Category:Everything else]]