The (somewhat) working wireworld checkbox

Here is a checkbox I made in wireworld, for the "Create a checkbox!" question.

The problem is, we don't have a way to score answers like these.

Do we score these by pixels, like piet did, or in other ways?

  • 4
    \$\begingroup\$ By how many bytes it takes to save the file as normal? \$\endgroup\$
    – Blue
    Feb 8, 2017 at 12:06
  • 8
    \$\begingroup\$ Shouldn't we start from the question "how do cellular automata take input and return output so that we can treat them as programming languages"? \$\endgroup\$ Feb 8, 2017 at 12:08
  • \$\begingroup\$ @MartinEnder Eh, I'm unsure about that. \$\endgroup\$ Feb 8, 2017 at 12:08
  • \$\begingroup\$ @MatthewRoh That is one of the criteria for programming languages. \$\endgroup\$ Feb 8, 2017 at 16:18
  • \$\begingroup\$ If there is a cellular automata that does meet our definition of a programming language, I would say something like "Number of Cells" but that gets fuzzy fast. Conway's Game of Life is technically on an infinite plane for example (although GoL isn't currently considered a programming language here). Also there's no clear consensus on how to measure Piet programs right now. \$\endgroup\$ Feb 8, 2017 at 16:24
  • \$\begingroup\$ @MikeBufardeci GoL is certainly considered a programming language. \$\endgroup\$
    – Wheat Wizard Mod
    Feb 8, 2017 at 17:03
  • \$\begingroup\$ @WheatWizard True, since its turing-complete. \$\endgroup\$ Feb 8, 2017 at 17:06
  • \$\begingroup\$ @WheatWizard (and Matthew Roh) I don't see how it meets the requirements I linked to earlier but I trust you guys. This is not really related to the topic at hand though. \$\endgroup\$ Feb 8, 2017 at 17:28
  • \$\begingroup\$ 1. Representation of Natural numbers and tuples: unsure, 2. Taking input and sending output: partially, 3. Adding two natural numbers: yes, 4. Finding prime: unsure, People has been asking for answers in those cellular automatas: absolutely \$\endgroup\$ Feb 8, 2017 at 17:41
  • \$\begingroup\$ @MatthewRoh So by your own admission it's unclear if these count as programming languages on this site. I want to reiterate that this is not the best place to be discussing this. \$\endgroup\$ Feb 8, 2017 at 19:55
  • \$\begingroup\$ I think the number of cells in the smallest bounding rectangle would be a good measurement. The fact that it's infinite doesn't really matter. ><> is "infinite", but you just don't count trailing infinite whitespace. \$\endgroup\$
    – mbomb007
    Feb 8, 2017 at 22:11
  • \$\begingroup\$ Possibly the bytes when you change it into something like a "text format"(not including trailing whitespace)? Or the size of the image file? \$\endgroup\$ Feb 9, 2017 at 3:55
  • 1
    \$\begingroup\$ @MikeBufardeci It would certainly be good to have implementations of these tasks that we could point to. However, if it is true that GoL or Wireworld are Turing-complete, then they definitely meet our criteria. The criteria were chosen as a less stringent requirement than Turing-completeness--a superset of the Turing-complete languages, if you will. (See first bullet point under Observations in the answer you linked.) \$\endgroup\$
    – DLosc
    Feb 9, 2017 at 6:05
  • \$\begingroup\$ @Martin We need to explore the same question for something like Bitwise Cyclic Tag, where (for example) the "output" of Esolangs.org's Collatz program is defined as: "when (and only when) the data-string takes the form (100)^k immediately before beginning a cycle through the program [i.e. on steps that are multiples of 24], it represents the integer k." I don't believe that format is among the default I/O methods. :P \$\endgroup\$
    – DLosc
    Feb 9, 2017 at 6:12
  • \$\begingroup\$ Note: accoording to the wiki, "despite the simplicity of the rules, Wireworld is Turing-complete." \$\endgroup\$ Feb 9, 2017 at 7:30

5 Answers 5


There shouldn't be a general answer for all cellular automata.

People have pointed out that cellular automata are diverse. Some have only two states and square cells. Others have differently shaped cells with different rules and many possible states. This diversity means that we should not have one rule for all of them. Instead we should look at each one individually and decide how to score it.

  • \$\begingroup\$ I think this is the best approach. Let each CA have its own textual/binary encoding, and count the bytes of those. \$\endgroup\$
    – user45941
    Feb 9, 2017 at 17:24

I know that golly allows you to copy and paste text into it, with spaces as empty cells, non-space as filled cells, and newline as ... newline. After pressing cmd/ctrl v, you click once, and the pattern is placed. Perhaps this could be used for the scoring system?


MCL Code

There is a Cellular automata emulator, which is widely used, called MCell.

This can emulate Cellular automata and create code for each, with the .mcl extension.

Maybe we might be able to use this.


The smallest bounding rectangle

If the program fits in a 16 by 16 rectangle of cells, then its score is 256 cells.

Worrying about how many bytes it'd take to store in a file isn't really a relevant plan unless there's a built-in way to convert a state into a file. If there is a built-in way to do that, then use the file size. As long as there's not, then the bounding rectangle should be used, because it represents the smallest grid that the base program could fit on, with the part outside the boundary all being the same infinite pattern, such as all live, or all dead.

  • 1
    \$\begingroup\$ This only works for GoL, where each cell represents a single bit. The system isn't fair for other systems like VarLife, where each cell has a rule and a alive/dead state. \$\endgroup\$
    – user45941
    Feb 9, 2017 at 2:50
  • \$\begingroup\$ Would this be the smallest bounding rectangle of the initial stare, or the smallest bounding rectangle for the program over the course of running it? \$\endgroup\$ Feb 9, 2017 at 15:31
  • \$\begingroup\$ The initial state. \$\endgroup\$
    – mbomb007
    Feb 9, 2017 at 16:53
  • \$\begingroup\$ @Mego This isn't bytes. This is cells. If there's no built-in byte scoring system, we shouldn't attempt to score with bits or bytes. Just use cells in the same way that Piet uses codels/pixels. \$\endgroup\$
    – mbomb007
    Feb 9, 2017 at 16:55
  • \$\begingroup\$ My point was, not all cells are created equal. In GoL, each cell holds one bit of information (alive/dead). In VarLife, each cell holds more than one bit of information (rule plus alive/dead). Scoring both of those types of cell equally is disingenuous - it's the same logic why we don't score by characters anymore (since UTF-16 is two bytes per character, while ASCII is one byte per character). \$\endgroup\$
    – user45941
    Feb 9, 2017 at 16:57
  • \$\begingroup\$ @Mego Yet we score ASCII (7-bits) on equal ground with UTF-8. \$\endgroup\$
    – mbomb007
    Feb 9, 2017 at 16:59
  • \$\begingroup\$ ASCII is represented as 1 byte, even if it doesn't use one of the bits. I'm not sure what you mean by "equal ground" - we directly compare the number of bytes, which is exactly equal to the number of characters in ASCII, but not necessarily so in UTF-8. \$\endgroup\$
    – user45941
    Feb 9, 2017 at 17:01
  • \$\begingroup\$ You mean UTF-16? And I still disagree. GOL can be thought of like ASCII. It just uses less of the bits per cell, but can be scored the same. \$\endgroup\$
    – mbomb007
    Feb 9, 2017 at 17:04
  • \$\begingroup\$ Let us continue this discussion in chat \$\endgroup\$
    – user45941
    Feb 9, 2017 at 17:05
  • 1
    \$\begingroup\$ @mbomb007 Comparing these to Piet might not be the best idea as there's currently no consensus on whether Piet programs should be counted by number of codels or bytes in the image. \$\endgroup\$ Feb 9, 2017 at 18:35

ceil(Pixels/logbase(states,256)) + 3

This only works for gol variants on an infinite, square, grid. It takes no entropy to store an empty infinite grid. This is a fairly roundabout scoring system, so please feel free to downvote or critique.

Note that if the size is greater than a 256 by 256 box add 2 for each byte needed as representation of the size of one dimension.

Essentially we could easily create a file format where you take start with one byte detailing the number of bytes in which the dimensions are stored. Thus, each side can be up to 2^(2^128) squares long. Later two bytes (one for each side). Then convert the map to a binary integer (1=filled, 0 = empty) (and pad with 0's to make a multiple of 8 bits) to store in the rest of the file.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .