Automata

Automata

Unfortunately the distinction between an Automaton and a Language or a Gewgaw is not always cut-and-dried so you might want to see those articles as well.

SMETANA

Sample program:

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

preview

Also

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 cylobot 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 more common.

I originally conceived of this automaton, calling it an "interactive desktop toy", in or around 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 (Visual Basic)

Implementation: cyclobots.js

RUBE

Sample program:

  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

Sample program:

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

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

Reference Implementation: redgreen.alp

noit o' mnain worb

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

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

Sample configuration:

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

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

Reference Implementation: braktif.alp

Xigxag

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

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

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

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

Chzrxl

preview

Also

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

Reference Implementation: chzrxl.js

Backtracking Wang Tiler

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

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