[<<][math][>>][..]Tue Jun 9 14:55:19 CEST 2009

Inspired by the idea from the Sheep synth that only XOR and AND are interesting ways of combining oscillators, here is some investigation of the why of that. There are 2^4 boolean functions that map 2 inputs to one. There are only a couple of interesting ones after you remove 0/1 morphism. In the following, the squares indicate their Karnaugh maps[1]. | A | 0 1 ----+-------- B 0 | . . 1 | . . Simply looking at the Karnaugh maps already suggests a number of equivalence classes: Select class: 1/3 NAND OR => <= 1 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 AND NOR N=> N<= 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 Transform class: 2/2 diag XOR <=> 1 0 0 1 0 1 1 0 Drop class: 2/2 non-diag A B !A !B 0 1 0 0 1 0 1 1 0 1 1 1 1 0 0 0 Ignore class: 4/0 0 1 0 0 1 1 0 0 1 1 Each class is a set of boolean function which is closed under inversion of one of the 2 inputs, or the output of the function. The classes can be constructed from a single representative f. With i_o, i_a, and i_b inversion or identitiy, the functions g(a,b) = i_o(f(i_a(a), i_b(b))) make up the class. The maximum number of elements is 2^(n+1), which occurs when all combinations of inversion and identitiy yield a distinct function. Let's define an "interesting" function to be the ones that belong to large equivalence classes. In this sense only AND and its symmetries are interesting. Note that this is => (implication). Putting it as "only implication is interesting" makes it sound a bit more profound. Instead of looking at inversions, it's also possible to look at input permutations. For the 2->1 case this seems to be a closed operation in all the classes (mirror around the diagonal). In fact, in the 3->1 case we need to include permutation symmetry. So what about 3->1 functions. Is there a similar way to classify them as interesting/boring using the same classification (inversion + permutation). There are 2^(2^3) = 256 such boolean functions. They can be visualized as 2x2x2 Karnaugh cubes or folded open to one side as a flat map: | AB : | 00 10 : 11 10 ----+--------:------ C 0 | . . : . . 1 | . . : . . : fold For 3->1 functions one just needs to look at the morphisms of the 2x2x2 binary cube. With what we find from the 2->1 case, there are some things we can expect: 1. single select (3AND, 3OR, ...) 2. embeddings of the 2->1 functions 3. irreducible structures Here 3. is expected to be an analogue of non-separable convolution kernels: increasing dimensionality introduces new structures that can't be written simply in terms of lower-dimensional ones. Looking at the 2x2x2 binary cube and trying to fill it with a pattern that can be oriented in many different ways makes me think of an L-shape like this: x x . . x . . . It can be placed in one of 8 corners, with each taking 3 possible orientations, leading to 24 symmetries. However, this one is "flat". It is independent of one of the inputs. Rotating one plane of the the 2x2x2 cube 90 degrees wrt to another one (like you would do with a rubik's cube) gives this configuration: . x x . x . . . Which is no longer flat. It is like an L that maximally occupies space in the cube. This turns out to be the function (class) that's used in Wolfram's rule 110[2]. These two functions are in distinct classes (they difference is _essential_ as the former doesn't use one of the inputs, while the latter does). However, they have the same number of symmetries: 8 x 3 x 2 = 48 This follows from 8 different positions (the corners of the cube), 3 different orientations to fix one of the other 3 points at, and the inversion of the pattern. This might not be a coincidence. Are they maybe lines and planes of a projective plane, thereby being dual? For 3-input, binary, 1D CAs, Wolfram identifies 88[3] fundamentally different rules. Why are there so many? For CAs the order and polarity matters a great deal. Due to recursive application, there is little more than left-right symmetry (256->128) + some symmetry in degenerate cases. Anyways. How to look for such "interesting" functions automatically? Let's look at the interpretation of functions in this class. After all, this is simple logic, so there is natural-language intuition to connect to. _ __ _ _ AB AB AB AB C . x x . C x . . . (A & B & C) | ((~B & ~C)) | ~(B | C) Hmm not much there.. What practical predictions to make? Not more than hunches really. I suspect that a representative of this function will lead to an interesting modulation scheme for a 3-oscillator synth. This can probably be generalized to higer dimensional functions. Does giving up permutation give special status to the individual functions? This might also be usable in sound synthesis, where one of the modulators has a different function than the other sounds. [1] http://en.wikipedia.org/wiki/Karnaugh_map [2] http://mathworld.wolfram.com/Rule110.html [3] http://www.wolframscience.com/nksonline/page-57-text?firstview=1

[Reply][About]

[<<][math][>>][..]