# How do we score turing complete cellular automata (GoL, Wireworld, etc)

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?

• By how many bytes it takes to save the file as normal? – Blue Feb 8 '17 at 12:06
• 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"? – Martin Ender Feb 8 '17 at 12:08
• @MartinEnder Eh, I'm unsure about that. – Matthew Roh Feb 8 '17 at 12:08
• @MatthewRoh That is one of the criteria for programming languages. – Mike Bufardeci Feb 8 '17 at 16:18
• 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. – Mike Bufardeci Feb 8 '17 at 16:24
• @MikeBufardeci GoL is certainly considered a programming language. – Wheat Wizard Feb 8 '17 at 17:03
• @WheatWizard True, since its turing-complete. – Matthew Roh Feb 8 '17 at 17:06
• @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. – Mike Bufardeci Feb 8 '17 at 17:28
• 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 – Matthew Roh Feb 8 '17 at 17:41
• @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. – Mike Bufardeci Feb 8 '17 at 19:55
• 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. – mbomb007 Feb 8 '17 at 22:11
• Possibly the bytes when you change it into something like a "text format"(not including trailing whitespace)? Or the size of the image file? – Matthew Roh Feb 9 '17 at 3:55
• @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.) – DLosc Feb 9 '17 at 6:05
• @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 – DLosc Feb 9 '17 at 6:12
• Note: accoording to the wiki, "despite the simplicity of the rules, Wireworld is Turing-complete." – Matthew Roh Feb 9 '17 at 7:30

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

• I think this is the best approach. Let each CA have its own textual/binary encoding, and count the bytes of those. – user45941 Feb 9 '17 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.

• 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. – user45941 Feb 9 '17 at 2:50
• 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? – Mike Bufardeci Feb 9 '17 at 15:31
• The initial state. – mbomb007 Feb 9 '17 at 16:53
• @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. – mbomb007 Feb 9 '17 at 16:55
• 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). – user45941 Feb 9 '17 at 16:57
• @Mego Yet we score ASCII (7-bits) on equal ground with UTF-8. – mbomb007 Feb 9 '17 at 16:59
• 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. – user45941 Feb 9 '17 at 17:01
• 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. – mbomb007 Feb 9 '17 at 17:04
• Let us continue this discussion in chat – user45941 Feb 9 '17 at 17:05
• @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. – Mike Bufardeci Feb 9 '17 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.