Fractal Logic


Consider a pair of binary operations F0(x,y) and F1(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 complementary 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 F01 with the past value of F0, 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.



For another example of “fractal logic”, consider the three most common "means" of two variables x,y



We can construct another binary "mean" function by combining these three common means as follows



Let this function be denoted by AGH(x,y). By permuting A, G and H we can construct six such functions, but since the first two components are symmetrical we have only three distinct functions, which we will call AGH, AHG, and GHA. The function z = AGH(x,y) implies that z (if not zero) satisfies the cubic


which, in the special case x = y, factors as



Therefore, if z = AGH(x,x) then either z = x (as one would expect) or else z equals one of the two quadratic roots



If we consider the HGA mean we find z = HGA(x,x) implies that either z equals x or else z equals one of the values



Interestingly, for the third mean, AHG, we find that AHG(x,y) = G(x,y).


So, given the three original two-input functions, we have constructed another set of three two-input functions. These can be combined in the same three distinct ways to produce yet another set of three functions, and so on. At each level (above the lowest) the three functions have precisely the same structure in terms of the three lower-level functions. What is the limit of these functions at the nth level as n goes to infinity?


Return to MathPages Main Menu