consider a brick in N dimensions composed of unit hypercubes. for example, let N=3. each unit cube is labeled 0 or 1, subject to the following monotonicity constraints:
- let A = (a[1], a[2], a[3]) be the coordinates of one unit cube and B = (b[1], b[2], b[3]) be the coordinates of another unit cube. if for all i in {1,2,3}, a[i] <= b[i], then it must not be the case that the label at A is 1 and the label at B is 0.
- Similarly, if A >= B, then it must not be the case that A = 0 and B = 1.
is constraint 2 necessary, or does it logically follow from 1 ?
how many valid labelings of the cubes in the brick are there?
I suspect the number is much less than total number of possible unconstrained labelings. what is a compact way of describing a coloring, more compact than giving the label of every unit cube?
inspired by trying to generalize Conway's Game of Life cellular automata to 3D. let neighbors through a corner of a cell, edge, and face each contribute a different amount of influence to the "number of neighbors" a cell has. we want more generality than a weighted sum, but we want to keep rules to be monotonic: for example, if a threshold has been crossed for "too many neighbors", then it remains crossed for "more" neighbors. (previously, 2D.) in 3D, there can be 0 to 8 corner neighbors, 0 to 12 edge, and 0 to 6 face. these together which define a 9 x 13 x 7 brick. label each of its 819 unit subcubes "OK" or "too crowded". without the monotonicity constraints, there are 2^819 possible labelings, far too large to evaluate all of them by brute force.
2D: 5 x 5 brick (0 ... 4 edge neighbors and corner neighbors), so 2^25 = 32 million unconstrained labelings. counting those which satisfy the monotonicity constraints can be done by brute force. finding those which yield "good" cellular automata is harder.
future work: 3 labels for unit cubes: "too isolated", "OK", "too crowded". we need to come up with a new definition for monotonicity among the 3 ordered labels, probably not difficult. a second brick describing births from dead cells. perhaps constrain the conditions suitable for birth to be a subset of conditions suitable for life.
No comments:
Post a Comment