User:Ssstephen/rule-110

Here I mess around with cellular automata and "computers" they can be emulated in, like playing cards and knitting.

Rule 110

Cellular automata are a type of computer where the data (usually binary) is updated according to certain rules based on the previous state of the computer, often each byte is calculated in relation to its previous state and those of it's nearest neighbours.

Play the universal game

Click anywhere to change a pixel. This is a p5.js version of the cellular automaton often referred to as Rule 110. Each cell (black or white square) is generated by simple rules from the three squares above it.

Universality in Elementary Cellular Automata, Matthew Cook

Background pattern for the cellular automata rule 110, when it is used as a universal computer.

A larger section of rule 110 gameplay showing some gliders

This game has been proven turing complete by Matthew Cook in Universality in Elementary Cellular Automata. In particular a universal computer can be built when using the repeating background pattern 11101100100000. On this background variations can be make to programme "gliders" in a cyclic tag system, which is itself capable of universal computation.

-

-

-

-

-

-

-

-

Because a system is universal, some of its properties are undecidable (will it become periodic, will a particular sequence occur)

Because Turing machines are universal, if a compiler exists that can compile any data and program from a turing machine to another computer, then that computer is also universal

Tag systems are universal ACDABBE --> DABBECCDD

Cyclic tag systems can only have a two letter alphabet {Y,N}, but they can emulate tag systems so are also universal.

A glider system from Matthew Cook's paper 'Universality in Elementary Cellular Automata'

A glider system (see image) is a system of moving particles called gliders. In the image you can see diagonal lines which interact with vertical lines (the tape head or data) in the centre, emulating a cyclic tag system. The glider system is running an emulation of the cyclic tag system, which is running an emulation of the tag system. In a way this looks like a vector system to me, of interacting vectors rather than flipping bits.

Lastly you run an emulation of the glider system inside rule 110.

-

Fabric version of this could be really interesting. If you got a round loom with 14n pins (a flat loom maybe would be more flexible, to decide different sizes), you could knit a hat or sock program. https://www.youtube.com/watch?v=gOTIAmg0Iow Or does it need to be woven? No idea.

The piece should be a ring so the ends more obviously loop back on themselves. Re: slow computing, computation as labour, This Work of Body / This Body of Work, Meghan Clarke https://www.designacademy.nl/p/study-at-dae/graduation-show/graduation-projects/meghan-clarke Talk to Daniela about double sided knitting, re binary knitting and ternary knitting. So the knitting is the computation; knit the first line of the program then knit further to get the output. A little similar to a quipu, although probably a less efficient system. Are quipus universal?

Programming some A gliders into 110, of increasing width from left to right.

What can you compute on rule 110 (apart from everything)? Can you write a hello world script on a rule 110 computer? Can you add 2+2? https://www.youtube.com/watch?v=QKnSRw_X2w4

First attempts here at coding in the p5.js version of 110 with a few A gliders of increasing widths. Even experimenting on the javascript version of this is so slow, doing this in playing cards or knitting would be incredibly slow. But if it's a statement about computational labour the slowness reveals that.

Stopped at page 13 for now.

Why

Universalism is ridiculous

The idea that computers can solve all our problems is still around, despite so much evidence to the contrary. This particular computer that can do everything is actually pretty useless because it is extremely difficult to interact with in a meaningful way. Visualising black and white pixels/cards/threads that are slowly computed is a way to draw attention to the energy that goes into making calculations.

Slowing down the computer

Computers are sometimes thought of as quick and powerful tools. They are this way because a lot of design and development has gone into (and continues to go into) improving them, and a lot of energy and materials get consumed by them in order to make these calculations.

Computing together

Playing this card game is a communal action. There is labour involved, and play and collaboration. These things are not a metaphor for processes in digital networks but in fact examples of what is actually happening. By slowing down and visualising this process, some of these elements are made more obvious which are often obscured.

Rules

Computers follow strict rules and humans don't (always), so it's funny to ask humans to do something that is usually done by a logic gate. Will they follow the rules or will they cheat / make mistakes? Is making a mistake cheating? Intention of the individual actors vs intention of the system, or the initialiser of the system seems interesting to explore. Card games are usually imagined as a field where humans follow rules and cheating is generally discouraged (or even not considered) so this seems like an interesting medium for this.

Playing this with a deck of cards

First attempt at card rules

Solitaire version of cards played with 110

1. Players are given a large number of cards which are black on one side and white on the other. Players should be in a circle.
2. In the first hand everyone plays one card with either side face up, chosen by any method (no rules for this hand! see below for turing complete version of the game).
3. Everyone plays a new card based on the last hand's cards (in particular their own and the player on each side of them).
   • If you and your neighbours all played the same colour last round, you should play white.
   • If the person to your left played black but you and the person to your right played white, you should play white.
   • In all other cases, you should play black.
4. Keep playing hands until you halt!

Turing complete variation

If you would like this round to be Turing complete you will need 14n players. The simplest place to start is to play the first round as follows:

• player one: white
• player two: white
• player three: white
• player four: black
• player five: white
• player six: white
• player seven: black
• player eight: black
• player nine: white
• player ten: black
• player eleven: black
• player twelve: black
• player thirteen: black
• player fourteen: black

Then proceed by the usual rules. Programs can be written by making variations on the starting hand.

Memoryless version

Each player gets one card and flips it to black or white according to the usual rules. This requires much less cards! An alternative form of memory could be used like time lapse photography. A digital memoryless version, possibly in a circle, could also show this principle.

Calculating this with knitting

Two sided knitting is another, even slower way of clocking this machine. The initial state is the order of th

Double Knitting would be a useful technique (emulation?) for this computer. Three colour knitting also seems very interesting, not for this computer but instead some sort of ternary cellular automota, which some people have explored here for example.

A thing about sustainability that came up

Laser cut playing pieces for 110, from recycled corrugated card

When I decided to make cards for this game it seemed like a great idea and I had plans to either laser cut some duplexed paper or even duplex handmade paper myself (if you bond the papers while they're still wet it's much more effective). Then I went for a walk and was thinking about cards that are different on one side than the other. I realised this is the standard way to design playing cards, and the game could be played with a normal deck (or multiple decks) if you ignore all the other information. From an environmental point of view I really like this idea as it doesn't introduce any more physical junk into the world.

But I also really like making things out of paper, and have been taught that prototyping is an important step of the design process. Is this true though? Making and prototyping require energy and material, which are finite and depend on extractive processes with negative side effects. If you have thought of a way to execute something with minimal environmental impact, is it immoral to continue testing and prototyping other options? What if the other options are potentially better? It seems like the knowledge you could potentially gain is greater than the harm you could cause, but there are examples in history like Test Baker at Bikini Atoll, and John B. Watson's experiment on Little Albert. Historically science has pushed too far and then doubled back, maybe we could be more sensitive to how far we're pushing and stop before the breaking point?

Then Daniela suggested laser cutting the cards out of scrap instead of specially bought/created paper. This has the benefit of not being constrained to playing card size (in favour of the found cards), and I decided cutting a few pieces of paper for a prototype would be a worthwhile expenditure of materials / energy. The materials were on their way to being recycled and still can be at some stage so I have just inserted an extra state in that process. The energy from the lasercutter however cannot be recovered, so the cost of the prototype includes this energy. Using visibly recycled materials also has a symbolic strength of course, and could make this action even more worthwhile. The energy expense of the lasercutter "paid for" the symbolic currency of the prototype. Weird commerce metaphor but it is useful when thinking about balance.