Automata

Note that the precise distinctions between an Automaton, a Programming Language, and a Gewgaw are debatable, and entries may be categorized somewhat arbitrarily.

by Cat's Eye Technologies

  • Backtracking Wang Tiler (in Javascript) (Feb 2015)

    Try it Online

    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.

    (Illustration)
  • Braktif (in ALPACA) (2005)

    Try it Online

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

    (Illustration)
  • Chzrxl (in Javascript) (2013)

    Try it Online

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

    (Illustration)
  • Circute (in Java and ALPACA) (2005)

    Try it Online Try it (Java Web Start)

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

    (Illustration)
  • Cyclobots (in Visual Basic and Javascript) (ca 1994)

    Try it Online

    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.

    (Illustration)
  • Jaccia (in ALPACA) (Apr 11, 2009)

    Try it Online

    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.

    (Illustration)
  • Jacciata (in ALPACA) (Apr 11, 2009)

    Try it Online

    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.

    (Illustration)
  • REDGREEN (in ALPACA) (1998)

    Try it Online

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

    (Illustration)
  • SMETANA (in Perl and Java and Visual Basic) (ca 1994)

    Try it (Java Web Start)

    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.

    (Illustration)
  • Schrödinger's Game of Life (in Javascript and Python) (Feb 7, 2015)

    Try it Online

    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.

    (Illustration)
  • noit o' mnain worb (in Javascript and Java and Perl) (Sep 15, 2000)

    Try it Online Try it (Java Web Start)

    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?)

    (Illustration)
  • Didigm (Nov 20, 2007)

    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.

  • RUBE (in ANSI C) (1997)

    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.

  • Xigxag (in Perl) (Apr 23, 2007)

    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.)

by Our Valued Partners

Commentary

What's the difference between an automaton and a programming language and a calculus and a model of computation? Precious little, I'm afraid — under many circumstances you can consider them just about interchangeable. There are subtleties, and I'll try to write something about those subtleties at some point. But don't be too surprised when they (seemingly arbitrarily) get lumped together here, and when they (seemingly arbitrarily) don't.