Generalized Logic Functions
S.Roof, Sept. 10, 2002
This paper originated from attempts to go beyond Wolfram's work. I was bothered by representation issues and had been thinking about ways to quantify information flows in systems. To get outside the figurative box, I thought it would be good to think in terms of quantifying information to begin with and then build up a cellular model instead of starting with cellular models. It seemed apparent to me that it was important to think in terms of pattern and not magnitudes. Thinking in magnitudes seemed to be one of the ways we fall into concepts of continuity etc.
My first approach was to think about information flowing in through various channels. The idea would be to quantify the amount being input as part of the system parameters. I was aware that Wolfram's model already quantifies info as one bit per cell in a neighborhood of states but I want to handle arbitrary numbers of bits as in a time series. That was my initial thrust anyway. Then I needed some way to multiplex those bits and apply some sort of rule. I was still inside the box, but enjoying the new approach anyway. I had already completed a working model that uses linear ansatz, so I started with ideas about superposition of inputs as patterns, not magnitudes. This led me to thinking about logic functions and truth tables. I became so preoccupied with logic functions that I soon abandoned superposition altogether. I realized that superposition is really no different than applying what Wolfram call totalistic rules i.e. it involves an average and destroys spatial information in a reductive fashion. The logic functions themselves became my new interest.
The following theory implements generalized logic functions i.e. multivalent logic functions that map onto n-dimensional truth tables. I started with the common idea of logic which is a binary function of two binary inputs. There are 16 possible normal logic functions and their output domain can be directly represented by 2X2 tuth table grids. One of those functions is called 'AND' such that say A AND B is true if A is true and B is TRUE, else the output is false. All the functions have names but it is convenient to simply use truth tables to define their behavior. It seemed to me that this was about the simplest way one can deal with raw patterns without using magnitudes.
The next thing I needed was to generalize logic functions to handle more than just two inputs. I realized after a while that all one needs to do is build truth tables with higher dimensionality i.e. 3dim cubes could handle three inputs etc. I also wanted to make the logic functions handle multivalent inputs so they could work with a range of values instead of just binary TRUE/FALSE. It turns out that binary is just a symbol base 2 system. We can use any symbol base we like. Think of a symbol base as the number of symbols in a pool of possible symbols. When we latch onto a symbol from our input stream, we only presume that it must be one out that pool of possible symbols. This is the orignal idea of Shannon's Information Theory. I call it the symbol base. It can be any lexicon or set of arbitrary representations whatsoever. We only assume at this point that we can latch fixed bites of input i.e. one symbol at a time. We make no assumption at all about what the symbols mean or how big they are. We are only interested in patterns as I said. I dont want to think about magnitudes or numbers either - just symbols and whatever sequential patterns they might make.
Seen in the above light, a generalized symbol base goes beyond multivalent logic which suggests ranges of value like really true or slightly false. My generalization is more like saying 'apple' is the result of pear, banana, pi, and jet engine. Now in my generalized higher dimensional truth tables I will actually use numbers to some base B but they serve only as internal addressability implementations and can be used to represent any pool of symbols at will. I am trying to set the context of how general this method turns out to be.
Once I finally threshed out the bones of my new model I discovered a startling fact. I will not reveal it yet, however, so that the impact will be more worthwhile. Suffice it to say, I will not be discussing cellular automata here. At this point I had completely diverged from cellular models and was simply thinking about patterns of symbols and possible functions for combining them.
Ok. Here is the theory.
Consider multiple channels of input. Assume a fixed number of possible symbols that one might extract from any of the input streams. Call this fixed number of arbitrary symbols a symbol base. We give the symbol base a number B equal to the number of possible symbols.
We may then compose an input vector S = { S0, S1, S2, ... Sn } whose components are symbols taken from channel 0,1,2,.. up to N different channels.
We can define a N-dimensional truth table 'T' such that any vector 'S' addresses one and only one cell within that truth table. The symbol at that cell is defined as the output 'O' given 'S' as the input.
The truth table T is defined as the core representation of a generalized logic function G such that the output symbol O = G(S).
The truth table is built as follows:
Each input channel gets assigned a dimensional axis with addressability equal to the symbol base B. In other words, if the symbol base is a pool of 10 arbitrary symbols, then the index or address of any particular symbol falls at it's particular place along this dimensional axis with 10 slots in it.
Since each channel gets it's own axis, we have a truth table with N axes each of which has B positions. The number of cells in the truth table is thus B^N i.e ( B to the power of N )
To achieve addressability into this N-dimensional table, we need a mechanism to flatten it especially since it will be convenient to represent the table as a one-dimensional linear array of elements when implementing the system on a computer. It turns out that the formular for doing this is
Table index = Sum from i=0 to i=N-1 of Si * B^i
Si = the ith component of the input vector S and the symbol base B is raised to the ith power. The sum over N gives the index into the flattened linear array of the truth table. We then have for our function G:
O = G(S) = Table[index]
The output symbol 'O' is just a quick lookup in a N-dim truth table. The input symbols form a n-dimensional key of addressability.
Now for the final piece of the puzzle. Each cell in the lookup table has to be able to address any arbitrary symbol in our pool of symbols. This requires each cell to have an addressability index range from 0 to B.
Now since each ouput cell of the truth table can have one of B possible indexes, the total number of possible truth tables given a fixed configuration of B symbols and N input channels is given by B^Cells or B to the power of the number of cells in the truth table. But above, we stated that the number of cells in the the truth table is equal to B^N. The final number of possible truth tables is thus B^B^N i.e
The number of possible generalized multivalent base B , N-dimensional logic functions is given by B to the power of B to the power of N.
I would like to emphasize that this is the most general idea of pattern based logic I could think of. Arbitrary symbols from a fixed set is the only content suggested by these functions. No magnitudes are implied at all! In addition, the functions have an n-dimensional arbitrary input domain.
I didn't think this idea would be so simple to solve. It is an elegant generalization and easily implemented on a computer. The shocker was that I realized that these generalized functions map one-to-one exactly onto Stephen Wolfram's cellular automata model.
Here is the correspondence:
The N input channels are equivalent to the neighborhood cells about a cell whose state is being evaluated. Wolfram starts with neighborhoods of three cells. This is equivalent to using a 3D input vector in my generalized logic functions. The number of possible neighborhood patterns in his system is equivalent to the number of truth table cells in my model. The total number of possible rules is the same as the number of possible logic functions. The two models are isomorphs (?).
I arrived at my model by intentionally striking out in an independent direction and to my surprise, I came full circle back to Wolfram's model. This strikes me as elegant justification for his ideas. I seemed to have inadvertantly generalized his model into pure logic, independent of cellular automata systems. My logic functions are in fact independant of any system. It is just a logical way of evaluating input patterns in the most general possible fashion. It could be applied to neural nets, black boxes, cellular automata, directed graph networks, rule based AI systems, times series, signal processing etc. etc.
When one sees the generality of the idea, he begins to be convinced that Wolfram is indeed correct in his assesment that all systems are subject to his new kind of science.
The downside to my new generalization is that the representational fat is back on the fire. Instead of finding a way around the problem, I merely more or less proved that it isn't going to go away! The ontological issues implied by this are troubling to me because it just seems unavoidable that rules, logic, functions etc. live in a larger space than the domains they operate on. Having been trained with a normal math background in calculus functions I am used to thinking in terms of real number domains and ranges for functions but not in terms of possible numbers of functions. We now have a way to quantify and classify discrete functions themselves, but at a cost. The representational cost is second order exponential so if such systems are to be embedded- as in actually putting one on a chip - then we can only work with very simple systems. This is a limitation of physical nature herself I think! Of course Wolfram says simple systems are all you need to achieve true complexity, but still I'm bothered by the disparity in an ontological sense.
It seems to me that such systems imply meta-levels. Maybe I shouldn't be troubled by this. The upside is that I formulated my idea in terms of input streams, so I can arbitrarily latch any number of input bits in between evolutions of the system. My thought is to let the input symbols ( or cellular states ) consist of RGB components and do real 24bit colored cellular automata graphs. The 3-fold blending of multiple input streams might produce really interesting patterns. I surmise they would merely be like superpositions of individual cellular plots but there might be surprises. I'll just have to try it.
One last thought for emphasis. By generalizing into pure logic I have shown that complexity does not arise from interactions between magnitudes at all. Magnitude or value oriented computation does not in effect produce complex behaviour. Magnitude based computation is based on ideas of continuity and is a subset of the pure discrete combinatorial logistics of operational math systems. Such discrete operational systems are content free. Complex behavior is a pattern that emerges from the pure combinatorial properties of patterns themselves. No other mechanisms are needed.
Caveat: My model does indeed use magnitudes, but I counter that they are involved only in the indexing addressability of the internal representation. The actual content that the functions operate on can be any arbitrary signals, symbols, bitmaps, numbers etc. I suppose this use of magnitudes in indexing should bother me, but actually in an embedded situation like a multiplex addressor on a chip, it is merely a question of transistors and wires that latch on or off. No magnitude implied!