The theory of Detailed Dynamics and the Combinatorial Explosion
THE COMBINATORIAL EXPLOSION
Think of a physical system that is complex and dynamical. It could be the brain,
a computer, or a hot gas made of many molecules. The system has many states,
described by many variables, and it can transition from state to state. Assume
everything is discrete and finite. After all, this is the best we can do on a
computer. A "real" number on a computer is still an integer.
Take now a multi-dimensional state space with one coordinate per variable. One point in state space describes one state of the system. As the system evolves from state to state, the point moves, and describes a trajectory in state space. If I is some initial state - such as the input data for a program - and F some final state - such as the output from the program, there can in general be many trajectories from I to F. I can explain why, using only 2 variables.
Let x, y be the 2 variables, originally initialized to 0. Then, the initial state is I=(0, 0). Let x=2, y=3 be the allowed state transitions - they could be statements in a program. The final state is F=(2,3). If the program executes as given, the system goes from state (0,0) to (2, 0) to (2,3). That's a trajectory. But if we write y=3, x=2, then the trajectory is (0,0) to (0, 3) to (2,3), which is a different trajectory. There are 4 different states, and 2 different trajectories from state I to state F. From state (0,0), the system can transition to either (2,0) or (0,3). Of course, on a sequential computer, the program fixes a unique trajectory.
In general, a complex system in a certain state has a choice to transition to one out of many destination states. The usual assumption - "usual" because it is the best one can do - is that the transitions happen at random with a certain probability. Such an assumption results in a highly uncertain dynamics. In addition, a system, even one that is relatively small, can have an enormous number of different trajectories. I know of one with only 9 variables that has 23,610 trajectories, and another with 12 variables and 954,789 trajectories. This is a major combinatorial explosion.
The above description is similar to a discrete Markov chain, where a transition from a current state to another depends only on the current state and not on any previous states (no memory of previous states). However, in causal logic, the process is a waterfall, not recurrent, and probability distributions are not used. What would be called the "same" state in Markov's terminology, i.e. a state that reappears later in time, is in causal theory considered as two different states because they appear at different times. The Markov theory restricts the system's behavior by requiring that certain states remain "the same", which means they are not allowed to change as the result of learning. Causal logic allows every state to change as required by learning.
The issue at hand is how to overcome the combinatorial explosion. Is there anything certain that can be said about such an uncertain dynamics? Below I examine this question from the points of view of Physics, and the Quest for Certainty. More specifically, I follow the flow of information. I will ask what is it that we know, how is it that the information got there, and how we can use that what we know to seek certainty.
PHYSICS
In Physics, we know the fundamental principles of causality,
symmetry, least-action, and the laws of Thermodynamics. Each principle is a
statement of fact, and together they cover the largest body of experimental
evidence ever. I'll start with causality. Causality is the principle that
effects follow their causes [Gell-Mann]. All systems in our world are causal. In
Physics, causal sets are used to represent causality. Assume that a causal set
model of the system has been constructed. It would be a very large model, every
possible trajectory would have to be described. But it is easy to develop. The
state variables would be the elements, and the transitions the precedence
relations. The effort is the same as writing a program. For state (0,0) we would
write something like "if(system in (0,0) and goes to (2,0)) then ..., else
if(system is in (0,0) and goes to (0,3))then ..." and so on. A causal set is the
same as a program, an algorithm, and takes about the same effort to develop.
In the causal set model, a permutation of the set represents a trajectory. In the example above, the causal set is {x, y}, and the permutations are (x, y) and (y, x). They indicate the order in which the variables are calculated, and hence the trajectory. In a more general case, not all permutations are legal (because of the partial order), and those that are legal correspond to the allowed trajectories.
The causal set captures causality. The next principle is symmetry. The principle
of symmetry says that any system with a symmetry of the action also has a
conservation law for a conserved quantity. The conserved quantity can be any
function of the state variables, such as a value, an algorithm, a behavior. The
principle doesn't say what it is, but it does say that one exists. How is this
helpful? It helps in part because it reduces the uncertainty problem to one of
search, in part because symmetry reduces the number of variables, and most
importantly because of the following remarkable property: Every causal set
has a symmetry of the action, represented by the set of its legal permutations.
There follows that every causal set has a conserved quantity. This is,
already, a very important fact.
Next, there comes the principle of least-action (for a quick update on least-action see this article by David Dalrymple, scroll down to find the article). This principle states that any system that travels from initial state I to final state F, and can do so by following one out of many possible trajectories, will do so along a least-action trajectory. The principle works only when the system has some form of interaction with the environment that allows it to shed its excess free energy, along with the entropy that goes with the energy. Only the trajectories with the least-action remain because there is not enough "action" (energy that can travel) in the system to feed higher-action trajectories.
Before talking about least-action, one has to learn how to measure action. In other words, a metric has to be defined for causal sets. That metric, is nature's metric. The principle is in nature, hence the metric must also be in nature, and the correct approach is to ask nature what it is rather than trying to invent one. I did so, many years ago, on my own brain (you can do it on yours), and I discovered the action functional. The action functional is nature's metric for causal systems. The system I used for the experiment is given in Eq. (20) Section 4.3 of my JAGI paper, and Eq. (2) ibidem is the expression for the action function.
With the action functional in hand, we can run the causal set model and find the least-action trajectories. The set of permutations of the causal set that describes them is a grupoid (in rare cases, a group). Grupoids, just as groups, have block systems, which can be calculated by well known group-theoretical methods. A block system is a partition of the set of elements in the causal set that remains invariant under the action of the grupoid. A block system is, in turn, a causal set, and has its own block system. Iteration results in a hierarchy of block systems. The hierarchy is a mathematical fractal. Function E (in my JAGI paper) is defined as a map from the collection of all causal sets to the collection of all fractal hierarchies. Function E is bijective, which means that E-1 exists and that the hierarchy is unique. Function E is a one-one correspondence between the infinite-numerable set of all causal sets and the infinite-numerable set of all fractal hierarchies. A block system is a fact. It is a conserved quantity, and being a causal set, that is, an algorithm, it is also a conserved behavior. The block system has the property of being invariant under all the permutations in the grupoid, that is, under all the least-action trajectories of the dynamical system. The system goes from I to F along one of the trajectories. We do not know which, but we do know that the same block system applies to any trajectory the system chooses to follow. Therefore, we no longer care for which trajectory the system actually follows. Least-action stands as the supreme principle of nature. It is the principle that bypasses the combinatorial explosion and moves in the direction of certainty. I like to say: I didn't do it. It's all there, I just found it.
Many conclusions follow. One of them: there is no reinforcement learning. Nature has only one single "reward function", the action. Any system that has excess free energy and some form of interaction with the environment that allows it to shed the excess energy, ("cool off") will do so. In the process it will minimize its internal action (action = traveling energy), bypass the combinatorial explosion, and attain the least-action trajectories. As a side effect, the conserved quantity will emerge (emergence, self-organization) in the form of a fractal hierarchy of block systems. Block systems are observable because the system "dwells" in the blocks, unlike the states, which are ephemeral. If, in addition, the system has some form of memory, it will appear as "adaptive," or "intelligent." In causal logic, behavior = function(knowledge). When we learn something, the knowledge changes, and so does the behavior. When we perceive something from the environment, our knowledge changes, and so does our behavior. As we engage in a task, we are constantly flooded with a huge influx of sensory information, and it sure looks like our actions are responding to it while keeping the overall goal in mind. But all we are doing is minimizing the action of the incoming casual, that is, algorithmic information, combined with the overall goal, and using the resulting least-action algorithm to control our actions. This is what we call adaptation. We humans used to be unable to understand how adaptation works, so we decided to build a mystique around it and tried to explain it by reasoning and theories. But adaptation and intelligent behavior are side effects of Thermodynamics. Any machine, if given the chance to shed its excess free energy and equipped with a memory, will adapt and behave intelligently just as we do.
Another conclusion is that reasoning is a consequence of intelligence, and not the other way around. The same applies to logic, and theories. The causal sequence is that intelligence is in nature, then reasoning, logic and theories follow. Expecting that intelligence will emerge from reasoning and theories, as is frequently done, is a reversal of causality. Intelligence is not in Mathematics. Mathematics is in intelligence.
On the other hand, once causal logic is understood, then human creativity and engineering will be needed to devise procedures for minimizing the functional. Nature has its own ways to do that, but we can improve by using modern technology. The basic algorithm (Section 4.2 of my JAGI paper) assumes a permutation of the causal set represented by "neurons" in a row, and all that the neurons must do is to commute their adjacent positions if doing so helps to reduce the value of the action. The neurons need only local information to make decisions. This can be easily implemented on specially designed parallel hardware. As electronics is faster than cells, it is possible that the hardware will run much faster than the corresponding wetware.
In the course of describing the long process above, I have followed the thread
of information, and I have examined each one of the fundamental principles of
Physics as it participated in the thread. It is useful to repeat the same
exercise by following another thread, that of uncertainty (entropy). When this
is done, the process of causal logic will be viewed as a quest for certainty
(fact, truth).
The original dynamical system is very uncertain (high entropy). It has a very large number of states and can transition from one to another at random, giving rise to a huge number of potential trajectories. The first principle is causality, which states that only causal transitions will take place. This limits the number of trajectories and removes some of the uncertainty from the system.
Next comes the principle of symmetry. We intuitively understand that the presence of symmetry in a system reduces its complexity. Causal sets always have symmetry, and their symmetry is represented by the set of legal permutations, that is, legal trajectories. Hence, symmetry reduces the uncertainty of the system even further, and this effect is very significant.
Third, the principle of least-action states that only least-action trajectories are allowed, provided the system is allowed to dispose of its excess free energy. How many least-action trajectories are there? I have researched this question and found a limited answer: very few. I have seen systems with 1 million legal trajectories of which only 3 are least-action. The action functional partitions the set of legal permutations, and I have also researched the distribution of the population of permutations in the parts of the partition: it looks like an asymmetric Gauss curve. The bulk of the permutations are in the intermediate region. The populations decay towards both ends of the spectrum, but asymmetrically, so there is still a very large population at maximum action, and a very small population at minimum action. In my example above, there are 864 permutation at the maximum, and only 3 at the minimum. The principle of least-action is the most effective at removing uncertainty from the system: from 1 million legal trajectories, to only 3 least-action trajectories.
Finally, with the least-action permutations at hand, all that remains to achieve certainty is to calculate the block system for them. But even this simple step comes with yet another piece of puzzling information: the smaller a set of permutations is (provided it has more than 1 permutation), the more likely it is to have non-trivial block systems. In the example, the 3 least-action permutations have a non-trivial block system. The 864 permutations do not. Perhaps this is why nature has chosen least-action over maximum action.
In view of all of which, and in view of the fact that the brain is made of physical matter and that any AGI machine that may be built in some future will also be made of physical matter, and in further view that the fundamental principles of Physics represent the properties of physical matter in the most general and appropriate way currently possible, I have accepted for my work the working hypothesis that intelligence is also a property of physical matter and must be sought as such.
UPDATE (March 2013)
Oxford University Press has just announced, but not yet released, "From Strange Simplicity to Complex Familiarity. A Treatise on Matter, Information, Life and Thought" by Manfred Eigen, Max Planck Institute. Several statements found in Amazon's description of this book are tenets of causal logic, as described in my JAGI paper. Eigen introduces the new notion of information space. I don't know how Eigen defines information space, but I have the feeling that the notion will help to understand causal theory better.