-5 bytes thanks to @Dialfrost
f=lambda n,g=0,c=0:g<n**len(e:=range(n*n))!=(s:={g,sum(i//n*n**i for i in e),sum(i%n*n**i for i in e)})and f(n,g+1,c+([s:=s|{sum(g//n**(l//n**i%n*n+r//n**i%n)%n*n**i for i in e)}for _ in"a"*n**n**2for l in s for r in s]!=len(s)==n**n**2))or c
Try it online!
Uses a simple integer encoding of the gates, and composes them to depth n**(n*n)
which should be sufficient. It's able to calculate up to n=2
.
Full disclosure, this python golf is just to qualify this answer as code golf. The rest of this answer will explain how to calculate n=4
Explanation of the algorithm used to calculate n=4
The following algorithm works for all n>=2
. In this explanation I refer to gates (also) as functions. f(a,b)
denotes the value of gate f
with inputs a
and b
. Gates can be composed just like functions. To keep every function binary, I often use the special functions l(a,b)=a
and r(a,b)=b
(which just pass the left/right argument).
Core algorithm
Unary completeness
A gate f
is said to be unary complete if it's possible to create every unary function using f
. Obviously, f
has to be unary complete to be functionally complete.
We first check if f
is unary complete. If not, then it's not functionally complete. Then we move to the next section.
Functional completeness
Assuming that f
is unary complete, we can check if f
is functionally complete with the two following tests.
Lonelyness-test
We want to find some symbols a, b, c, d
where a≠b
and c≠d
, so that f(a, c)
is distinct from f(a, d)
, f(b, c)
and f(b, d)
. This means that f
is "lonely".
Using these values, and unary functions, we can simulate all of boolean logic.
If there are no such a, b, c, d
I claim that f
can't be functionally complete.
To see why, let's look at how non-lonely functions compose. Note that the functions l(x,y)=x
and r(x,y)=y
are not lonely. Assume L
and R
are non-lonely functions. g(a,b)=f(L(a, b), R(a,b))
. In general, L
, R
and f
have the one of the three following "truth" tables, for the relevant inputs:
. a b
c x x
d y y
. a b
c x y
d x y
. a b
c x y
d y x
It should be clear that composing these does not make the resulting function lonely. This is a finitary problem and can be easily proved with brute-force. It is the same reason xor
and not
are not functionally complete.
In other words, composing non-lonely functions makes non-lonely functions, and since some gates are lonely, a non-lonely gate cannot be universal.
Constructible-test
Again, we assume f
is unary complete, and also lonely.
A function f
is n+1-constructible if there are some subsets of the alphabet L
and R
where |L|=|R|=n
, |f[L,R]|≥n+1
. A function f
is constructible iff it is n-constructible for all n≥3
up to the length of the alphabet.
If f
is constructible, then it is definitely functionally complete. You can just convert your input to base-2, do whatever calculations you want, and then convert back to the full alphabet.
Now is it possible to not be constructible and still be functionally complete? No.
Let's assume that there is some n
so that f
is not n-constructible. Note that the functions l(x,y)=x
and r(x,y)=y
are never n-constructible. Assume L
and R
are non-n-constructible functions. Then g(a,b)=f(L(a,b),R(a,b))
is also non-n-constructible. Because the image of L
and R
has cardinality ≤n
, so does g
. Therefore g
is also non-n-constructible
Therefore f
has to be constructible to be functionally complete, because again, non-n-constructible gates compose to create non-n-constructible gates and some gates are n-constructible.
Optimizations
Data Format
A duadic function f
is represented as a n*n
list, so that f(a, b) = list[a*n+b]
.
This is a bit slow, so for n=4
I use a 32-bit integer.
Every function has a unique index. The indices start from 0 and have no gaps.
Every monadic function f(a,b)=g(b)
has a unique index. It also starts from 0 and has no gaps.
Transposition
A transposition fᵀ
is defined as fᵀ(a,b)=f(b,a)
Permutation
p
is a permutation of the alphabet. p(x)
applies the permutation. p⁻¹(x)
applies the inverse. p(p⁻¹(x))=p⁻¹(p(x))=x
.
fₚ
is defined as fₚ(a,b)=p⁻¹(f(p(a),p(b)))
Theorem 1
Claim: f
is functionally complete, iff fᵀ
also is.
Proof: You can just swap the arguments lol
Theorem 2
Claim: f
is functionally complete, iff fₚ
also is (for all permutations p
)
Proof: When you do function composition with fₚ
, the outer and inner permutations cancel out. So the "meat" of the function doesn't change, just that the alphabet is relabled.
Minimal representation
f
is said to be minimal if f≤fₚ
and f≤fₚᵀ
for all permutations p
(here ≤
refers to some total order). By theorem 1 and 2, we only need to consider minimal elements.
Rust code for n=4
main.rs
#![feature(let_else)]
#![feature(map_first_last)]
#![feature(adt_const_params)]
#![feature(generic_const_exprs)]
#![feature(label_break_value)]
use indicatif::{ProgressBar, ProgressStyle};
use itertools::Itertools;
use rand::Rng;
use rayon::prelude::*;
use std::sync::atomic::AtomicBool;
use std::sync::atomic::AtomicUsize;
use std::sync::atomic::Ordering::*;
use std::thread;
#[cfg(not(debug_assertions))]
macro_rules! get_unsafe {
[$a:expr, $i:expr] => {
*unsafe {$a.get_unchecked($i)}
};
}
#[cfg(debug_assertions)]
macro_rules! get_unsafe {
[$a:expr, $i:expr] => {
*$a.get($i).unwrap()
};
}
#[cfg(not(debug_assertions))]
macro_rules! get_mut_unsafe {
[$a:expr, $i:expr] => {
*unsafe {$a.get_unchecked_mut($i)}
};
}
#[cfg(debug_assertions)]
macro_rules! get_mut_unsafe {
[$a:expr, $i:expr] => {
*$a.get_mut($i).unwrap()
};
}
trait Function: std::hash::Hash + Clone + std::cmp::Eq + std::fmt::Debug + std::cmp::Ord {
const N: usize;
fn impl_eval(&self, a: usize, b: usize) -> usize;
#[cfg(debug_assertions)]
fn eval(&self, a: usize, b: usize) -> usize {
assert!(
a < Self::N && b < Self::N,
"Called eval with a={}, b={} but N={}",
a,
b,
Self::N
);
self.impl_eval(a, b)
}
#[cfg(not(debug_assertions))]
fn eval(&self, a: usize, b: usize) -> usize {
use std::hint::unreachable_unchecked;
if a >= Self::N || b >= Self::N {
// I am speed
unsafe {
unreachable_unchecked();
}
}
self.impl_eval(a, b)
}
fn pass_left() -> Self;
fn pass_right() -> Self;
fn compose(&self, left: &Self, right: &Self) -> Self;
fn unary_compose(&self, left: usize, right: usize) -> usize {
self.compose(
&Self::from_unary_index(left),
&Self::from_unary_index(right),
)
.unary_index()
}
// Used by fuzzers
fn random<R: Rng>(rng: &mut R) -> Self;
// Returns true if should be discarded
fn low_effort_discard(&self) -> bool {
for n in 0..Self::N {
if self.eval(n, n) == n {
return true;
}
}
false
}
// Unique, no holes, for r-unary ops
fn unary_index(&self) -> usize {
let mut ret = 0;
for a in (0..Self::N).rev() {
ret *= Self::N;
ret += self.eval(a, a);
}
ret
}
fn from_unary_index(i: usize) -> Self;
fn is_unary_complete(&self) -> bool
where
[(); Self::N.pow(Self::N as u32)]:,
{
// Bruteforce-checks if self is a unary-complete function
// Keeps track of all the visited nodes and has a queue of functions to add
// A function is popped from the queue and composed with every previous function, plus itself
// The new compositions are added to the queue
// visited is a "Linked list" containing the already visited unary functions
// 0 - not visited
// n - visited, next visited in n steps (n is possibly negative)
// Hack - this list can store BOTH the queue AND the already visited nodes
let mut visited = [0isize; Self::N.pow(Self::N as u32)];
let vl = visited.len() as isize;
let mut start = vl;
let mut queue;
let pri = Self::pass_right().unary_index();
get_mut_unsafe![visited, pri] = vl - pri as isize;
queue = pri as isize;
while queue != vl {
let ui = queue as usize;
// Pop from queue
queue += get_unsafe![visited, ui];
// Redundant, visited[ui] will get overwritten anyway
// visited[ui] = 0;
// Start iterating
let mut ptr = start;
while ptr != vl {
let add = [
self.unary_compose(ptr as usize, ui as usize),
self.unary_compose(ui as usize, ptr as usize),
];
// Push to queue
for x in add {
if get_unsafe![visited, x] == 0 {
get_mut_unsafe![visited, x] = queue - x as isize;
queue = x as isize;
}
}
// Next visited function
ptr += get_unsafe![visited, ptr as usize];
}
// Self-composition
let x = self.unary_compose(ui as usize, ui as usize);
// Push
if get_unsafe![visited, x] == 0 {
get_mut_unsafe![visited, x] = queue - x as isize;
queue = x as isize;
}
// Add self
get_mut_unsafe![visited, ui] = start - ui as isize;
start = ui as isize;
}
visited.iter().all(|&x| x != 0)
}
fn is_functionally_complete(&self) -> bool
where
[(); Self::N.pow(Self::N as u32)]:,
{
let n = Self::N;
let unary = self.is_unary_complete();
if !unary {
return false;
}
// Loneliness
let mut pass = false;
'a: for a in 0..n {
for b in 0..a {
for c in 0..n {
for d in 0..c {
let ac = self.eval(a, c);
let bc = self.eval(b, c);
let ad = self.eval(a, d);
let bd = self.eval(b, d);
let mut arr = [ac, bc, ad, bd];
arr.sort_unstable();
if arr[0] != arr[1] || arr[2] != arr[3] {
pass = true;
break 'a;
}
}
}
}
}
if !pass {
return false;
}
// k+1 - completeness
self.is_k_complete()
}
fn is_k_complete(&self) -> bool {
let n = Self::N;
let mut counter = vec![0; n];
let mut k = 2;
'b: while k < n {
let cmb: Vec<_> = (0..n).combinations(k).collect();
for l in &cmb {
for r in &cmb {
for &a in l {
for &b in r {
counter[self.eval(a, b)] = 1;
}
}
let s = counter.iter().sum();
counter.fill(0);
if s > k {
k = s;
continue 'b;
}
}
}
return false;
}
true
}
fn from_index(i: usize) -> Self;
fn to_index(&self) -> usize;
// If this function is minimal in it's equivalence class, returns the number of functions in the equivalence class
// Else returns zero
fn cifminelse0(&self) -> usize;
// Pretty prints this gate
fn pretty_print(&self) {
println!("Gate i={}", self.to_index());
let pad = " ";
let space = " ";
print!("{}?", pad);
for b in 0..Self::N {
print!("{}{}",space,b);
}
println!();
for a in 0..Self::N {
print!("{}{}", pad, a);
for b in 0..Self::N {
print!("{}{}",space,self.eval(a,b));
}
println!();
}
}
}
// Four bit functions
impl Function for u32 {
const N: usize = 4;
fn impl_eval(&self, a: usize, b: usize) -> usize {
*self as usize >> (a * 4 + b) * 2 & 3
}
fn pass_left() -> u32 {
0xFFAA5500
}
fn pass_right() -> u32 {
0xE4E4E4E4
}
fn compose(&self, l: &Self, r: &Self) -> Self {
let mut ret = 0;
for a in (0..4).rev() {
for b in (0..4).rev() {
ret <<= 2;
ret |= self.eval(l.eval(a, b), r.eval(a, b));
}
}
ret as u32
}
fn random<R: Rng>(rng: &mut R) -> Self {
rng.gen()
}
fn to_index(&self) -> usize {
*self as usize
}
fn from_index(i: usize) -> Self {
i as u32
}
fn unary_index(&self) -> usize {
*self as usize & 255
}
fn from_unary_index(i: usize) -> Self {
let r = i | (i << 8);
let r = r | (r << 16);
r as u32
}
fn cifminelse0(&self) -> usize {
const PERM4: [[usize; 4]; 24] = [
[0, 1, 2, 3],
[0, 1, 3, 2],
[0, 2, 1, 3],
[0, 2, 3, 1],
[0, 3, 1, 2],
[0, 3, 2, 1],
[1, 0, 2, 3],
[1, 0, 3, 2],
[1, 2, 0, 3],
[1, 2, 3, 0],
[1, 3, 0, 2],
[1, 3, 2, 0],
[2, 0, 1, 3],
[2, 0, 3, 1],
[2, 1, 0, 3],
[2, 1, 3, 0],
[2, 3, 0, 1],
[2, 3, 1, 0],
[3, 0, 1, 2],
[3, 0, 2, 1],
[3, 1, 0, 2],
[3, 1, 2, 0],
[3, 2, 0, 1],
[3, 2, 1, 0],
];
fn flipped(f: u32) -> u32 {
f & 0xc0_30_0c_03
| f << 6 & 0x30_0c_03_00
| f << 12 & 0x0c_03_00_00
| f << 18 & 0x03_00_00_00
| f >> 6 & 0x00_c0_30_0c
| f >> 12 & 0x00_00_c0_30
| f >> 18 & 0x00_00_00_c0
}
fn permuted(f: u32, p: &[usize; 4]) -> u32 {
let mut invp = [0, 0, 0, 0];
for i in 0..4 {
invp[p[i]] = i as u32;
}
let mut r = 0;
for a in (0..4).rev() {
for b in (0..4).rev() {
r <<= 2;
r |= invp[f.eval(p[a], p[b])];
}
}
r
}
let mut m = vec![*self; 48];
m[1] = flipped(*self);
if m[1] < *self {
return 0;
}
for (i, p) in PERM4.iter().enumerate().skip(1) {
m[i * 2] = permuted(*self, p);
m[i * 2 + 1] = flipped(m[i * 2]);
if m[i * 2] < *self || m[i * 2 + 1] < *self {
return 0;
}
}
m.sort_unstable();
m.dedup();
m.len()
}
}
impl<const N: usize> Function for [[usize; N]; N] {
const N: usize = N;
fn impl_eval(&self, a: usize, b: usize) -> usize {
self[a][b]
}
fn pass_left() -> Self {
let mut r = [[0; N]; N];
for a in 0..N {
r[a] = [a; N];
}
r
}
fn pass_right() -> Self {
let mut d = [0; N];
for b in 0..N {
d[b] = b;
}
[d; N]
}
fn compose(&self, l: &Self, r: &Self) -> Self {
let mut ret = [[0; N]; N];
for a in 0..N {
for b in 0..N {
ret[a][b] = self.eval(l.eval(a, b), r.eval(a, b));
}
}
ret
}
fn random<R: Rng>(rng: &mut R) -> Self {
let mut r = [[0; N]; N];
for a in 0..N {
for b in 0..N {
r[a][b] = rng.gen_range(0..N);
}
}
r
}
fn from_index(mut i: usize) -> Self {
let mut r = [[0; N]; N];
for a in 0..N {
for b in 0..N {
r[a][b] = i % N;
i /= N;
}
}
r
}
fn to_index(&self) -> usize {
let mut r = 0;
for a in (0..N).rev() {
for b in (0..N).rev() {
r *= N;
r += self[a][b];
}
}
r
}
fn from_unary_index(mut i: usize) -> Self {
let mut x = [0; N];
for n in 0..N {
x[n] = i % N;
i /= N;
}
[x; N]
}
fn cifminelse0(&self) -> usize {
let flip = |i: &Self| i.compose(&Self::pass_right(), &Self::pass_left());
let permute_self = |p: &[usize]| {
let mut inv = [0; N];
for i in 0..N {
inv[p[i]] = i;
}
let mut ret = [[0; N]; N];
for a in 0..N {
for b in 0..N {
ret[a][b] = inv[self.eval(p[a], p[b])];
}
}
ret
};
let mut m = vec![*self; (1..=N).product::<usize>() * 2];
m[1] = flip(self);
if m[1] < *self {
return 0;
}
for (i, p) in (0..N).permutations(N).enumerate().skip(1) {
m[i * 2] = permute_self(&p);
m[i * 2 + 1] = flip(&m[i * 2]);
if m[i * 2] < *self || m[i * 2 + 1] < *self {
return 0;
}
}
m.sort_unstable();
m.dedup();
m.len()
}
}
#[test]
fn test_pass() {
fn test_pass_g<F: Function + std::fmt::Debug>() {
let l = F::pass_left();
let r = F::pass_right();
for a in 0..F::N {
for b in 0..F::N {
assert_eq!(l.eval(a, b), a, "a is {}, b is {}, l is {:?}", a, b, l);
assert_eq!(r.eval(a, b), b, "a is {}, b is {}, r is {:?}", a, b, r);
}
}
}
test_pass_g::<u32>();
test_pass_g::<[[usize; 3]; 3]>();
test_pass_g::<[[usize; 4]; 4]>();
}
#[test]
fn test_compose() {
use rand::rngs::SmallRng;
use rand::SeedableRng;
fn test_compose_g<F: Function + std::fmt::Debug>() {
let mut rng = SmallRng::seed_from_u64(42);
let repeats = 1_000_000;
for _ in 0..repeats {
let f = F::random(&mut rng);
let l = F::random(&mut rng);
let r = F::random(&mut rng);
let c = f.compose(&l, &r);
let a = rng.gen_range(0..F::N);
let b = rng.gen_range(0..F::N);
assert_eq!(
c.eval(a, b),
f.eval(l.eval(a, b), r.eval(a, b)),
"a:{} b:{} f:{:?} l:{:?} r:{:?} c:{:?}",
a,
b,
f,
l,
r,
c
);
}
}
test_compose_g::<u32>();
test_compose_g::<[[usize; 3]; 3]>();
test_compose_g::<[[usize; 4]; 4]>();
}
#[test]
fn test_low_effort_discard() {
use rand::rngs::SmallRng;
use rand::SeedableRng;
fn test_low_effort_discard_g<F: Function + std::fmt::Debug>()
where
[(); F::N.pow(F::N as u32)]:,
{
let mut rng = SmallRng::seed_from_u64(42);
let repeats = 1_000;
for _ in 0..repeats {
let f = F::random(&mut rng);
assert!(
!f.low_effort_discard() || !f.is_functionally_complete(),
"Discarded f:{:?}",
f
);
}
}
test_low_effort_discard_g::<u32>();
test_low_effort_discard_g::<[[usize; 3]; 3]>();
test_low_effort_discard_g::<[[usize; 4]; 4]>();
}
#[test]
fn test_specifics() {
// Using the examples from the blog post + = 0, 0 = 1, 1 = 2
let triplets = [
([[0; 3]; 3], false),
([[1; 3]; 3], false),
([[2; 3]; 3], false),
([[0, 1, 2]; 3], false),
([[0; 3], [1; 3], [2; 3]], false),
([[0, 1, 2], [1, 1, 2], [2, 2, 2]], false), // Min
([[0, 1, 2], [0, 1, 1], [0, 0, 0]], false), // Imp
([[0; 3], [1; 3], [0; 3]], false), // Imp composition
([[2, 0, 0], [0, 0, 0], [0, 0, 1]], true), // Tand
([[2, 1, 1], [1, 0, 1], [1, 1, 1]], true), // Modified Tand
([[2, 2, 2], [2, 0, 2], [2, 2, 1]], true), // Modified Tand
([[1, 0, 0], [0, 2, 0], [0, 0, 0]], true), // Modified Tand
([[1, 1, 1], [1, 2, 1], [1, 1, 0]], true), // Modified Tand
([[1, 2, 2], [2, 2, 2], [2, 2, 0]], true), // Modified Tand
([[2, 0, 1], [0, 0, 0], [1, 0, 1]], true), // Pointy Tand
// Experimentally found
([[0, 2, 0], [0, 0, 0], [0, 0, 0]], false),
([[1, 2, 0], [0, 0, 0], [0, 0, 0]], true),
// From the post
([[2, 0, 1], [0, 0, 0], [2, 2, 0]], true),
([[2, 0, 1], [1, 0, 0], [2, 2, 0]], true),
([[2, 0, 1], [2, 0, 0], [2, 2, 0]], true),
([[1, 0, 0], [1, 0, 2], [2, 2, 1]], false),
];
for (f, r) in triplets {
println!("{:?} -> {}", f, r);
assert_eq!(f.is_functionally_complete(), r);
}
}
fn smart_method<F: Function>()
where
[(); F::N.pow(F::N as u32)]:,
{
let amount = F::N.pow(F::N as u32 * F::N as u32);
(0..amount).into_par_iter().for_each(|i| {
let n = F::from_index(i);
let m = n.cifminelse0();
if m == 0 {
return;
}
let r = n.low_effort_discard() || !n.is_functionally_complete();
if !r {
TC.fetch_add(m, Relaxed);
} else {
FC.fetch_add(m, Relaxed);
}
});
CONT.store(false, Release);
}
static TC: AtomicUsize = AtomicUsize::new(0);
static FC: AtomicUsize = AtomicUsize::new(0);
static CONT: AtomicBool = AtomicBool::new(true);
// Change this to [[usize;3];3] for n=3
type T = u32;
fn main() {
// Fluff
let start = std::time::Instant::now();
let amount = T::N.pow(T::N as u32 * T::N as u32);
let pb = ProgressBar::new(amount as u64);
pb.set_style(
ProgressStyle::default_bar().template(
"{wide_bar:.green/red}\n{pos}/{len} - {percent}% - {per_sec} - {eta} - {msg}",
),
);
let t = thread::spawn(move || {
while CONT.load(Acquire) {
thread::sleep(std::time::Duration::from_millis(100));
let t = TC.load(Relaxed);
let f = FC.load(Relaxed);
pb.set_position(t as u64 + f as u64);
pb.set_message(format!(
"Ratio at {}/{} = {:.5}",
t,
t + f,
t as f64 / (t as f64 + f as f64)
));
pb.tick();
}
});
// Call
smart_method::<T>();
// Fluff
match t.join() {
Err(_e) => {
println!("Failed to join ui-thread :/");
}
_ => {}
};
let t = TC.load(Relaxed);
let f = FC.load(Relaxed);
println!(
"Ended with {} universal gates and {} non-universal gates. Ratio is {}/{} = {:.5}",
t,
f,
t,
t + f,
t as f64 / (t as f64 + f as f64)
);
println!("Took {:?}", start.elapsed());
// Remember to reset TC, FC and CONT if you want to call again
}
cargo.toml
[dependencies]
itertools = "0.10"
rand = {version="0.8", features=["small_rng"]}
rayon = "1.5"
indicatif = {version = "0.16", features = ["rayon"]}
Takes around 20 minutes on my machine™. The actual code is not that interesting, maybe with the exception of the unary completeness check, which uses a buffer with two non-overlapping linked lists, to form a very efficient deduplicated queue + set data structure.
n=5?
For n=5
you basically need a new idea (or a lot of computing power). Checking each gate individually becomes impractical (if you could do it in one cycle, it would still take two years). If someone manages to calculate n=5
, I'm happy to forward Bubblers +500 bounty to them.
1/e
. The fact that Euler’s constant shows up here is amazing." \$\endgroup\$1/e
result, you definitely shouldn't use this link sci-hub.ee/10.1002/malq.19790251903 because I definitely don't condone such copyright infringement :) \$\endgroup\$https://doi.org/10.1002/malq.19790251903
\$\endgroup\$