Introduction

A liquid computer is a device that uses incompressible fluid to process information via mechanical, electrical, optical, or chemical means. The implementation of computation in liquid media has a history spanning over 120 years, from hydraulic algebraic machines developed in the 1900s to fluid maze solvers and droplet logics in the late 2000s. For an overview, please see1. Advantages of liquid computing include reconfigurability and flexibility, scalability, potential for reduced energy consumption, bio-compatibility and integration with biological systems, intrinsic parallelism, innovative data storage and retrieval, and novel computation paradigms. While liquid-based computers are still largely experimental and face several technical challenges, they offer intriguing advantages that could revolutionise various fields of computing and technology2,3,4,5.

Recently a new sub-domain of liquid computing emerged—computing with colloids (mixtures where microscopically dispersed insoluble particles liquids). The rise of colloid computers started from the liquid cybernetic systems, conceptualised as colloidal autonomous soft holonomic processors have demonstrated intriguing features, including autolographic capabilities2,3. Our previous experiments with ZnO colloids under controlled laboratory conditions demonstrated their potential as electrical analog neurons, successfully implementing synaptic-like learning and Pavlovian reflexes2,5. Additionally, the computational capabilities of \({\text {Fe}_{3}\text {O}_{4}}\) ferrofluid for digit recognition further exemplify the versatility of liquid-based systems4.

One of the key developments in colloid computing became mining of Boolean circuits in colloids6,7. The technique is based on selecting a pair of input sites, applying all possible combinations of inputs, where logical values are represented by electrical characteristics of input signals, to the sites and recording outputs, represented by electrical responses of the substrate, on a set of the selected output sites. The approach belong to the family of reservoir computing8,9,10,11,12 and in materia computing13,14,15,16,17 techniques of analysing computational properties of physical and biological substrates.

In our experimental laboratory studies6,7 we discovered a range of 4-, 6- and 8-ary Boolean functions. In present paper, we evaluate dynamics and complexity of the functions using one-dimensional cellular automata (CA). CA, despite their simple rules and structure, can exhibit complex behaviour. This makes them an excellent tool for evaluating the inherent complexity of n-ary Boolean functions by mapping the functions onto the CA rules and observing the resulting dynamics. CA can generate a variety of patterns based on initial states and transition rules. By encoding n-Boolean functions into CA rules, we study the patterns that emerge, providing a visual and dynamic representation of the function’s complexity. This is particularly useful for understanding how simple functions can lead to complex behaviours and vice versa.

Methods

Fig. 1
figure 1

(a) A scheme of the experiments. PC—laptop for generating sequences; CU—control unit, the dashed section is a breakdown of a single channel; ADC—analogue to digital converter18. (b) experimental setup. (c) A schematic of the inside of the unit control box. (d) A close-up photo of the colloid dish and the electrodes interfacing it. From7.

Full size image
Table 1 Most commonly found Boolean functions, \(\phi \) is a frequency of the functions’ discovery, extracted from ZnO nanoparticle. Boolean functions derived in7 are shown in (abc), and the functions derived in6 in (def) (ad) Two-inputs, (be)Four-inputs. (cf) Eight inputs.
Full size table
Table 2 The four most common extracted sum-of-products Boolean expressions with varying thresholds for the dispersed proteinoids (abc) and mixture of ZnO and proteinoids (def), (ad) 2-bit input string, (be) 4-bit input string, (cf) 8-bit input string.
Full size table

Experimental techniques on mining Boolean functions are described in full details in6,7. Here we briefly outline an overall approach, based on the example of7. Colloids of ZnO and proteinoids have been prepared as detailed in6,7. The hardware was built around an Arduino Mega 2560 (Elegoo, China) and a series of AD9833 programmable signal generators (Analog, USA). This setup can send sequences of 2, 4, and 8-bit strings to the colloid sample, with the strings encoded as step voltage inputs: − 5 V representing a logical ‘0’ and 5 V representing a logical ‘1’. In Fig. 1a, a PC programs a Control Unit (CU) and receives readings from an analog-to-digital converter (ADC). The CU, shown as a grey box connected to a standard laboratory power supply in Fig. 1b, contains the Arduino Mega and multiple amplifiers. To generate the 2, 4, and 8-bit strings without redesigning or rewiring the CU, multiple programmable signal generators were incorporated. This is abstracted in Fig. 1c, where only one generator and its output are depicted for simplicity. Activation of these generators is controlled by the Arduino Mega, which is programmed through the PC and also depicted within the CU entity in Fig. 1c. To search for 2-, 4-, and 8-input Boolean circuits, we used respective electrodes. These were 10 \(\upmu \text {m}\) platinum rods inserted 5 mm apart into the colloid container. Data acquisition (DAQ) probes, separated by 5 mm, fed 2 differential outputs to a Pico 24 ADC. Its 3rd channel received a pulse on each input state change. Refer to Fig. 1 for the apparatus schematic. The strings counted from binary 00 to 11, 0000 to 1111, or 00000000 to 11111111, changing state every 15 s. All possible electrode states were tested. For two bits, states sequentially altered every 15 s between 00, 01, 10, and 11. Similarly, all states of the four- and eight-bit strings were sequentially applied. Samples from 2 channels were taken at 1 Hz throughout the experiment. Peaks for each channel were located for 10 thresholds, from 100 to 600 mV in 50 mV steps, for each input state from 0000 to 1111. Most commonly found Boolean functions extracted from ZnO nanoparticle are listed in Table 1. Boolean functions derived in7 are presented in Table 1(abc), and the functions derived in6 in Table 1(def). Most frequent Boolean functions discovered in proteinoid colloids are shown in Table 2(abc) and mixture of ZnO and proteinoids in Table 2(def).

We evaluate complexity of the functions discovered via complexity of the space-time configurations of one-dimensional cellular automata (CA) governed by these functions. We call these CA ‘colloid cellular automata’ because their space-time evolution is governed by Boolean functions implemented by colloids and their mixtures in laboratory experiments. We consider an array Z of finite state automata, called cells, where every cell takes states ‘0’ or ‘1’ and updates its state depending on the states of its two, four or eight immediate neighbours. All cells update their states by the same rule and in discrete time. For example, a cell with index i, \(x_i \in Z\), updates its state at time t as a function of states of its two neighbours \(x^{t+1}=f(x_{i-1}^t, x_{i+1}^t)\) (representing variables A and B in Tables 1ad and 2ad), four neighbours: \(x^{t+1}=f(x_{i-2}^t, x_{i-1}^t, x_{i+1}^t, x_{i+2}^t)\) (representing variables \(A \ldots C\) in Tables 1be and 2be), or eight neighbours \(x^{t+1}=f(x_{i-4}^t, x_{i-3}^t, x_{i-2}^t, x_{i-1}^t, x_{i+1}^t, x_{i+2}^t, x_{i+3}^t, x_{i+4}^t)\) (representing variables \(A \ldots H\) in Tables 1cf and 2cf). For example the function \(f_{25}=(A \cdot B \cdot D \cdot \overline{ C}) + (C \cdot D \cdot \overline{ A} \cdot \overline{ B})\) is represented in a cell-state transition rule as \(x^{t+1}=(x_{i-2}^t \cdot x_{i-1}^t \cdot x_{i+2}^t \cdot \overline{x_{i+1}^t}) + (x_{i+1}^t \cdot x_{i+2}^t \cdot \overline{x_{i-2}^t} \cdot \overline{x_{i-1}^t})\). We evolved automata of 500 cells in 500 iterations of simultaneous cell-state transition.

To evaluate complexity of the cellular automata we used Shannon entropy19,20,21, Simpson’s diversity (commonly used in ecological studies to evaluate biodiversity of populations22,23,24), Lempel-Ziv complexity25, space filling and expressiveness26,27. Let matrix L represent time-space configuration of a 1D CA governed by state-transition rules derived from colloids. Let \(W=\{ 0,1 \}^9\) be a set of all possible configurations of a 9-node neighbourhood \(B_x\) including the central node x. Let B be a configuration of matrix L, we calculate a number of non-quiescent neighbourhood configurations as \(\eta = \sum _{ x \in L} \epsilon (x)\), where \(\epsilon (x)=0\) if for every resting x all its neighbours are in the state ‘0’, and \(\epsilon (x)=1\) otherwise. The Shannon entropy H is calculated as \(H =- \sum _{w \in W} (\nu (w)/\eta \cdot ln (\nu (w)/\eta ))\), where \(\nu (w)\) is a number of times the neighbourhood configuration w is found in configuration B. Simpson’s diversity S is calculated as \(S=\sum _{w \in W} (\nu (w)/\eta )^2\). Simpson diversity linearly correlates with Shannon entropy for \(H<3\); relationships becomes logarithmic for higher values of H as we previously demonstrated in28. The assessment of Lempel-Ziv complexity (compressibility), denoted as LZ, is based on the size of space-time configurations saved as PNG files representing configurations. This approach suffices because the ’deflation’ algorithm utilised in PNG lossless compression, as outlined in29,30,31, is a derivative of the classical Lempel–Ziv 1977 algorithm, as described in25. Space filling D is a ratio of non-zero entries in B to the total number of cells/nodes. This is used to estimate expressiveness. Expressiveness E is calculated as the Shannon entropy H divided by space-filling ratio D, the expressiveness reflects the ‘economy of diversity’.

Results

Fig. 2
figure 2

Functions with two-arguments and those functions with four or eight arguments which produce alike patterns. Space (1D CA array) states are horizontal, and time (progressing from top to bottom) is vertical: \(x^0_1 x^0_2 \ldots x^0_{500}\) \(x^1_1 x^1_2 \ldots x^1_{500}\) \(\ldots \) \(x^{500}_1 x^{500}_2 \ldots x^{500}_{500}\).

Full size image
Fig. 3
figure 3

Functions with four-arguments and those functions with eight arguments which produce alike patterns. Space (1D CA array) states are horizontal, and time (progressing from top to bottom) is vertical.

Full size image
Fig. 4
figure 4

Functions with eight-arguments. Space (1D CA array) states are horizontal, and time (progressing from top to bottom) is vertical.

Full size image

CA presented by majority of functions from Tabs. 1 and 2 evolve to all-0 or all-1 state, an example of evolution to all-0 states is shown in Fig. 2a. These are ‘trivial’ functions. Let us consider the positions of the functions within Wolfram’s classification of CA behaviour32. Most functions discovered belong to Class I, which is characterised by automata exhibiting simple dynamics and evolving to a stable state where all cells are in the same state. Functions \(f_1\), \(f_{10}\) (Fig. 2b), \(f_{39}\), \(f_{28}\), \(f_{35}\) (Fig. 2g), \(f_{40}\) (Fig. 2h), \(f_{12}\) (Fig. 3a), \(f_{14}\) (Fig. 3b), \(f_{19}\) (Fig. 3c), \(f_{20}\) (Fig. 3d), \(f_{37}\) (Fig. 4c), \(f_3\), \(f_6\), \(f_{38}\) (Fig. 2c), \(f_4\), \(f_9\), \(f_{13}\), \(f_{15}\), \(f_{17}\), \(f_{18}\) (Fig. 2d) and the function \(f_{37}\) (Fig. 4c) belong to the class II: the automata fall into global cells do not update their state or update them cyclically from ‘0’ to ‘1’. Space-time dynamics of class III CA is by quasi-random behaviour and difficult predictability of the successions of the global states. The following functions can be related to the class III CA: \(f_7\) (Fig. 2e), \(f_8\) (Fig. 2f), \(f_{21}\) (Fig. 4a), \(f_{36}\) and \(f_{45}\) (Fig. 4b). No functions from those discovered in laboratory experiments seem to belong to class IV, where the space-time dynamics of automata show gliders (compact patterns translating in space) with non-trivial interactions between the gliders. CA governed by functions presented in Fig. 2c,d demonstrate travelling compact patterns however these patterns emerge due to asymmetry of the functions.

Table 3 Complexity of space-time patterns generated by CA derived from non-trivial Boolean functions mined in ZnO and proteinoids’ colloids: LZ is an LZ complexity measured via size of ZIP file of the space-time configurations, LZ/n is the complexity normalised by the input string size, H is Shannon entropy, S is Simpson diversity, D is a space filling, E is an expressiveness. (a) Two-arguments functions, (b) Four-arguments functions, (c) Eight-arguments functions.
Full size table
Fig. 5
figure 5

(a) Shannon entropy H vs expressiveness E, linear approximation \(E=0.30874 + 2.5032*H\). (b) Shannon entropy H vs Simpson index S, linear approximation \(S=0.058092 + 0.43781*H\). (c) Shannon entropy H vs space filling D, linear approximation \(D=0.56455 + (-0.073223)*H\).

Full size image

Complexity measures of the functions discussed are shown in Table 3. Complexity measures — Shannon entropy, Simpson index and expressiveness—are consistent with each other as seen in scatter plots for Shannon entropy H vs. expressiveness E (Fig. 5a), Shannon entropy H vs. Simpson index S (Fig. 5b). Person correlation coefficients \(r(H,E)=0.57\), coefficient of determination \(R^2=0.3234\), shows moderate positive linear correlation and \(r(H,S)=0.9518\), \(R^2=0.9059\), shows strong positive linear correlation. While Shannon entropy H vs space filling D (Fig. 5c) show very weak negative correlations, \(r(H,D)=-0.1722\), \(R^2=0.0297\).

Based on measures calculated we can construct the following hierarchies of complexity:

  • CA representing 2-ary functions.

    • LZ: \(\{f_8, f_7\} \gg \{f_1, f_3, f_4\}> f_{11} > f_2\)

    • H: \(\{f_8,f_7\} \gg f_1 > f_2 \gg \{f_{11}, f_3, f_4\}\)

    • S: \(\{f_8, f_7\}> f_1 \gg \{f_3, f_4\} > \{f_2, f_{11}\}\)

    • E: \(f_7> f_8 \gg \{f_1, f_4, f_3\} > \{f_2, f_{11}\}\)

  • CA representing 4-ary functions.

    • LZ: \(f_{20}> f_{19}> \{f_{12}, f_{14} \} > f_{40} \)

    • H: \(f_{12}> \{f_{14}, f_{20}\} > \{f_{19}, f_{40} \}\)

    • S: \(\{f_{12}, f_{20}\}> f_{14} > \{f_{19}, f_{40} \}\)

    • E: \( f_{20}> \{f_{12}, f_{14}\} > \{f_{19}, f_{40}\}\)

  • CA representing 8-ary functions.

    • LZ: \(f_{21}> f_{36} > f_{37}\)

    • H: \(f_{21} > \{f_{37}, f_{36}\}\)

    • S: \(f_{21}> f_{37} > f_{36}\)

    • E: \(f_{37} \gg f_{21} > f_{36}\)

For CA governed by 2-ary functions, LZ hierarchy shows that functions \(f_8\) and \(f_7\) have the highest complexity, significantly higher than the others, \(f_1\),\(f_3\), and \(f_4\) have moderate complexity, \(f_{11}\) lower, and \(f_2\) the lowest. In Shannon complexity hierarchy \(f_8\) and \(f_7\) again rank highest, \(f_1\) is slightly lower, followed by \(f_2\); functions \(f_{11}\),\(f_3\), and \(f_4\) rank lowest and are grouped together. Simpson index ordering indicates that \(f_8\) and \(f_7\) have the highest structural complexity, \(f_1\) follows, with \(f_3\) and \(f_4\) significantly lower, and \(f_2\) and \(f_{11}\) the lowest. Order of expressive complexity puts function \(f_7\) as the highest, slightly higher than \(f_8\); functions \(f_1\),\(f_4\), and \(f_3\) are moderate, while \(f_2\) and \(f_{11}\) rank the lowest.

For CA governed by 4-ary functions, the order of compressibility demonstrates that function \(f_{20}\) has the highest complexity, followed by \(f_{19}\), functions \(f_{12}\) and \(f_{14}\) have moderate complexity, and \(f_{40}\) the lowest. Shannon complexity demonstrates that function \(f_{12}\) ranks highest, with \(f_{14}\) and \(f_{20}\) following, \(f_{19}\) and \(f_{40}\) are the lowest. In Simpson hierarchy functions \(f_{12}\) and \(f_{20}\) are highest, followed by \(f_{14}\), and \(f_{19}\) and \(f_{40}\) rank the lowest. In the expressiveness hierarchy function \(f_{20}\) is highest, with \(f_{12}\) and \(f_{14}\) in the middle, and \(f_{19}\) and \(f_{40}\) the lowest.

In CA governed by 8-ary functions, compressibility hierarchy is the following. Function \(f_{21}\) has the highest complexity, followed by \(f_{36}\)f and \(f_{37}\). In the Shannon entropy and Simpson index hierarchies function \(f_{21}\) is highest, with \(f_{37}\) and \(f_{36}\) being equal and lower. Expressiveness hierarchy shows that function \(f_{37}\) is significantly higher, followed by \(f_{21}\), and \(f_{36}\) the lowest.

Functions \(f_8\) and \(f_7\) are consistently ranked highest across multiple criteria for 2-ary functions, indicating their higher complexity or influence. Function \(f_{21}\) is ranked highest in the majority of criteria for 8-ary functions. Different criteria (LZ, H, S, E) can yield different hierarchies. For instance, in 4-ary functions, \(f_{12}\) is ranked highest by H and S but not by LZ or E. Expressiveness measure E seems to have distinct rankings compared to others, especially in the 8-ary functions.

Functions which produce CA patterns with absolute highest Liv-Zempel complexity, Shannon entropy and Simpson diversity are \(f_{21}\) (Table 1c and Fig. 4a), \(f_8\) (Table 1a and Fig. 2f) and \(f_7\) (Table 1a and Fig. 2e). A function with highest expressiveness is \(f_{37}\) (Table 2c and Fig. 4c). Whilst space-time configurations of CA governed by \(f_37\) shows complex local dynamics, the global dynamics is dull. This shows that the expressiveness might be not a reliable measure of global complexity. If we normalise values of LZ, H and S complexity measures by a number of terms or literals, we will fine that functions \(f_7\) and \(f_8\) are most complex functions, relative to formula complexity and in terms of space-time dynamics, discovered in colloids.

Conclusion and discussion

The colloid automata—one-dimensional cellular automata (CA) governed by Boolean functions derived from ZnO, proteinoid, and their mixture, colloids—exhibit a rich spectrum of space-time evolution. Using complexity measures such as Lempel-Ziv complexity, Shannon entropy, Simpson diversity, and expressiveness, we can construct families of complexity hierarchies based on the space-time configurations of these colloid CA. These hierarchies reflect the inherent complexities of the Boolean functions and provide a means to compare and understand their behaviour across different dimensions.

Fig. 6
figure 6

Space-time evolution of one-dimensional CA governed by \(f_7\). (a) Initial configuration is a single cell (in the middle of the array) being in the state ‘1’, all others are ‘0’. (a) Two cells, based 200 cells to the left and to the right the array’s centre are at state ‘1’ at the beginning of evolution. Cells in state ‘1’ are black, ‘0’ are light-gray. Time goes top down.

Full size image

The most complex, in terms of CA dynamics, functions discovered are xor (function \(f_7\)) and not xor (function \(f_8\)). The xor gate is the most hard to find in natural non-linear systems, Boolean gate33,34,35. Moreover, already in 1960s it was demonstrated that a linear perceptron can no learn xor function36. The use of xor gates in modern circuit design offers several advantages, such as reduced representation size and improved testability, and optimal power consumption37. CA governed by xor gate exhibit unpredictable dynamics, similar to that of that randomly generated patterns38 and, when evolve from single non-zero state configurations produced fractal patterns—Sierpenski gasket39. An evolution of rule \(f_7\) CA started from a single cell in state ‘1’ is shown in (Fig. 6a), a reflection from absorbing boundaries is seen. The same evolution, but from two cells in state ‘1’ (Fig. 6b), shows a new fractal derived from a collision. The newly formed fractal pattern has a higher density of non-quiescent cells than the parent fractal structures.

There are several limitations of the research which could be addressed in future studies. The research focuses solely on one-dimensional cellular automata. Extending this to two-dimensional or three-dimensional models could provide a more comprehensive understanding of the behaviour of colloid automata. The Boolean functions derived from ZnO, proteinoids, and their mixtures may not fully capture the complexities of information processing in real colloid systems. More sophisticated approaches incorporating physical and chemical interactions could yield more accurate results. The study is constrained by a finite set of states and rules, which might not encompass all possible behaviours of colloid systems. Exploring larger or infinite state spaces could reveal more complex dynamics. The reliance on specific complexity measures such as Lempel-Ziv complexity, Shannon entropy, Simpson diversity, and expressiveness might not capture all aspects of the system’s behaviour. Other measures or a combination of multiple metrics could provide a more holistic view. Measures like fractal dimension, Lyapunov exponents, or network-based metrics might offer new insights. Extending the research to higher-dimensional cellular automata could provide deeper insights into the spatial-temporal patterns of information processing in colloid systems, potentially revealing new patterns and behaviours.