Browsed by
Month: May 2016

Standardization

Standardization

As I have mentioned in previous posts, it is important for all of the basic building blocks to have similar sizes and delays, so that they are compatible in larger circuits.  The next level of abstraction is that of tiles, which each tile representing a single wire or gate.  By holding ourselves to strict requirements for the underlying gates, we will be able to run our simulations in terms of tiles, without needing to simulate the underlying metapixels.  I’ve said a few things about bounding boxes and delays, but now is time to get a lot more specific.

The Standard

We have settled on 11×11 metapixel components.  The figure below show the typical layout of a single gate.  The top and left sides are input, and the right side is output.  The red box is 11×11 (inclusive), and the red itself denotes cells that cannot be occupied by the gate.  This is to provide the necessary 1-cell-wide padding to prevent interference between components.  The output side is the only side that doesn’t need buffering, since buffering is provided by the input side of the adjacent component.   The blue and green cells denote the mandatory wire buffers.

typical unit bounding box

Every logic gate in the previous post can fit into a bounding box like this, and so can many of the wire components (the others won’t be used individually).

As far as timing is concerned, the distance between signals will be a multiple of 11 (often 22 for data), so a gate should be able to receive electrons every 11 ticks, and give the output exactly 11 ticks later.  The only exceptions are the 22:11 and 33:11 delay wire units, which of course delay their output to a different multiple of 11.

When testing a new gate, it is important to include a length of wire on every side so that you can actually see if any erroneous/malformed electrons are produced.

Time-Keeping Components

The two main types of timing components (clocks and delay wires) must be special-built for 11-cell-based technology.  Delay wires will be used to increase the delay between two components without having to increase the travel distance between them.  Especially important is a 22:11 delay, which solves the checkerboard parity problem (moving an odd Manhattan distance in an even number of ticks).  Clocks are used to synchronize the circuits and to create inverted gates.  Ultimately, a couple large clocks will likely control the computer.  Here are some delay wire units ( which were also previously featured on the “Building Blocks: Wires” post) and some small clocks:

22:11 delay wire
33:11 delay wire
11-tick clock
22-tick clock
33-tick clock

Multi-tile Components

Sometimes, components don’t fit into a single tile, but rather occupies the space of a group of tiles.  There are typically two causes of this:

  1. An 11×11 square is sometimes simply not enough space, and it’s not something that can be made with two separate tiles next to each other.  We did consider larger tile sizes for our standard, like 16×16, but changing 11×11 to 16×16 would double the total area of the rest of the computer and dramatically increase the amount of empty space.
  2. The given component can be made using existing components, but can be made significantly smaller by compacting its sub-components together.  An example of this is the serial binary adder, which will be the subject of a future post.

In these cases, the component can be considered a “multi-tile” component, which fits neatly into a 11-wide grid but which can’t be divided into independent 11×11 squares.  The multi-tile component will be treated as a single unit during simulation, without needing to simulate the different sub-components.  Below is an example of a 33-clock in the form of a 2×1 multi-tile.

33-clock, a multi-tile component. It is actually period-66 (too long for the GIF creator), and can be converted to a 66-clock.

The timing of multi-tile components is more complicated, since their delays are influenced by their size and complexity.  They should be able to receive input and give output every N*11 generations, for some integer N.  The delay between input and output should be a multiple of 11 as well.  A multi-tile component is considered “lagless” if the delay between input and output equals the distance between them.  A component is “linear” if the input is aligned (either horizontally or vertically) with the output, so that the signal travels in a straight line.

Tile-Based Circuit Simulator

Conor is currently working on a tile-based circuit simulator, which will served as the next (and possibly final) platform for circuit design.  His software will be able to simulate tile and multi-tile components without needing to worry about the underlying metapixel structure, allowing for easier development of complex circuits.

Building Blocks: Logic Gates

Building Blocks: Logic Gates

The second class of building blocks is where things get interesting: logic gates.   In real-life digital design, the gates you would typically encounter are as follows:

  • AND
  • OR
  • NOT
  • NAND
  • NOR
  • XOR
  • XNOR

With the exception of NOT (which has a single input), all of the gates listed above have two inputs and one output. Furthermore, they are symmetrical: swapping the order of inputs has no effect.  Unfortunately, only a portion of these gates are available for use in our computer. The main issue we run into is that it is impossible for a gate to create electrons from nothing. This means that any gate with all zeroes input must give a zero output, immediately eliminating the possibility of NOT, NAND, NOR, and XNOR gates.  To be more precise, those gates would require a clock as input to make sure that the outputs have the correct timing. For example, a NOT gate would be an XOR hooked up to a clock.  At that point, however, we are no longer dealing with the basic building blocks.

There is some good news though.  One gate left off the above list is the AND-NOT gate, which outputs true iff the first input is true and the second input is false.  Unlike the gates above, this is an asymmetrical gate.  Since it returns false when both inputs are false, we are able to build it as a core gate.  This gate will help reduce our need for inverters.

Configuration is Key

There’s not much that isn’t important when designing logic gates.  In order for a logic gate to be useful, it has to fit with the wires that we chose.  Since we are arranging everything rectilinearly, each logic gate has four sides, two of which are input, and one or two of which are output.  This gives rise to multiple distinct configurations of each gate.  For an example, one version of a gate could take input from the left and right, while another version could take input from the left and top.  These gates are distinct because there’s no sequence of rotations/reflections that transforms one to the other.  We must individually, and explicitly, construct each distinct gate configuration.  For symmetrical gates, there are 4 configurations, and for asymmetrical gates, there are 5.

Having a wide palette of gates is very important, since not having the right gate generally results in additional wiring or additional gates, which slows down the circuit, which means that other parts of the circuit (or computer) must be adjusted as to keep the timing in sync.

There is an important additional restriction on shape, which is that they fit into a square bounding box (of arbitrary size) with the input/output wires centered on each side.  This helps the gate fit into the grid system and means they may be rotated/reflected and still fit properly without affecting timing.

Timing is Key

In order for a given logic gate to be compatible with our wiring system, they must follow an important timing principle:

The time between input and output is given by the Manhattan distance between input and output, not by the type of gate or what the input/output values are.  If the logic gate were replaced by a straight or corner wire, the delay must be identical.

This rule is what ensures that the logic gates are compatible with each other, and that the next layer of abstraction (detailed in a later post) actually works.  Several gates have been discovered that are completely unusable because of timing issues.  In those cases, it is generally possible to correct the timing issue by simply bending some of the surrounding wires, but that generally adds to the size of the gate.


 

List of “Core” Logic Gates

Here is a (to-be-completed) comprehensive list of the known logic gates.  Some of the animation needs to be updated to VarLife quality.  The VarLife animations are also hyperlinked to an example implementation.  In some images, a red bounding box (11×11, inclusive) is displayed, although that same bounding box can fit (centered) over any other gate here.

AND gate

All of the possible AND gates are known.

opposing inputs, single output
adjacent input, single output
adjacent input, two outputs
Opposing inputs, two outputs.

XOR gate

The situation for XOR gates is similar.  Missing is opposing input with two outputs.

opposing inputs, single output
Adjacent input, single output. The double-output version is constructed similarly to the double-output AND gate.

OR gate

The OR gate typically uses the B12/S1 cell type.  It has, however, a second version of the adjacent-input configurations which is more compact.  The larger version is often used, simply for consistency.  It is likewise missing the opposing-inputs double-output version.

opposing inputs, single output
Adjacent inputs, first version. A second output can easily be connected.
Adjacent inputs, version two, which is 3 cells narrower. The transformation to double-output is as simple as connecting the second wire.

AND-NOT gate

The AND-NOT gate is asymmetrical, so there’s five possible configurations  So far, two have been found:

  1. Adjacent inputs, single output, with input A across from the output.
  2. Opposing inputs, single output.
  3. Adjacent inputs, single output, with input B across from the output.
  4. Adjacent inputs, two outputs

Missing is the following:

  1. Opposing inputs, two outputs
adjacent inputs, single output, with input A across from the output
Adjacent input, double output. This is one of the largest gates.
adjacent input, single output, with input B across from the output. The more compact output means that it can’t be turned into a double-output gate.
opposing inputs, single output

What about those missing gates?

As you may have noticed, a couple theoretical gate configurations are missing.  This is generally due to a lack of effort: a serious need for many of the double-output gates hasn’t arisen yet, so not much time has been spent searching for them.  On the other hand, I do not believe that the double-output gates will be simple.  If you find a missing gate, or a more compact version of an existing gate, please contact us.  If it is compatible with our project, I will add it to this list.

Building Blocks: Wires

Building Blocks: Wires

Our vision for the GoL computer is one similar to real computers.  That is, it’s built from logic gates, has memory, adders, clocks, etc., and is programmed in a format comparable to real assembly language.  Just like regular computers, we have to start from the basics: wires and logic gates.  The first task is to find implementations of those simple components in metapixels.

The order in which I present the various building blocks is a combination of discovery order,  relevance, and complexity.

Wire

There’s actually a couple different options as far as wire goes.  You can see some options in this simulation.

some wires and a clock

We chose the 3-wide wire, with electron tails 2 blocks behind, which is shown on the top row.  There are some other variations on electron which are shown in the second row.  The third row shows a type of  2-wide wire (discovered later) which has some inherit side-to-side flexibility.  This 2-wide wire ends up being useful only as a single “module” within a larger wire, to help squeeze around an obstacle.  The 3-wide wire is superior, in my opinion, because it is uniform (can take on any length) and handles 90 degree turns better.  The electron as shown in the first row is the kind that arises most naturally in various circuits, such as the clock at the bottom.  Care must be taken, however, to ensure that the tails are properly formed, since several logic gates malfunction if the tails are incorrect.  Furthermore, a sporadic signal in the wire can end up reverberating to both ends.

There are probably other potential designs for a wire, using other metapixel rules or other arrangements, but I believe the B1/S and B2/S combination is one of the most useful.   For comparison, wireworld electrons are B12/S (but have a third “dying” state).

Corners

I made some mention of corners in the last post, but here are some more variations:

Three types of corner. Each corner has identical delay.

The best kind of corner is one whose delay we can ignore, meaning that we do not have to count the number of corners to calculate the time it takes for a signal to travel down a long wire.  Each corner above follows the correct Manhattan-distance-based timing, so they will all be compatible with each other and with any other circuits that obey Manhattan distance (which is not a give-in with a Moore neighborhood).

  1. The most common corner used in our designs is the one in the top-left and bottom-right of the animation.
  2. The corner in the top-right has the advantage of being narrower on one side, but is likewise wider on the others.
  3. The corner in the bottom left is the widest, which can be both an advantage and disadvantage.

Wire Splits

One important rule to keep in mind is that “something cannot be created from nothing,” when it comes to our CA, at least.  The only way to generate an electron is if we already had one.  The only way to increase our total electron count is through wire splitters.

The corners listed above can be converted into wire splitters, quite conveniently actually.   The first corner can be transformed into a 2-way wire split (turning left and right).  The second can be transformed to a 2-way turn-or-go-straight split.  The third one can be converted into any kind of 2- or 3-way split.

4 of the 5 most common splits. Missing is the third configuration of the bottom two splits. Note the slight but important modification to the top-right split.

Wire Crossing

Wire crossings allow signals to pass directly through each other.  Since we are limited to a 2D world, a compact wire crossing is one of the most important building blocks.  The discovery of the wire crossing actually came after a couple of the more simple logic gates.  After the team did a decent amount of trial-and-error, El’endia found the wire crossing below.  He introduced the B12/S1 rule, shown in red, as the fourth (and currently last) type of metapixel in our project.

First-discovered wire crossing.

I figured out a slightly more compact version, but so far I’ve never actually used it in bigger circuits:

Slightly more compact, but probably has no real advantage.

There is also a parallel wire crossing.  After one notable almost-correct attempt, it turns out I only needed to make a minor modification.  El’endia gets credit for this design.

Parallel wire crossing.

Rarely in actual circuitry are parallel wires this close together, so the circuit will probably involve diagonal wiring to bring them together.

Diagonal Wire

Diagonal wire is wire that shifts to the side as it travels forward,  which enables the wire to cut corners if need be.

Diangonal wiring.

Or, less practically (requiring larger distances between electrons and dependent on the exact distance):

Small diagonal wiring.

Delay Wire

Also of importance is delay wire, which is wire that slows down the passage of electrons.  Delay wire is classified by its length and delay (how long it is versus how long electrons take to flow through it).  The only useful generic delay wire I’m currently aware of is this 4:3 wire by El’endia:

4:3 delay wire

I have built some delay wire modules of the sizes 22:11 and 33:11 for our project.  The use-cases and reasoning behind those sizes will be explained later.

22:11 delay wire
33:11 delay wire
Intro to Metapixels

Intro to Metapixels

The core of Conway’s Game of Life is the cell, which can either be live or dead.  Or rather, a grid of such cells with unbounded size.  The simulation is run in generations, similar to “ticks” in video games.  The state of the simulation during a particular generation is derived from the state of the previous generation, following simple rules.  If a dead cell is surrounded by exactly three live neighbors (out of 8 total), then it is born.  If a live cell is surrounded by either two or three live neighbors, it survives.  Otherwise, the cell dies.  Using some simple notation, this rule is known as B3/S23.  Despite these simple rules, very intricate patterns can be made.

Gosper’s Glider Gun (source: Wikipedia)

So far, I’ve never created anything interesting in the basic rules describe above.  There are many limitations to work around, since even though there’s lots of “parts” to build with, there’s no guarantee that the parts will fit together in any simple/convenient way.  When building a computer, which involves many complex parts, the keys are regularity, predictability, controllability.  It would be very convenient if there were a way to dictate exactly which cells are allowed to do what, and instead design the rules to fit your pattern instead of designing patterns based on the rule.  Except… there is.

Enter the Metapixel

The OTCA metapixel is a large (2048×2048) construction which allows for the emulation of any “life-like” rules.  That is, any rule of the form B[0-8]*/S[0-8]*.  The most common use is emulation of B3/S23, which is meta-life.

A pattern in meta-life. (Source: conwaylife.com)

The suggestion of using metapixels in the project originally came from the challenge author, although he did not specify anything more than that they may be useful.  Several months ago (I don’t know the time scale exactly), I had a realization: the grid of metapixels can be programmed independently.  This fact, which I verified using Golly, was big news.   By having a grid of mostly background (B/S) cells, other cell types can be arranged form wires, much like how wireworld has copper wires on a black background.

Unfortunately, there’s no simple way to create an “electron” (a pulse along a wire) with only two types of cells (background and wire) and two states (live or dead).  Wireworld uses a 3-state cell for its wire, which provides both a “head” and “tail” that gives the electron direction.  For our project, we could either construct a complex spaceship to serve as our electron, or use an additional type of cell.  I chose to use a third type of cell.

Below is an animation (my first, created in MS Paint), of an electron flowing in a wire and going around a corner.  The grey cells are B/S, the blue cells are B1/S, and the green cells are B2/S.  The live blue cell serves as the electron head, and the green live cells are the tails.  Each cell, of course, represents a single metapixel, which is actually 2048×2048 real GoL cells.  Each generation in this animation represents 35328 real GoL generations.

Electron flowing around a corner.

You can play with an electron in some wire with this Variations of Life simulation.   An important thing to note is the speed of travel: one cell per generation (also known as c, the “speed of light” in CAs).  Even though there appears to be a gap in the wire, the timing is correct: the number of generations matches the Manhattan distance (our preferred measure of distance, so that the time it takes for a signal to travel depends less on the exact path used).

More information on wires and other simple components will be in the next post.

The Quest for Tetris

The Quest for Tetris

Just under 3 years ago, a codegolf.SE user created this challenge:

Build a working game of Tetris in Conway’s Game of Life

As of writing, this challenge is the most upvoted unanswered question on the site, by a large margin.  Some users have predicted that the challenge will never be answered.  I say, this will not be due to a lack of trying.  I am currently involved in a large, serious, and very promising attempt to build a programmable computer in GoL.  This is… the Quest for Tetris.


The Team

As of writing, there are three core developers working on this project, although there have been several additional users participating in the dedicated chat room.

  • PhiNotPi (me) – I consider myself the “project leader.”  I’ve probably done the plurality of physical logic gate/circuit design and construction, although little actual programming.  I was the initiator of this solving attempt.
  • El’endia Starman – He created Variations of Life, the mixed-rule CA simulator that has been the “base of operations” for most of our work so far.  He has also discovered several logic gates.
  • Cᴏɴᴏʀ O’Bʀɪᴇɴ – He is currently programming the tile-based circuit simulator, on which we will develop most of the more complex logic circuits of the computer.

Prior Work

We stand on the shoulders of giants.  There are two main sources from which we are basing our computer design:

  • The OTCA metapixel was created by Brice Due in 2006.  It is a square-shaped GoL construction that is capable of emulating any life-like rule (that is, 2-state Moore-neighborhood outer totalistic rule).  The details of its inner workings are beyond the scope of this project, but the ability to program cells independently of their neighbors is the key to this project.
  • The wireworld computer was built by David Moore and Mark Owen in 1992.  It is (as far as I’m aware), the only CA-based computer of similar complexity and usability.  We intend on using several similar methods in the construction of our computer.  His website describes several parts of the computer, but unfortunately lacks the thoroughness I would prefer (and which I will attempt to provide in this series of blog posts).

Our Approach

We are building our computer on several layers of abstraction.

  1. The Game of Life is the lowest level, of course.
  2. Next is the OTCA metapixel, which is used to emulate a larger grid of cells.  These cells can contain a variety of rules.  We are using the rules B/S (for background), B1/S, B2/S, and B12/S1.
  3. By stringing certain types of metapixels together, we can create wires, down which signals can flow (in the form of “highly controlled spaceships”).  We can also create logic gates that take signals as input and give other signals as output.  All of the basic logic units will be of comparable size and delay, allowing further abstraction.
  4. Logic gates can be arranged to build logic circuits, like adders, multiplexers, memory cells, etc.
  5. These circuits can be combined to form a functional, although basic, computer.
  6. The computer can be programmed to have Tetris.

These steps will be broken down into more detail in additional blog posts.


Current Status

We have finished the majority of logic gate discovery, and are now working on building larger circuits.  Some of our work will still be done with hand-crafting compact circuits, but eventually our circuit design work will be tile-based, without needing to simulate the underlying circuitry.  Our current bottleneck is the programming of this tile-based circuit simulator.

Hello world!

Hello world!

Welcome to WordPress. This is your first post. Edit or delete it, then start writing!

Today I bought my own domain, phinotpi.com.   I chose the “.com” TLD simply because it’s typically considered the most popular, and I decided to take it while it was still available.  I’m hosting this blog with OpenShift, a PaaS by RedHat (currently for free).

I don’t really have any big plans for this blog, but most of it will probably deal with PPCG and related shenanigans.

www.000webhost.com