Wednesday, August 12, 2015

Changoite (sodium zinc sulfate)

Phew, I am getting more and more into crystal growing last weeks. Few more specimens will be ready soon.

Crystals of synthetic changoite, double sulfate of sodium and zinc.

Here are some fresh crystals of a double sulfate of sodium and zinc with formula \(Na_2Zn(SO_4)_2\cdot4H_2O\). Natural variety of this compound is known as mineral сhangoite. It is not well known among crystal hobbyists, but definitely worth trying: it easily forms large, well-wormed single crystals; the crystals are very stable on air and not prone to dehydration; and finally, source compounds (sodium and zinc sulfates) are cheap and available. Remaining photos of this compound are in this gallery, and all my crystal growing photos are here.

Shape and size of the crystals of sodium zinc sulfate.

Crystals are colorless, monoclinic, having thick tabular form with multiple facets. Top faces have form of a distorted octagon, very close to a rectangle. On side faces, striations are sometimes visible. Tabs are slightly slant.

Side view, striations are visible on the biggest crystal.

My crystals are rather cloudy. It would be really great to grow absolutely transparent crystals (by the way, I am now growing crystals of another zinc compound: zinc ammonium acetate, and they are crystal clear). Probably, additional recrystallization step could improve transparency.

Obtaining compounds

To grow crystals of changoite, prepare solution containing equal molar amounts of zinc and sodium sulfates. Indeed, both of these compounds can be bought in a chemicals store. However, they can also be prepared from commonly available materials.

Sodium sulfate (Na2SO4)

From sulfuric acid

The second easiest way to obtain sodium sulfate (after buying it) is reaction of sulfuric acid (acid electrolyte) with baking soda, according to the equation:

$$2NaHCO3 + H_2SO_4 \rightarrow Na2SO4 + 2H_2O + CO_2 \uparrow$$

Take some acid and add small portions of soda until it stops fizzing. Looks simple, but in practice it is harder than it seems. Fizzing is very vigorous, so soda must be added really carefully to avoid spilling of acidic foam. Always perform this reaction over some larger vessel and wear eye protection! Moreover, gas bubbles are producing thin acidic fog, which is surely not good for health and surrounding objects. I used a piece of cloth to cover the reaction vessel.

Upon drying, solid sodium sulfate decahydrate, \(Na_2SO_4\cdot10H_2O\) is obtained from the solution.

From copper sulfate

A safer (though more expensive) alternative is reaction of some metal sulfate with soda. For example, with copper sulfate:

$$CuSO_4 + 2NaHCO_3 \rightarrow Na_2SO_4 + H_2O + 0.5Cu_2(OH)_2CO_3 \downarrow + 0.5CO_2\uparrow$$

Make copper sulfate solution and add soda by small portions until reaction (fizzing and sediment formation) stops. Remaining transparent solution would contain sodium sulfate. Do not throw away blue-green sediment of basic copper carbonate, it can be used for preparing other interesting compounds and beautiful crystals, such as copper acetate.

The (questionable) advantage of this method is that it does not use dangerous acid.

Zinc sulfate (ZnSO4)

Zinc sulfate is a colorless solid, soluble in water. From water solutions, it crystallizes as heptahydrate: \(ZnSO_4\cdot7H_2O\). Besides the chemicals store, it can be sometimes bought as a fertilizer, since zinc is an important micro-element. However, the amount is usually small. It also can be prepared in several ways.

Preparation from zinc oxide (ZnO)

Zinc oxide ZnO is a white powder insoluble in water, used as pigment "zinc white". I bought a big jar of white watercolors and washed it several times with water to remove soluble glue components. To prepare sulfate, dissolve oxide in sulfuric acid:

$$ZnO + H_2SO_4 \rightarrow ZnSO_4 + H_2O$$

This reaction is quite exothermic. Crystalline heptahydrate is obtained by cooling and evaporation.

From metallic zinc

If you have metallic zinc, it can be turned into sulfate in several ways. The straightest one is to dissolve zinc in sulfuric acid:

$$Zn + H_2SO_4 \rightarrow ZnSO_4 + H_2\uparrow$$

Beware of acidic fog, always cover the reaction vessel. Also, if zinc or acid are not pure, badly smelling reduction products can form, so ensure good ventilation.

Safer, though more expensive method is, again, via copper sulfate. Put zinc metal into solution of copper sulfate, and metal will quickly cover with red porous metallic copper:

$$CuSO_4 + Zn \rightarrow ZnSO_4 + Cu \downarrow$$

Remaining clean solution is zinc sulfate.

Preparing the solution

The solution must contain equal molar amounts of both sulfates. For solid hydrated compounds, the proportion is: 1 part of \(ZnSO_4\cdot7H_2O\) per 1.12 parts of \(Na_2SO_4\cdot10H_2O\) (by weight of solid compounds).

To grow crystals, solution must be saturated. Both compounds have very high solubility, so add only enough water to completely wet and cover the components. If after stirring and mild warming they are not completely dissolved, add a bit more water. Resulting solution should be transparent and slightly viscous.

Growing

I used the usual growing procedure: slow evaporation. First let the solution to evaporate for a day or 2. Eventually, small rectangular crystals appear (if they are not appearing, then solution is too dilute). Harvest several most clean and well-formed seed crystals, attach them to a thread (I use thin nylon filament, and attach crystals to it by the double overhand knot).

Then suspend seed crystals in the solution and wait patiently.

Side view, striations are visible on the biggest crystal.

Safety

Zinc is important element for life, but only as a micro-element. In big amounts, it is toxic. Swallowing 1-2 grams of zinc sulfate causes nausea, and 10-20g can be even deadly. However, with basic precautions, such as washing hands and not trying to taste the compounds, it is totally safe. In small amounts, such as 100mg/day, zinc is prescribed as a drug.

Thursday, June 25, 2015

The percent of valid formulae in random strings

In the solution to the Arithmetic hide and seek problem, I mentioned a practical observation that among all strings composed of 18 characters "0123456789+-*/^k()" roughly 20% are valid formulas, and conjectured that it is true for arbitrarily long strings. This appears to be wrong: the percent gradually converges to 0.

Proof

Let, for some formal language, \(n_k\) is the number of words of length k. Then Z-transform of the sequence \(n_0,n_1,...\) is called its growth function \(f(z)\). (Apparently, it is common to use non-standard Z-transform by positive powers of z for growth function; I instead use the usual negative transform). For a regular language, that is set of strings, accepted by some finite automaton, growth functions are always rational and can be calculated by a simple formula:
$$f(z) = e(zI - A)^{-1}s,$$ where A is transition matrix, showing number of ways to get from state i to state j; e is row matrix of accepting states (1 for accepted 0 otherwise); and s is column matrix of initial states.

Unfortunately, formulas are not a regular language, because accepting automaton must have infinite number of states to balance braces. So instead of the exact count, I would estimate it by upper and lower bounds.

Lower bound

Lower bound is given by the automaton, that accepts valid formulas without braces.

Automaton, accepting formulas without braces. Blue are accepting states.

To better match grammar in my solution, it disallows leading zeros in integers. States are named by the last accepted character; blue color indicates accepting states. State "OP" is achieved after consuming a binary operator. If 5 states are ordered as [OP,0,1-9,0-9,K] then the transition matrix is:
$$A = \left[\begin{matrix} 1 & 5 & 5 & 5 & 5\\ 1 & 0 & 0 & 0 & 0 \\ 9 & 0 & 0 & 0 & 0\\ 0 & 0 & 10 & 10 & 0\\ 1 & 0 & 0 & 0 & 0 \end{matrix}\right]$$ which, with \(e=(0,1,1,1,1)\) and \(s^T=(1,0,0,0,0)\) gives growth function:
$$f_{lower}(z) = \frac{11z^2-20z}{z^3-11z^2-45z+100}.$$ After inverse transform, this gives an expression for number of valid strings of length k:
$$n_{lower}(k) = 0.623\cdot(-4.399)^k+0.02467\cdot{1.654}^k+0.598\cdot{13.745}^k. $$

Upper bound

To get upper bound, consider an automaton, accepting strings with unbalanced braces, only requiring that operator is not following an opening brace, and number not following a closing brace. Such strings are clearly a superset of all valid formulas.

Automaton, accepting formulas with unbalanced braces. Blue are accepting states, "op" is one of 5 binary operators "+-*/^".

Its transition matrix, for state ordering (OP, 0, 1-9, 0-9, ")", K) is:
$$A = \left[ \begin{matrix} 2 & 5 & 5 & 5 & 5 & 5\\ 1 & 0 & 0 & 0 & 0 & 0\\ 9 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 10 & 10 & 0 & 0\\ 0 & 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 0 & 0 & 0 & 0 \end{matrix} \right]$$ which gives growth function:
$$f_{upper}(z) = \frac{11z-20}{z^3-13z^2-23z+80}$$ and the number of accepted strings is:
$$n_{upper}(k) = -0.6339*(-3.06)^k-0.003648 \cdot (1.8383)^k+0.6375 \cdot {14.2217}^k $$

Conclusion

Thus, the number of correct formulas grow not slower than \({13.745}^k\) and not faster than \({14.2217}^k\) where k is string length. Since total number of strings is \(18^k\), the percent of valid formulas is gradually decreasing with rate between \({0.7636}^k\) and \({0.7901}^k\). Moreover, \(k \approx \log_{18}t\), where t is current string index in shortlex ordering. Using this, asymptotic percentage bounds can be written as: \({0.7636}^{log_{18}t} = t^{-0.0933}\) and \(t^{-0.0815}\). Slow decrease rate explains why it was not apparent in the numeric test results.

Despite that my initial conjecture on percentage of valid formulas failed, the conclusion on growth rate is nevertheless correct, since number of formulas grows exponentially with length.

Note on Z-transform

Articles I have seen define growth function by means of non-standard Z-transform by positive powers of z:

$$f(z) = \sum_{i=0}^\infty a_i z^i.$$

Wikipedia calls it "Geophysical definition". I here took a regular definition applied in control systems and signal processing, since it allows me to use standard computer algebra tools. Its another advantage is that bases of the exponentials in expression for string count are just negated roots of the denominator polynomial. Traditional growth functions may be obtained by substituting \(z'=1/z\).

Sunday, June 14, 2015

Crystal growing: Mohr's salt

Some fresh crystals of the common laboratory preparate of iron (II): Mohr's salt, or ammonium iron sulfate hexahydrate (NH4)2Fe(SO4)2·6H2O. (Whole gallery)

Some crystals of Mohr's salt. Cell size is 5mm.

Among other iron (II) compounds it is notable for its stability when exposed to air. Most other salts are easily oxidized by air, but Mohr's salt can be stored for years without notable changes (by some reports). This (together with non-toxicity and availability) makes it a good material for hobby crystal growing.

Obtaining

Surely, the easiest way to get Mohr's salt is to buy it in the chemicals store. It is the most boring way too.

I prepared my salt from more common compounds:

  • Iron (II) sulfate Fe2SO4 from the gardener's store,
  • Sulfuric acid H2SO4, used as electrolyte for acid accumulators,
  • And ammonia NH3 from the drug store, in a 10% aqueous solution.

First step was to prepare ammonia sulfate from the NH3 solution and sulfuric acid, by equation:
$$ 2NH_3 + H_2SO_4 \rightarrow (NH_4)_2SO4 $$
The reaction is very exothermic, and must be done carefully. With 10% NH3 and 43% H2SO4, temperature reached 80-90°. Moreover, NH3 is evaporating quickly from the hot solution, while the reaction is not finished. So wear goggle, do it outside and ensure that the reaction vessel will not crack of sudden temperature change. I added acid with a small excess.

Then I added Fe2SO4·7H2O to the hot solution. After stirring, everything dissolved, giving brown solution (pure compound is green, brown color is caused by Fe(III) contamination). After evaporating it partially and cooling, light-green crystals of Mohr's salt precipitated.
$$(NH_4)_2SO_4 + FeSO_4 \cdot 7H_2O \rightarrow (NH_4)_2Fe(SO_4)_2 \cdot 6H_2O \downarrow + H_2O $$
To grow bigger crystals, I used them for traditional growing procedure with a glass and a thread.

Three biggest crystals

Growing

The compound easily forms large, pale-green crystals. I used slow evaporation technique, with a seed crystal suspended on a thin nylon thread. Crystalline Mohr's salt has good resistance to oxidation by air, but its solution is more prone to it. Initially light green solution gradually becomes brown in a couple of days. To reduce oxidation, I added some excess of the sulfuric acid to it. There are also reports, that additional acid improves crystal clarity too.

Crystals are monoclinic, their form depends on impurities and additions. When solution is fresh, flat tabular crystals grow.

Crystals grown from the fresh solution has flat tabular form.

From the older solution, contaminated with Fe3+ ions, more elongated crystals are growing.

Crystal grown from the older solution is elongated.

Despite all my efforts, I failed to grow crystals with even perfect faces. In all cases, faces had irregularities crystals were not entirely transparent. I tried to add glycerol (which gives good results with copper sulfate), which caused flattening of crystals and slightly improved transparency.

Safety notes

The compound itself is generally safe and low toxic, its pure form is used as iron supplement for humans. Acidic solution is corrosive and irritant. The preparation procedure I used, involving hot acid and ammonia could be dangerous. Also, spilled solution leaves permanent stains on everything, handle it with caution.

Sunday, June 7, 2015

A rainbow on the asphalt

It was a sunny summer day. I was walking to the bus stop when a rainbow, not in the clean sky, but on the gray asphalt of the road. I stopped to look better, and it almost disappeared. It was best visible in motion.

That's what I saw when I stopped. But where is the rainbow…

After a closer examination, it appeared that road workers were updating road surface marking and spilled some glass spheres, used to add retro-reflectivity to the marking. White sugar-like thing on the photo above is made of these small glass spheres. And just like water drops create rainbow in the sky, glass drops made rainbow on the road.

I wanted to make a better photo, but big contrast between the white glass "sand" and dark asphalt made rainbow hardly visible on a still photos. So I decided to try to average-out the noise, using the fact that rainbow observed position does not move when observer moves.

All frames taken, camera position is slightly different on every frame, but the rainbow is on the same place.

It's a common way to deal with noise in measurements: make many measurements and then average them. Since noise is random, it will become become weaker, as the number of measurements grows. (Noise amplitude is inverse proportional to the square root of the measurements number).

So I made 15 photos, moving a little between frames, and averaged them.

All 15 pictures averaged with Gimp.

Here it is! There is something unsettling in this picture… I intentionally made all photos in the same pose to use the shadow for aligning images, and on the merged photo black shadow makes strange view on the blurred road.

Color contrast exaggerated to make rainbow more prominent.
Finally, some circular blur added to reduce noise and show the rainbow clearer.

Monday, June 1, 2015

Arithmetic hide-and-seek: solution

Here is my solution for the problem of arithmetic hide and seek. Please read it if you prefer to solve the problem by yourself.

Many users on G+ (comments thread) and in the comments has correctly solved it and additional questions. The first ones were Suhail Sherif, Brent Werness and Heffalump Horton. Hope that the problem entertained you.

Solution

First note, that if Angel knows the formula, then he can win instantly, whatever the current turn number \(k\) is. To do this, just substitute \(k\) to the formula and obtain exactly, where Demon hides. Indeed, Angel does not know the formula. However, it is not a problem, since the set of possible formulas is countably infinite. This means that it is possible to build an infinite sequence of formulas that contain every possible formulas (moreover, this can be done explicitly, see below). Angel can use this sequence to check formulas one-by-one, on each turn substituting current turn number to \(k\) and checking for Demon. Sooner or later, Angel will try the formula, Demon has conceived and win the game (though he can win earlier, by pure luck). This gives the winning strategy.

Explicit solution

The above solution could be enough for a mathematician, but as a programmer, I wanted to write down the explicit algorithm. To do this, first the sequence of all formulas should be built. It can be done in a multitude of ways, some of them are more computationally effective (faster and contain less duplicates) than others. For the proof-of-concept code, I used the simplest approach.

Using the usual linear notation, every allowed formula can be written as a string, composed of characters “0123456789+-*/^()k” (where ^ stands for powering). It is easy to enumerate all possible strings. A simple way is shortlex order: first all strings of 1 character, then of 2 characters in alphabetic order and so on. By excluding non-valid expressions, one gets a sequence of all possible formulas, from the shortest ones to the longest.

I implemented this enumeration algorithm in Python. To check whether the string is a valid formula it uses a simple parser, written with pyparsing library. To reduce numbers of duplicates (equivalent formulas), it disallows numbers starting with 0, except for the 0 itself. The implementation is not breathtakingly fast, but fast enough to enumerate expressions up to 5 characters in a reasonable time.
Source code is on Github: dmishin/arithmetic-hide-and-seek.

Here are few first formulas and corresponding search attempts done by Angel.

Turn kFormula fValue f(k)
100
211
322
1099
11k11
121010
1019999
102-00
47629512
4772k3'902'185'687'894'990'289'226'996'537'241'457'882'185'747
1729kk1.40457…×105598

The sequence of attempts behaves erratically, but its amplitude grows very fast. At the step \(k=320282\), the formula \(k^{k^k}\) is reached, which evaluates to tremendous \(320282^{320282^{320282}} \approx 10^{10^{1763323.7111}} \), a number that is so big that to write down even the number of digits in it one needs 1'763'324 digits.

This sequence is shown on the graph below. The graph uses logarithmic vertical scale because of the fast growth rate. Positive values are show in red, and negative in blue. Note that not all actual data points are shown, some values are so large, that even in the logarithmic coordinates the rest of the graph will be too small.

First 10000 search attempts of Angel, using the implementation above.

Growth rate

How fast the amplitude of Angel's search grows? Quite fast, actually. Even the logarithmic plots above do not properly reflect it, since the highest data points are not shown on them.

For the proposed implementation, growth rate is easy to estimate. Quite obviously, when \(k\) is large enough, the biggest possible values have form k^k^…^k. Since the percent of valid formulas remains roughly constant at about 20% (a rather curious fact, actually. Is it true, and what is the limit value? I don't know UPD: Actually, it is not true, but number of formulas nevertheless grows exponentially), the length of the string grows approximately as logarithm of the turn number: \(L ~ \log k\). Therefore, maximum value grows as k^k^k^… (log k times). This can be written as: \(^{\log k}k\) (see tetration) or, with Knuth's up-arrow notation, as \(k\uparrow\uparrow\log k\).

Growth rate, however, depends on the enumeration method chosen. By rearranging formulas, it is always possible to make growth faster.

It is also possible to decrease growth rate. For example, it can be done by “diluting” sequence with growing sequences of zeros. However, there is a lower limit: the growth rate should be strictly faster than of any fixed height power tower: \(k^{k^{k^\ldots}} = k\uparrow\uparrow n\).

Angel's winning strategy, first 50000 steps. Slightly zoomed to show steps with smaller amplitude.

Extensions

Here are few thoughts on possible extensions of the problem, with a result that I was not aware of.

Extension first: more operators

It can be easily seen that the set of allowed operators is rather arbitrary. It can be expanded with arbitrary number of additional operators, functions or constants like \(\pi\).

Extension second: Turing machine

But what if instead of a formula, Demon uses a Turing machine: an ideal computer, capable to implement any algorithm. This change the game.

At first, it may seem that nothing has changed significantly. The set of all programs is countable and enumerable, but there is one obstacle … It can be formulated as a theorem:

Theorem 1: weaker Demon

If a winning strategy for the Angel exists, and Demon's computation method is expressive enough (see below), then Angel's search sequence is not expressible by Demon.
Here expressive enough means that for every expressible formula \(f(k)\), there is another expressible formula \(f_1(k)\), such that \(f_1(k) \ne f(k) \forall k\). For example, \(f_1(k)=f(k)+1\). The rules from the original problem are, indeed, expressible enough in this sense.

The proof is by contradiction:suppose that Angel's sequence (winning strategy) \(A(k)\) can be implemented by Demon. Then he can implement sequence \(A(k)+1\), which is always 1 step before Angel. Then Angel can't win. Contradiction.

Theorem 2: slower Demon

The above theorem is a corollary of another theorem:

Growth rate of Angel's search sequence is strictly faster than growth rate of any sequence that Demon can compute.
This theorem can also be proven by contradiction.

So, back to the Turing machines. Now it is clear that if Demon uses an algorithm instead of formula, then Angel's sequence can't be calculated by an algorithm: it is uncomputable. This does not means that the winning strategy does not exist: we just can't write an algorithm that produces it.

However, if Angel (with some divine help maybe) can obtain a Turing oracle - an entity that can determine, whether any given Turing machine hangs or terminates, then the situation changes. Using the oracle, Angel can win with the following algorithm:

k := 1
for each algorithm A:
    if oracle says that A(k) terminates, then:
        search Demon at point A(k)
        k := k + 1
 

Since oracle can not be implemented algorithmically, Demon can't go a step before angel and can't escape.

Go deeper

So what if we go further, and give oracle to Demon?

Now Angel can't catch him for sure even with the help of an oracle. Since the set of all oracle-enabled algorithms is also enumerable, it essentially proves that Turing oracle is not enough to solve termination problem of an algorithm with oracle!

Thus, winning strategy, while existing in some sense, can not be computer neither by an algorithm nor by an algorithm with oracle. To catch Demon, Angel needs something more powerful: a second order oracle.

This race or arms can be extended indefinitely, defining an infinite hierarchy of oracles.

Saturday, May 23, 2015

The game of arithmetic hide-and-seek

Angel tries guess where Demon hides now.

Here is a mathematical problem I've made recently. It could seem unsolvable at first, but there is a solution, and a simple one!

Update: see solution here.

The problem

Angel and Demon are playing the game of arithmetic hide-and-seek. The game is played on a linear "field" of numbered cells, going infinitely both in positive and negative directions.

Before the play, Demon conceives a formula, using 5 operations: addition \(+\), subtraction \(-\), division \(/\), multiplication \(*\) and powering \(x^y\); any integer numbers and variable \(k\). He never shows that formula to Angel.

Some of possible formulas are: \(666+k\); \(k^2-3k\); \(k^k\); \(2^k/k\) or just \(5\).

The game is played in turns. On each turn, first Demon moves. He substitutes current turn number for \(k\) in his formula. I.e. \(k=1\) on the first turn, \(k=2\) on the second etc. Then he evaluates it, rounds the result down to the nearest integer (example: 17/5 = 3.6 rounds to 3), and hides in that cell.
If the formula has no numeric value, like \(1/(k-5)\) when \(k=5\), then Demon hides in the cell 0.

Then Angel takes action. He does not see Demon, but on each turn he can check one cell. If he finds Demon there, then Angel wins. Otherwise, the game continues to the next turn.

Clearly, there is no way for the demon to win, but he could hope to hide forever.

Propose a winning strategy for Angel, and thus show that Angel can always win in a finite number of attempts.

Additional questions

  1. Estimate the asymptotic growth rate of the distance of Angel's search.
  2. Is the problem solvable, if instead of a formula Demon uses an ideal computer (Turing machine?)

Sunday, March 8, 2015

Crystal growing: potassium alum

Potassium alum, an old favourite in crystal growing at home. In childhood, I read a book on crystals, and it mentioned this compound a lot. Unfortunately, alum was not available at my place, and I could only look at the pictures.

$$KAl(SO_4)_2\cdot12H_2O.$$
Formula of the alum, showing that it is a double salt: sulfate of potassium and aluminium.

Well, now I decided to make a few crystals and they grew great. Very transparent (though not without soem defects, alas) sparkling octaheders. Just look at them (full gallery).

With a scale to show size.
Transparency check
In front ob my lovely orthographic dictionary. The word in the center says "alum".

Growing

I used the simplest, traditional growing method: slow evaporation. Prepare a glass of saturated solution, make a small seed crystal (I poured a bit of solution to a glass and let it evaporate for a day) and suspend the seed on a thin thread (I used a very fine synthetic fiber, almost invisible). Then wait patiently - that's all.

Common problems in growing alum crystals:

  • Crust formation: crystalline crust grows slowly on the sides of the glass, depleting the solution and slowing down crystal growth. Solved by moving crystal to a clean glass (crust can be re-dissolved and used again).
  • Mold growth: some molds and bacteria can thrive in concentrated alum solution, dimming the crystal and reducing evaporation. I solved it by adding a few drops of iodine tincture.

Safety

Alum is a generally safe compound, so no special measures are required. Remember though that even table salt can become a poison if consumed too much.

On my hand. It's totally safe.

Sunday, January 25, 2015

Less trivial conserved quantities in binary block CA

Binary block cellular automata with Margolus neighborhood

A contrived title, but the thing is simple: consider an infinite field of square cells, where each cell can be dead: 0 or alive: 1 (thus binary). Now define the following evolution rule:

  • Subdivide board into 2x2 cells. Each cell can be in one of 16 states.
  • Transform every cell independently, using the same transformation function.
  • Alternate subdivision by shifting the grid by (1,1).
This subdivision scheme is called Margolus neighborhood, and the whole system defines a cellular automaton.

Block cellular automata are interesting, because it is easy to make them reversible: just ensure that block transformation function is reversible (i.e. it is described by a transposition of 16 states). A well studied examples or rules are Critters, Billiard Ball machine, miscellaneous gas automata. My personal interest is the Single rotation rule.

Conserved quantities

Having done few experiments it is easy to notice that rules for such automata generally fall into 2 categories:

  1. those that preserve population (BBM, Critters*, Single Rotation)
  2. and those that don't (Tron and most random rules).
(*) in the first group, there is a sub-group of rules that invert population on each step (Critters is a good example), thus population restores every 2 steps. Such rules can be effectively simulated with 2 non-inverting rules applied alternatively.

Rules without population conservation almost inevitably exhibit chaotic growth for the most initial patterns. (A slightly paradoxical observation: for all reversible rules, there is no difference between evolution forward and backward in time, but a random initial pattern almost surely grows, like if there is a chosen direction of time).

Small initial pattern in the rule without cell conservation. (Try live.)

The field tends to reach the state of maximal entropy, where roughly 50% of all cells are dead and 50% are alive.

Rules with conservation behave very different: they also strive to increase entropy, but this trend is limited by the conservation laws. Most interesting rules are in this class: Critters, BBM, Single Rotation.

Rules with conservation (Single Rotation). Entropy growth is limited, complex emergent behavior appears. (Try live.)

Less trivial conserved quantities

So my question was: are there any rules that have some conserved quantity other than number of alive cells. And the answer is yes. There are at least 2 ways to construct such rules.

Weighted population

It is easy to notice that in the Margolus neighborhood scheme, sum cells of the board are always on the diagonal of the block, and others are on the anti-diagonal (black and white cells of a chessboard). We can assign different weights to white and black cells, and find a rule that preserves this modified weight.

There are 3 significantly different ways to assign positive weights to the "black" \(w_b\) and "white" \(w_w\) cells:

  1. \(w_b = w_w = 1\): both weights are the same, this is the usual population.
  2. \(w_b = 1, w_w = 2\): a non-trivial case.
  3. \(w_b = 1, w_w > 2\): equivalent to counting black and white cells separately, because 2 black cells in a block can never outweigh any white cell.
In rules that preserve the (1,3) weight, populations of cells on black and white cells of the board are not interacting, so the only non-trivial case here is (1,2) weighted sum.

The (1,2) weighted population of a block takes values in range [0, 6]. Block states are divided by it into 7 groups of equal weight:

7 groups of block states by their weighted population.

Any rules that replaces block with another block of the same group, would preserve weighted population. Moreover, a rule that replaces block of weighted population \(w\) with block of w.p. \(6-w\), would be analog of the population inverting rule.

Some rules

The rules can be built by combining transpositions of states in the same group. It should be noted that most rules are anisotropic: they are not invariant to rotation bu 90°, patterns in such rules can't be rotated, only translated.

“Split and merge billiard&rdquo

This rule is defined by the following lookup table: [0,6,4,3,2,5,8,7,1,9,10,11,12,13,14,15], itis illustrated by the diagram below.

Substitution diagram for the split and merge billiard rule. Other block states remain unchanged.

It is an analog of the “Billiard Ball Machine” rule, but two anti-diagonal balls may merge on collision and create one diagonal.

Split and merge billiard animation. Try it live.

Rule [15,14,13,10,11,3,9,1,7,8,12,2,5,4,6,0]

This rule inverts weighted population on each step, thus after 2 generations weighted population is restored. This rule is relatively rare example of its family, because it have spaceships, moving in both directions along both diagonals (of course, these are different spaceships). Several tens minutes of random search discovered 35 different moving patterns.

Multiple spaceships. Try it live.

Other rules with spaceships

There is plenty of rules, supporting spaceships. Some of them are:

Negative weights

It is also possible to assign negative weights to the block cells. In rules preserving resulting invariant, total number of alive cells can grow infinitely, while invariant remains constant. This usually makes such rules “explosive&rdquo: most initial patterns grow ore or less chaotically.

An easy way to produce such rules is to take a rules with positive weights and consider it acting on a board, where half of cells is alive, forming a chessboard pattern. Then build a rule, describing evolution of the XOR between some field and the infinite chess pattern. For example, for "single rotation" resulting rule is [0,13,2,3,4,5,6,7,11,9,10,1,12,8,14,15]. It is partially "explosive", but supports some simple spaceships, moving along main diagonal.

Monday, January 12, 2015

Now in 3D (Single Rotation)

I am proud to present my most complex Three.js application so far: 3D visualization of the Single Rotation cellular automaton.

Screen-shot of the program display. Grey lines form indestructible wall, attacked by multiple patterns smashing on it.

What you see on the above picture are world lines of the cellular automaton cells, as they move according to the Single Rotation rule. World lines are rendered in the browser window using WebGL technology.

This application develops the idea, presented in the previous post: Single Rotation rules with frame interpolation (application link)

In short, Single Rotation is a simple cellular automaton rule that tells, how "alive" cells move across the rectangular grid. Movement of the cells is discrete, so to improve visual experience, intermediate positions are interpolated using Lanczos re-sampling. Additionally, low-pass Lanczos filter is applied in order to remove oscillations with period 4 and less. It is done to suppress annoying circular movement of single cells (one can easily ensure that they are period-4 oscillators). Together, filtering and interpolation give smooth, continuous trajectories for each cell. Cells move in 2 dimensions, so their word lines are 3-dimensional curves. The visualizer shows these word lines.

In case you don't have a WebGL-enabled browser, or the simulator runs too slow, here is a video demonstration. See also "Advanced usage" section below to improve performance.

Collisions in 3D

Three-dimensional view of world lines makes spaceship collisions especially charming. Don't they resemble Feynmann diagrams? Below are some collisions, seen in the simulator.

Spaceship + cell

It can be easily proved that in every reversible cellular automaton with cell count conservation, a collision of a spaceship of the lightest weight and a single-cell always produces a (possible different) lightest spaceship and single cell again. Below is an example.

Collision of a light spaceship and a single cell (bottom) translates single cell and changes direction of a spaceship.

To see this scene yourself, paste the following code to the "Custom Scene" text area and click "Load":

at -20 -20; 2bobo$b2o
at 0 0; $o

Spaceship + spaceship, symmetric

From the similar considerations, symmetric collision of 2 lightest spaceship also necessarily produces 2 (possibly different) spaceships. Here is how it looks like.

Symmetric collision of 2 light spaceships produces same spaceships after long reaction.

Interestingly, it appears that both spaceships don't even exchange their cells in the collision. Scene code for this collision is:

at -20 -20; 2bobo$b2o
at 20 20; 3b2o$bobo

Spaceship + spaceship, asymmetric

When collision of 2 spaceships is not symmetric, products may be different, but they necessarily include at least one spaceship (possibly not the lightest one). Here is an example.

Collision of 2 different light spaceships produces a spaceship and oscillators.

Scene code for this collision:

at -20 -20; 2bobo$b2o
at 20 20; 3b2o$bobo

Heavy spaceship + cell

Finally, when heavy spaceship collides with anything, it almost certainly produces lots of debris. Reversibility only requires that at least 1 spaceship is produced in this reaction, usually it is a light one. Below is a collision of a heaviest single (i.e. not chained) spaceship, made of 12 cells; and a single cell. Multiple oscillators and one light spaceship are produced.

Collision of the heaviest known spaceship (12 cells) and a single cell (bottom-left) produces a single spaceship and oscillator.

Scene code:

at -20 0; 2b4o$4b2o$bo2bo$2bo$bo2bobo
at 0 0; o

You can try any of the 328 spaceships from the library. Just copy the RLE code of the spaceship into the "Custom scene" field. Mini-language also lets you to assign colors to patterns, and combine multiple patterns with different offset. Rotating is not supported yet, you can use Reversible CA simulator to get RLE of the rotated pattern (paste RLE into the "buffer" text area and click arrow buttons).

Advanced usage

The application also takes some additional URL arguments. Add them to the URL after a "?" character, separating options with "&".

  • antialias=true
    Enables anti-aliasing, making smoother images but increasing CPU load.
  • visibility=distance
    where distance is a number in the range 1000 ~ 50'000. It defines, how farthe world lines are seen. Big distance significantly decreases FPS. Here are some sample links:
  • Additional mesh generation parameters (with their default values):
    • chunkSize=500
      number of steps in one mesh chunk
    • skipSteps=1
      Generate tube section every n'th step (1 - every step)
    • boardSize=100
      Size of the square board, must be even
    • lanczosOrder=3
      Lanczos interpolation order, 1 ... 10. 1 - linear interpolation, 3 - smooth interpolation
    • interpSteps=1
      How many mesh steps are there between 2 generation. integer, 1 ... 4
    • smoothingPeriod=4
      Low-pass filter, removing oscillations with period bigger than this. integer, 1 ... 100. 1 - no filtering.
    • timeScale=0.1
      "speed of light". z-axis length of one generation
    • tubeRadius=0.1
      Radius of a single rube
    • tubeSides=3
      Number of sides in the tube cross-section (2...10)
Probably, some more arguments would be added later.

Requirements

The application depends on the following technologies:

which means that latest versions of browsers and drivers are required. I have tested the application in Firefox (Linux, Windows) and Chrome (Linux, Windows, Android). It could run on the latest IE versions too.

Source code

Sources for this application are on Github: dmishin/singlerot-smooth, with 3D-specific code in the "3d" sub-folder. The sources are in CoffeeScript, to build them, CoffeeScript and "browserify" are required. Build system is written using GNU Make. I am not yet familiar enough with Node.js-specific tools.

Links

Here are links to the related posts and pages.

Monday, January 5, 2015

New Single Rotation spaceships

I still continue leisurely exploring the Single Rotation celluar automaton, a very simple reversible cellular automaton with complex emergent behavior. This post is a status repost on spaceships.

Brute-force spaceship search

My original library of spaceships had 205 patterns, found using random reaction method. Using a simple brute-force algorithm (C++ sources), some more spaceships having from 6 to 12 cells were discovered (well, this is an old news, but I haven't published it in the blog yet). Currently, there are 328 patterns in the library. The heaviest spaceship so far has 12 cells, and is surprisingly fast: c/71. For 13 cell patterns, several days of brute-forcing did not brought a single pattern yet. No knightships were found too.

Expansible spaceship

For me, this pattern is the most exciting discovery. While looking at the spaceship table, I have accidentally noticed a 7-cell spaceship, whose evolution resembled a ball, bouncing between 2 reflectors. A quick check showed that this impression was right: it consists of the lightest spaceship B, bouncing between 2 reflectors, of 1 and 2 cells. Each bounce moves the reflectors forward by 1 cell, thus making the pattern a single slow spaceship. The distance between the reflectors can be expanded, giving an infinite family of more and more slow and sparse spaceships. Note: because "Single Rotation" rule is chiral (i.e. not invariant to reflection), top and bottom reflectors must be different.

Evolution of the expansible spaceship.

Position of the reflector may be moved by \(2k\) cells diagonally, where \(k=0,1,...\), giving a diagonal spaceship of period \(245+56k\) and translation (1,1).

Expansible spaceship in its shortest form (bottom) and expanded by 2, 4, 6 cells. See it live in the simulator.

An interesting challenge is to find a growing variation of the ping pong ship (that would not be a spaceship, in a strict sence). If discovered, it would be the first growing pattern with growth rate below O(n).

Spaceship chains

Another (rater old) discovery, made by staring at the spaceship catalog. There are 2 patterns of 8 cells, resembling a pair of lightest 4-cell spaceships, moving in the same direction. However, the parts are not independent, they interact during the pattern evolution (though the interaction does not change period or speed of the pattern). A quick check revealed that both these patterns can be expanded, giving 2 infinite families of long spaceships of equal period and velocity.

Fast chain spaceship

Fast chain spaceships are built from the lightest spaceship B (the table of all lightest spaceships is here). The dimer of this spaceship is produced in random reaction with probability around \(2\cdot10^{-6}\)).

Lightest spaceship B and its dimer.

New spaceships can be attached to the end of the chain in 2 ways, giving 2 possible slants. All these chains have period 28 and move diagonally with velocity c/14.

Several chained spaceships. Spaceship B can be attached to the chain in 2 positions, giving 2 possible slants of the chain. See it live in the simulator.

The chains can be built by the following procedure:

  1. Take a dimer of the spaceship B, in some phase.
  2. Evaluate it step by step, until its right part will have the same configuration as the left part of the original dimer.
  3. Put the dimer to the field, matching coinciding parts.

Extending the chain: original dimer (top), its state after 10 generations (middle), trimer (bottom).

Interestingly, evaluation with tracking cell trajectories shows that all elementary spaceships in the zig-zag expansion are constantly exchanging cells.

Slow chain spaceship

The slow chain can be built from the repetitions of the lightest spaceship F. Unlike the fast chains, chains with different slant can't be connected, so no zig-zags here. Same as its monomer, these spaceships have period 368 and velocity c/184.

Two separate chains and their monomer. All move diagonally with velocity c/184. See it live in the simulator.