Exploring Universal Ternary Gates

Exploring Universal Ternary Gates

In this post: finding a gate that can emulate any other gate when using three-valued logic.

Universal Gates

Logic circuits are made up of gates connected by wires. Wires hold values, and gates operate on those values. Creating a circuit that computes a particular function is just a matter of running the inputs through the right gates in the right order.

Intuitively, you might expect that ever more complicated functions would require ever more complicated gates. It turns out that this is false: you can find universal sets of gates that can compute any function. In fact, there are gates that are universal all on their own.

When working in the usual two-valued boolean logic, there are two universal gates: the nand gate and the nor gate. (Note that I’ll only be talking about gates with two inputs in this post. See Toffoli gate for a three-input universal gate.) We can create any boolean function you can imagine, with a fixed number of inputs and outputs, using nothing but nand gates.

One day a coworker wondered if three-valued logic also had universal gates, like nand and nor but for three values instead of just true/false. A cursory googling revealed nothing… so I was sniped, and had to figure out the answer.

Ternary Logic and Gates

To do ternary logic, we need three values. I’m going to be using , , and as those values. You can think of as corresponding to true, as corresponding to false, and as being the extra “neither/both/whatever” value… but really they’re just arbitrary symbols.

A ternary function or gate is specified entirely by what to output for each possible input. We’ll be working with two-input single-output gates. That means there are possible inputs, possible outputs, and possible gates.

The most straightforward ternary gates to specify are the constant output gates, which just unconditionally return the same value regardless of their input:

Surprisingly, the above constant gates are actually not the simplest when it comes to how many things you can compute. The simplest gates are actually 1st and 2nd, which just return one of their inputs while ignoring the other:

The reason 1st and 2nd are the simplest gates, at least for our purposes, is because you get them for free. When building a circuit, no matter what gates you have available, you can always compute 1st or 2nd by applying no gates: just directly use the input wire instead of running it through a gate.

Thought of in another way: in the directed graph of gates that can emulate each other, 1st and 2nd are the leafs. Our starting point.

Exploring Ternary Gates

One useful trick when thinking about logic circuits is to imagine the gates as having an immutable value equal to the function they compute with respect to the circuit’s inputs.

So, when building a circuit, we start off with two values corresponding to the inputs: 1st and 2nd. Then we create new values by combining those values through a gate. This places a new gate into the circuit, with a (hopefully) distinct value. That’s how I think of circuits anyways: using gates to combine gates to make other gates in order to explore the space of gates.

Reading over that it does sound kind of weird, but it’s actually really simple. Let’s do an example. Suppose the candidate gate we’re working with is the min gate. min returns the smaller of its inputs, with the convention that :

We start off with our starting values: 1st and 2nd. We want to try to make as many different values as we can, by running values we already have through min. Let’s try combining 1st and 2nd together:

Go figure: when you compute the minimum of the inputs, the resulting function value is min. How tautological.

Now we have three function values we know we can reach: 1st, 2nd, and min. Unfortunately, as you’ll find out if you try it out for yourself, we can’t make any more. We always end up with just another way to make 1st, 2nd, or min instead of something new. Clearly min is not a universal gate.

Trying Another Gate

We barely got anywhere with min. Let’s try another gate to see if we get farther. I call the gate we’ll look at now imp, because it is a generalization of boolean implication. Its truth table is a lot like min‘s, except inverted and flipped:

Once again we start with just 1st and 2nd. If we gate those two together with imp, we trivially reach imp in exactly the same way that min gave us min. However, unlike with min, we have other useful moves available when using imp. For example, if we imp the first input into itself we get this function:

The above gate is like 1st, except it returns instead of when the first input was .

Clearly imp is more flexible than min was. Unfortunately, it’s still not universal. By combining and recombining 1st and 2nd in different ways using imp, we’ll be able to reach only functions. That’s a big improvement over , but nowhere near .

Note that we could have used a trick to know immediately that imp was not universal, without doing a breadth-first search of reachable functions. Knowing that 0 imp 0 = 0 is sufficient. It means there’s no way to escape to another value when both inputs are 0, implying imp can never be used to compute a function like “always return +“.

Generalizing Nand

Let’s try one more gate. This time we’ll base it off of nand, hoping to “bring along the universal-ness” by starting from a universal gate from another logic. We’ll extend nand to ternary by interpreting its truth table as “True when inputs differ, else rotate to next value” and generalizing. I’ll arbitrarily call the resulting function tand:

Let’s experiment a bit. If we combine 1st with itself, tand keeps getting matching inputs which it cycles from to to and back. So we end up “incrementing” the first input:

Basically everything we try to combine right now is going to result in a new function. For example we can get inc2 from 2nd tand 2nd, we can get dec1 from inc1 tand inc1, and we can get all+ from 1st tand inc1. With these in hand it’s a few short steps to gates whose output distinguishes one input from all the others:

and once you have gates like that you can start doing anything you want. It turns out that tand is in fact a universal gate.

That answers the original question: there are in fact universal ternary gates. I’m a bit curious how many, though.

Universal Universality

After I found tand I wrote code to find other universal ternary gates:

private static IEnumerable<TernaryGate> UniversalGates() {
    // hack: the hash code of a ternary gate is guaranteed to be under 2^18 and to not collide
    // we take advantage of that to do known-result lookups faster
    var tryIsUniveralByHash = new bool?[1 << 18];
            
    // optimization: having a known universal gate significantly speeds things up
    // it allows the 'what can I reach?' to terminate as soon as the known gate is found
    // instead of after ALL gates are found
    tryIsUniveralByHash[Tand.GetHashCode()] = true;
            
    foreach (var candidate in TernaryGate.All) {
        if (tryIsUniveralByHash[candidate.GetHashCode()].HasValue) continue;
                
        // if it turns out that this candidate is not universal
        // then all of the gates it reached also can't be universal
        // so we track them to be marked in that case
        var weakGates = new List<TernaryGate> {candidate};

        var reachedCount = 0;
        foreach (var reachedGate in candidate.ReachableGates()) {
            reachedCount += 1;

            var tryIsUniversal = tryIsUniveralByHash[reachedGate.GetHashCode()];
            if (tryIsUniversal == null) {
                // if the candidate gate isn't universal, we learn this reached gate also isn't
                weakGates.Add(reachedGate);
            } else if (tryIsUniversal == true) {
                // reaching a universal gate implies the candidate gate must be universal
                reachedCount = TernaryGate.CountAll;
                break;
            }
        }

        if (reachedCount == TernaryGate.CountAll) {
            yield return candidate;
            tryIsUniveralByHash[candidate.GetHashCode()] = true;
        } else {
            foreach (var gate in weakGates) {
                tryIsUniveralByHash[gate.GetHashCode()] = false;
            }
        }
    }
}

(Complete source is on github. I also brute force double-checked that tand was a universal gate.)

It turns out that 3773 of the 19383 two-input ternary gates are universal.

Speculation time: It’s interesting that the proportion of ternary gates that are universal is much higher than the proportion of binary gates that are universal (about 19.5% vs 12.5%). I suspect that this trend continues; that the proportion of universal gates limits to 100% as the number of values in your logic increases. I think all you need for a gate to be universal is some way to convert each of the values to and from two values that the gate acts on as if it was a nand. That’s constraints in a system with degrees of freedom, so it seems like the freedoms increase asymptotically faster and will result in almost all n-ary gates being universal.

Update: Turns out the proportion of universal gates does not limit to 100%. It limits to . The fact that Euler’s constant shows up here is amazing. The reason it can’t be 100% is because, as I mentioned above, the gates must satisfy for each value . That decreases the maximum proportion of universal gates by a factor of for each of the values. Counting all those up gives , so clearly there can’t be more than universal gates per gate. The concluding remarks in this paper casually mentions that the answer is in fact (unfortunately, I can’t access the papers it references for that result).

Summary

A universal gate can emulate any other gate.

You can think of gates in a circuit as producing new functions over the circuit’s inputs.

The following is a universal gate for three-valued logic:

Universal gates are not scarce.

Discuss on Reddit

My Twitter: @CraigGidney

Comments are closed.

Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.

Archive