Automata

An illustration for this article

This is a list of Automata designed by Cat's Eye Technologies, listed in chronological order. For more information on these Automata, see below.

The distinction between an Automaton and a Language or a Gewgaw is not always cut-and-dried, so if you can't find what you're looking for here, try those lists as well.

SMETANA

Try it online Browse files Download

Sample configuration:

Step 1. Swap step 1 with step 2.
Step 2. Go to step 2.
Step 3. Go to step 1.

SMETANA is a pathological little self-modifying language with only two possible operations: Go to step n, and Swap steps n and m. It has inspired a few variants and developments, notably a proof that despite its minimalism, it is finite-automata-complete; it is also the (great-?)grandfather of SMITH.

Reference Implementation: smetana.pl

Implementation: SMETANA (Visual Basic)

Implementation: tc.catseye.yoob.smetana

Cyclobots

Try it online Browse files Download
preview

Cyclobots is an automaton that consists of a number of little virtual "turtle robots" called "cyclobots". Each cyclobot moves with a constant velocity, and tries to follow exactly one other cyclobot, adjusting its heading to point towards the cyclobot it is following. No cyclobot is followed by more than one cyclobot.

A group of cyclobots tends to fall into one of several semi-stable patterns. The simplest of these is just a rotating circle, but more complex, trefoil-like patterns are common.

I originally conceived of this automaton, calling it an "interactive desktop toy", in 1994, and implemented it immediately in Visual Basic. I remember the year because I wrote the first implementation of SMETANA in Visual Basic at about the same time.

The original implementation had a few features which are not present (yet) in the HTML5 version: cyclobots could collide with each other, and the user could use the mouse to attract/repel them from a chosen point.

Reference Implementation: cyclobots.js

Implementation: Cyclobots (Visual Basic)

RUBE

Try it online Browse files Download

Sample configuration:

  0a21646c726f77202c6f6c6c6548
, :::::::::::::::::::::::::::: ,
 )
 ==============================
F
                               O F
                               c
                               =

RUBE is an esoteric programming language in tribute to Rube Goldberg, with bulldozers pushing around numbered crates, knocking them together to perform computations. It is based on a variant of a cellular automaton called a bully automaton, where certain state changes can force other state changes to occur elsewhere in the playfield.

Reference Implementation: rube.c

REDGREEN

Try it online Browse files Download

Sample configuration:

                   # #
 ......            # #
                   #  ~                      #
                   #######################   #
                  %#                         #
       . . .      T #####                    #
                  ###   #  :                 #
                        #                    #
                        #  .                 #
                        #                    #
                        #                    #
                        #  .                 #
                        #                    #
                        #                    #
#<<<<<<<<<<<<<<<<<############################
                                %
                                T

REDGREEN is a cellular automaton that simulates a little "physical world", much like RUBE.

Reference Implementation: redgreen.alp

noit o' mnain worb

Try it online Browse files Download
screenshot

Sample configuration:

#####         #####
#   ###########   #
# . >         < . #
#   #####v#####   #
#####   #  ########
        #       >!#
        #v#########
        # #
        ###

noit o' mnain worb is a probabilistic particle automaton that uses pressure between randomly moving particles to approximate the behaviour of circuits. It can approximate computation with these circuits, too, but it's so lossy that it has more value as just a neat toy to watch.

(The name of this language contains a secret message! Can you find it?)

Reference Implementation: worb.pl

Implementation: worb.js

Implementation: tc.catseye.yoob.worb

Circute

Try it online Browse files Download
screenshot

Sample configuration:

                 =
                 =
  #######==   ===N===   =========
  #       =   =     =   =       =
==N==     = ==N== ==N== =     ==N==
=   =     = =   = =   = =     =   =
=====     = ===== ===== =     =====
  =       =   =     =   =       =
  =============     =============

Circute is a cellular automaton that simulates conduits that carry digital signals and NAND gates that manipulate those signals.

Reference Implementation: circute.alp

Implementation: tc.catseye.yoob.circute

Braktif

Try it online Browse files Download

Sample configuration:

                            *
                       <<*[--]*
000000000000000000  *[-----  --]
-----------------d-i--         --------

Braktif is a cellular automaton modelled closely after the brainfuck programming language.

Reference Implementation: braktif.alp

Xigxag

Try it online Browse files Download

Sample configuration:

><<

Sample result:

><<
<<>><
<><<<<>>
<<<<>><><><<><<<><<<>

Xigxag is a simple string-copying automaton that has exponential growth almost everywhere (i.e. there are only a finite number of initial configurations that don't blow up.)

Reference Implementation: xigxag.pl

Didigm

Browse files Download

Sample configuration:

3333333333333
3002300230073
3111311132113
3311321131573
3111311131333
3333333333333
=F3
,
=F1
111111111111111
111111131111111
111111111111574
111111111111333
311111111111023
111111111111113

Didigm is a reflective cellular automaton: the transition rules for the automaton are defined by forms in the very playfield governed by those transition rules.

Jaccia

Try it online Browse files Download

Sample configuration:

#######S###
#:::::::::#
#:###:###:#
#:#:#:::#:#
#:#:#:#:###
#:::#:#:#:#
#####:#:#:#
#:#:::#:::#
#:#:###:###
#:::#:::::#
#########F#

Sample result:

#######S###
#    :::  #
# ###:### #
# # #:::# #
# # # #:###
#   # #:# #
##### #:# #
# #   #:  #
# # ###:###
#   #  :::#
#########F#

Jaccia and Jacciata are cellular automata inspired by the Announcement of Scientific Proof that Slime Molds are Intelligent Maze Solvers. Jaccia can solve mazes too, by a similar mechanism (shrinking). Jacciata builds upon this to find the shortest path through a maze, if one exists and is unique.

Reference Implementation: jaccia.alp

Jacciata

Try it online

Jacciata is a variant of Jaccia which finds the shortest path.

Chzrxl

Try it online Browse files Download
preview

"Chzrxl, the Living Inkblot." Or is it a sort of self-attracting lava lamp?

Reference Implementation: chzrxl.js

Backtracking Wang Tiler

Try it online Browse files Download
screenshot

This backtracking Wang tiler is an automaton which naïvely tiles the plane with Wang tiles.

It operates like a backtracking algorithm, backing up whenever it finds it cannot place a tile, but it may be inaccurate to describe it as an algorithm, since it never terminates.

Implementation: backtracking-wang-tiler.js

Schrödinger's Game of Life

Try it online Browse files Download
screenshot

Schrödinger's Game of Life is what happens when Conway's Game of Life meets Schrödinger's Cat: each individual cell may be Alive, or Dead, or Possibly-Alive-Possibly-Dead (which we call Cat.)

This is, in essence, the result of applying non-determinism to an existing cellular automaton, and this operation could probably be applied to any cellular automaton with similar results.

For a full account of its development, see its README document.

Reference Implementation: slife

Implementation: slife.js

About these Automata

We should say a few words about these automata here.