git @ Cat's Eye Technologies Chrysoberyl / master article / Automata.md
master

Tree @master (Download .tar.gz)

Automata.md @master — view markup · raw · history · blame

Automata

  • image_url: https://static.catseye.tc/images/illustrations/Perpetual_Motion_Machine.jpg

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

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

  • license: Public Domain
  • implementation-type: interpreter
  • host-language: Perl

Implementation: SMETANA (Visual Basic)

  • license: Freely Redistributable
  • implementation-type: interpreter
  • host-language: Visual Basic

Implementation: tc.catseye.yoob.smetana

  • license: Public Domain
  • implementation-type: interpreter
  • host-language: Java
  • host-platform: yoob

Cyclobots

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

  • license: Public Domain
  • host-language: Javascript
  • host-platform: HTML5
  • development-stage: mature

Implementation: Cyclobots (Visual Basic)

  • license: Freely Redistributable
  • host-language: Visual Basic
  • development-stage: lost

RUBE

  • type: Automaton
  • inception-date: 1997
  • genre: Esolang
  • development-stage: mature
  • computational-class: ???
  • paradigms: Bully automaton, 2-dimensional
  • reference-distribution: RUBE distribution
  • entry @ esolangs.org
  • online @ archive.org

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

  • license: BSD license
  • implementation-type: interpreter
  • host-language: ANSI C

REDGREEN

  • type: Automaton
  • inception-date: 1998
  • genre: Esolang
  • development-stage: mature
  • computational-class: Turing-complete
  • influences: RUBE
  • paradigms: Cellular automaton
  • reference-distribution: REDGREEN distribution
  • entry @ esolangs.org
  • online @ catseye.tc

Sample configuration:

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

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

Reference Implementation: redgreen.alp

  • license: BSD license
  • implementation-type: formal description
  • host-language: ALPACA

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

  • license: BSD license
  • implementation-type: interpreter
  • host-language: Perl

Implementation: worb.js

  • license: BSD license
  • implementation-type: interpreter
  • host-language: Javascript
  • host-platform: HTML5

Implementation: tc.catseye.yoob.worb

  • license: BSD license
  • implementation-type: interpreter
  • host-language: Java
  • host-platform: yoob

Circute

screenshot

  • type: Automaton
  • inception-date: 2005
  • genre: Esolang
  • development-stage: mature
  • computational-class: known not Turing-complete
  • influences: Wireworld
  • paradigms: Cellular automaton
  • reference-distribution: Circute distribution
  • entry @ esolangs.org
  • online @ catseye.tc
  • jnlp @ archive.org

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

  • license: BSD license
  • implementation-type: formal description
  • host-language: ALPACA

Implementation: tc.catseye.yoob.circute

  • license: Public Domain
  • implementation-type: interpreter
  • host-language: Java
  • host-platform: yoob

Braktif

  • type: Automaton
  • inception-date: 2005
  • genre: Esolang
  • development-stage: mature
  • computational-class: believed Turing-complete
  • influences: brainfuck
  • paradigms: Cellular automaton
  • reference-distribution: Braktif distribution
  • entry @ esolangs.org
  • online @ catseye.tc

Sample configuration:

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

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

Reference Implementation: braktif.alp

  • license: BSD license
  • implementation-type: formal description
  • host-language: ALPACA

Xigxag

  • type: Automaton
  • inception-date: Apr 23, 2007
  • genre: Esolang
  • development-stage: mature
  • computational-class: unknown computational class
  • paradigms: String-rewriting
  • reference-distribution: Xigxag distribution
  • entry @ esolangs.org
  • online @ archive.org

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

  • license: Public Domain
  • implementation-type: interpreter
  • host-language: Perl

Didigm

  • type: Automaton
  • inception-date: Nov 20, 2007
  • genre: Esolang
  • development-stage: not fully complete
  • computational-class: ???
  • paradigms: Cellular automaton, Reflective
  • reference-distribution: Specs on Spec distribution
  • entry @ esolangs.org

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

  • type: Automaton
  • inception-date: Apr 11, 2009
  • genre: Esolang
  • development-stage: mature
  • computational-class: known not Turing-complete
  • paradigms: Cellular automaton, 2-dimensional
  • reference-distribution: Jaccia and Jacciata distribution
  • entry @ esolangs.org
  • online @ catseye.tc

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

  • license: BSD license
  • implementation-type: formal description
  • host-language: ALPACA

Jacciata

  • type: Automaton
  • genre: Esolang
  • online @ catseye.tc

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

Chzrxl

preview

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

Reference Implementation: chzrxl.js

  • type: Implementation
  • license: Public Domain
  • host-language: Javascript
  • host-platform: HTML5

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

  • license: Public Domain
  • implementation-type: generator
  • host-language: Javascript
  • host-platform: HTML5

Schrödinger's Game of Life

screenshot

  • type: Automaton
  • inception-date: Feb 7, 2015
  • genre: Experimental language
  • development-stage: mature
  • computational-class: ???
  • paradigms: 2-dimensional, Cellular automaton, Non-deterministic
  • reference-distribution: Schrödinger's Game of Life distribution
  • online @ catseye.tc

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

  • license: Public Domain
  • implementation-type: interpreter
  • host-language: Python

Implementation: slife.js

  • license: Public Domain
  • implementation-type: interpreter
  • host-language: Javascript
  • host-platform: HTML5

About these Automata

We should say a few words about these automata here.