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

—

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

- strilanc
- What Quantum Computers Do Faster, with Caveats
- Naming Things: Fail-Useful
- Detecting Simple Cycles Forming, Faster
- Third Party Bit Commitment
- Angular Velocity is Simple
- Collection Equality is Hard
- Deadlocks in Practice: Don’t Hold Locks While Notifying
- Brute Force Parallelization
- A Year’s Worth of Opinions about Objective-C
- Referencing Substrings Faster, without Leaking Memory
- Not Crying Over Old Code
- Exploring Universal Ternary Gates
- Impractical Experiments #2: Securing Peer to Peer Fog of War against Map Hacks
- Achieving Exponential Slowdown by Enumerating Twice
- Using Immortality to Kill Accidental Callback Cycles
- Cancellation Tokens (and Collapsing Futures) for Objective-C
- Visualizing the Eigenvectors of a Rotation
- Collapsing Futures in Objective-C
- Bug Hunting #1: Garbled Audio from End to End
- Impractical Experiments #1: Representing Numbers as Polynomials
- Implementing Quantum Pseudo-Telepathy
- Turn On Your Damn Warnings
- Big-O Made Trivial
- Unfathomable Bugs #7: The Broken Oven
- Solomonoff’s Mad Scientist
- Yearly Blogging Roundup #1
- What isn’t a Monad
- Searching a Sorted Matrix Faster
- How to Read Nested Ternary Operators
- Making Sublime Text 2 Jump to the Correct Line with Unity on OS X
- My Bug, My Bad #4: Reading Concurrently
- Whole API Testing with Reflection
- Optimizing a Parser Combinator into a memcpy
- Don’t Treat Paths Like Strings
- Breaking a Toy Hash Function
- Counting Iterators Lazily
- Unfathomable Bugs #6: Pretend Precision
- My Bug, My Bad #3: Accidentally Attacking WarCraft 3
- Collapsing Types vs Monads (followup)
- Collapsing Futures: Easy to Use, Hard to Represent
- Eventual Exceptions vs Programming in a Minimal Functional Style
- The Mystery of Flunf
- Explain it like I’m Five: The Socialist Millionaire Problem and Secure Multi-Party Computation
- Computer Science Blows My Mind
- A visit to Execution Labs in Montréal
- Transmuting Dice, Conserving Entropy
- Rule of Thumb: Ask for the Clock
- Rule of Thumb: Use Purposefully Weakened Methods
- Rule of thumb: Preconditions Should be Checked Explicitly
- Intersecting Linked Lists Faster
- Mouse Path Smoothing for Jack Lumber
- My Bug, My Bad #2: Sunk by Float
- Repeat Yourself Differently
- Grover’s Quantum Search Algorithm
- Followup to Non-Nullable Types vs C#
- Optimizing Just in Time with Expression Trees
- When One-Way Latency Doesn’t Matter
- Determining exactly if/when/where a moving line intersected a moving point
- Emulating Actors in C# with Async/Await
- Making an immutable queue with guaranteed constant time operations
- Improving Checked Exceptions
- Perishable Collections: The Benefits of Removal-by-Lifetime
- Decoupling shared control
- Decoupling inlined UI code
- Linq to Collections: Beyond IEnumerable<T>
- Publish your .Net library as a NuGet package
- When null is not enough: an option type for C#
- Unfathomable Bugs #5: Readonly or not
- Minkowski sums: examples
- My Bug, My Bad #1: Fractal Spheres
- Working around the brittle UI Virtualization in Windows 8
- Encapsulating Angles
- Unfathomable Bugs #4: Keys that aren’t
- How would I even use a monad (in C#)?
- Useful/Interesting Methods #1: Observable.WhenEach
- Unfathomable Bugs #3: Stringing you along
- Anonymous Implementation Classes – A Design Pattern for C#
- Tasks for ActionScript 3 – Improving on Event-Driven Programming
- Minkowski sums and differences
- Non-Nullable Types vs C#: Fixing the Billion Dollar Mistake
- Unfathomable Bugs #2: Slashing Out
- Script templates and base classes
- Unity font extraction
- Abusing “Phantom Types” to Encode List Lengths Into Their Type
- Constructive Criticism of the Reactive Extensions API
- Quaternions part 3
- Quaternions part 2
- Quaternions part 1
- Unfathomable Bugs #1: You can have things! You can have things IN things! You can have …
- Coroutines – More than you want to know
- Asset Bundle Helper
- The Visual Studio goes away
- .Net’s time traveling StopWatch
- Introducing Catalyst