Fractal Logic

Consider a pair of binary operations F₀(x,y) and F₁(x,y), each constructed from two lower level binary operations using feedback as shown below:

The symbol denotes the "past value" of F contained in the feedback loop. Now suppose each of the four lower-level operations is similarly constructed from two operations on a still lower level, and so on, recursively. The general expression by which an operation at one level is expressed in terms of operations at the next lower level is

where the subscript *i signifies any binary string of zeros and ones (the same for each appearance in the expression) followed by the index i, and the index denotes the 2's complement of i. Every recursive expression is applicable with each subscript in the expression prefaced by the string *, so hereafter we will omit this preface. Also, instead of writing the expressions with the generic complementaty subscripts i and , we will use 0 and 1, with the understanding that each expression remains valid under exchange of these two symbols. Hence the above expression will be written as

For example, if the lower level functions ending with the subscript 1 are logical ORs, and those ending with the subscript 0 are logical ANDs, the top level operations written in Boolean notation are

Returning to the general case, we can use the recursive formula to express any operation in terms of operations two levels down as follows

By construction, the "past values" of successive levels are linked by the relations

Consequently we can replace the past value of F₀₁ with the past value of F₀, and the preceding expression can be written as

To illustrate, let us again define the lowest-level operations as simple logical functions. This time we define the 3rd-level functions whose subscripts end in 0 as logical ORs, and those whose subscripts end in 1 as logical ANDs. (This is the reverse of how we defined the 2nd-level gates in the previous example.) In Boolean notation the top level operations then reduce to

These are the very same logical operations that we found when we assumed the recursion went only to the 2nd level and imposed logical definitions on the second-level operations. Obviously if we proceed to the next level, and define the 4th-level functions as we did in the 2nd-level example, we will arrive again at the very same logical operations. In fact, we can define the top level events recursively down to any arbitrary level, and impose the logical function definitions on the operations at that level (transposing OR and AND depending on whether the level is odd or even), and the result will be the same two top-level operations. (Of course, if we don't transpose AND/OR on successive levels, the two top-level operations are themselves transposed for successive levels.) This is reminiscent of the story about mythological belief that the world is carried on the back of a turtle, and when the believer is asked what the turtle is standing on, he says "another turtle", and "it's turtles all the way down". It also reminds me of how the rest mass of a particle can be regarded as consisting of the rest mass of a smaller set of sub-particles with a large amount of kinetic energy to give them a greater effective "relativistic mass". And then the rest mass of the smaller particles can likewise be regarded as mainly kinetic energy of a set of even smaller particles, and so on. Extending this to a complete infinity would suggest the somewhat puzzling notion that there is no essential rest mass at all, and the entire top-level rest mass consists of nothing but recursive modes of kinetic energy of... lower lower-level modes of energy.

For what sets of fundamental operators (like AND and OR) do we arrive at a "convergent" top-level operation? This is certainly not always the case. For example, if we define the lowest-level operations as NAND and NOR functions, then the top-level operations based on just the first recurrence are

Going to the next level of recursion, the top functions are

Notice that the feedback loops represent "memory", so in general there is another element of memory for each level of recurrence, and presumably an infinite recurrence would represent infinite memory.

This type of "fractal" (i.e., self-similar) function is not limited to logical operations. For example, it's interesting to consider the result of defining the lowest-level functions in the above recurrence as MIN and MAX selection operators. Typical results for just the second order recursion level are illustrated below.

The blue and green lines are the sample input functions and the red line is the top-level output function. We can also imagine other patterns of nested self-similar operations, such as the trinary construction illustrated below.