Can this set of rules perform all Boolean operations?

Question

I never worked in this field before, I just thought about this set of rules and never saw something similar before. I apologise if I don't use the right mathematical vocabulary for my question.

Imagine a graph, in which bulbs are linked. The light can whether be on or off. Bounds between bulbs are one-way. But more than one bound between two bulbs are possible.

Then there is this rule : Each time the clock ticks, the bulbs who receive light from at least two alight bulbs become lit too. The others are turned off.

For example, the previous graph will, the next time the clock ticks, become like this :

And then it will become :

I made a quick search, but I'm not used to the mathematical vocabulary of this field but I'm pretty sure it exists. Then I studied this... "set of rules" a little bit.

Before the question, here are some interesting and maybe useful circuits.

This narcissistic bulb will never get off, because it's connected to itself by two bounds.

This is an AND gate because, the bulb C will be lit (after 1 cycle) if and if only the bulb A AND the bulb B are lit.

This is an OR gate because, the bulb C will be lit (after 1 cycle) if and if only the bulb A OR the bulb B is lit.

I wanted to determine if I could build a computer with this set of rules. This is why I tried to determine the classical logic Boolean gates. But the NOT gate is essential to Boolean arithmetic, and I can't think of a way to create it or to prove it's impossible.

A NOT gate is supposed to be a circuit where if a bulb A is lit, then after a predetermined clock ticks, the bulb B will be off, and if A is off, B will be lit. A kind of inverter.

My questions are :

• How is this field named in mathematics ?
• Is it possible to create a NOT gate ?

Answer 1

Let's describe a system of nodes that would describe the smallest possible NOT gate that has at-least one input node and one output node.

• When the input to the gate is ON, there need to be exactly zero other ON nodes connected to the output node to result in an output of OFF.
• When the input to the gate is OFF, there need to be at least two other ON nodes connected to the output node to result in an output of ON.

At the very least, we need two more nodes other than the input node to be connected to the output node.

• These nodes need to be OFF when the input node is ON. The input node can either be connected to these two nodes or not to achieve this as a single ON won't turn them on.
• These nodes need to be ON when the input node is OFF. This means that there needs to be an NOT gate between the input node and each of these two nodes.

Since the smallest construction of a NOT gate requires two NOT gates, the size of the smallest NOT gate is infinite in size. Therefore, you cannot construct a NOT gate with your rules.

Answer 2

It seems one could take your model and implement it with a Petri net

• directed bounds = arcs
• light = tokens
• receiving light of two other bulbs via a bound means activating the bulb = two tokens arrive at a place (which is configured to fire if two or more markers arrive), place activates and fires a marker

Answer 3

There is no way to create a "NOT" gate because bulbs are only turned on if other bulbs are on, and if you turn more bulbs on then you'll just wind up with at least as many bulbs being turned on when you apply your iteration. So turning a bulb off can only result in perhaps some other bulbs being turned off -- never that a new bulb will be turned on that wouldn't have already been turned on.

Answer 4

If you are willing to let a collection of more than one bulb represent a "state", then you can build a "NOT" gate by having bulbs A,B,C where A and B both have arrows in each direction between them, and then there are arrows from C to A and also C to B, and bulb C is always on, and one and only one of A and B is on. Then when you iterate, the bulb that is on will alternate back and forth between A and B. But note, if ever A and B are both on or both off, then the whole thing breaks. So you really do need to consider the combination of A and B to be the "state", and you need always for only one of them to be on, and whichever one is on tells you whether the state true or false.