Universal computation

While none of the 256 possible radius r = 1 binary valued CA are believed to be capable of universal computation, the rule whose long time behavior has proven to be the most difficult to understand fully is rule R22 ... 

Class c4 Rules, T20 (r=2) and T88 (r=3) It has been conjectured that all generic class c4 CA are capable of universal computation [wolf85e]. With initial configurations specifying arbitrary algorithmic procedures, such systems can effectively evaluate any computable function and therefore mimic the action of any general purpose computer. 

A formal analysis of the behavior of general reversible systems will be given in section 4.3. An explicit example of a two-dimensional reversible universal computer... 

Perhaps the most interesting result to come out of these investigations is the strong likelihood that the most complex rules, those capable of supporting universal computation, are in fact located within the second-order transition region. There are at least three strong reasons for this ... 

A remarkable, but (at first sight, at least) naively unimpressive, feature of this rule is its class c4-like ability to give rise to complex ordered patterns out of an initially disordered state, or primordial soup. In figure 3.65, for example, which provides a few snapshot views of the evolution of four different random initial states taken during the first 50 iterations, we see evidence of the same typically class c4-like behavior that we have already seen so much of in one-dimensional systems. What distinguishes this system from all of the previous ones that we have studied, however, and makes this rule truly remarkable, is that Life has been proven to be capable of universal computation. 

Although the formal meaning of this statement will be discussed greater detail a bit later in this section, its profound implication is just as easy to appreciate informally. By virtue of being a universal computer, a proper selection of initial conditions can ensure that Life can be made to carry out arbitrary algorithmic procedures - i.e.. Life can serve as a general purpose computer . 

Perhaps the simplest way to prove that a system is capable of universal computation - certainly the most straightforward way - is to show that the system in question is formally equivalent to another system that has already been proven to be a universal computer. In this section we sketch a proof of the computational universality of Conway s Life-rule by explicitly constructing dynamical equivalents of all of the computational ingredients required by a conventional digital computer. 

Just as there are universal computers that, given a particular input, can simulate any other com-puter, there are NP-complete problems that, with the appropriate input, are effectively equivalent to any NP-hard problem of a given size. For example, Boolean satisfiability -i.e. the problem of determining truth values of the variable s of a Boolean expression so that the expression is true -is known to be an NP-complete problem. See section 12.3.5.2... 

Notice that only the last class of unrestricted languages requires a full universal computer (i.e. Turing Machine)-, the other classes require progressively simpler kinds of computers. Each one of these four automata act as a kind of black-box into which is fed a tape of symbols, sequentially, one cell at a time. During each cycle, the black-box reads the symbol at the appropriate cell, responds to that... 

The last element necessary for the construction of a universal computer is a simple time delay, i.e. a circuit primitive whose output at time t-fl equals the input at time t and which allows us to feed outputs back into gates as inputs. 

The most important observation about the BBMCA is that since any BBM circuit can be translated into a BBMCA circuit (albeit with whatever number of time and/or cross-over delays might be required), the BBMCA is, like the BBM itself, a universal computer. 

Now, to be sure, McCulloch-Pitts neurons are unrealistically rendered versions of the real thing. For example, the assumption that neuronal firing occurs synchronously throughout the net at well defined discrete points in time is simply wrong. The tacit assumption that the structure of a neural net (i.e. its connectivity, as defined by the set of synaptic weights) remains constant over time is known be false as well. Moreover, while the input-output relationship for real neurons is nonlinear, real neurons are not the simple threshold devices the McCulloch-Pitts model assumes them to be. In fact, the output of a real neuron depends on its weighted input in a nonlinear but continuous manner. Despite their conceptual drawbacks, however, McCulloch-Pitts neurons are nontrivial devices. McCulloch-Pitts were able to show that for a suitably chosen set of synaptic weights wij, a synchronous net of their model neurons is capable of universal computation. This means that, in principle, McCulloch-Pitts nets possess the same raw computational power as a conventional computer (see section 6.4). 

Von Neumann s machine is actually an example of a universal constructor. It must not only carry out logical operations (i.e. act as a universal computer), but must also be able to identify and manipulate various components. The universal constructor C must be able to both (1) construct the machine whose blueprint appears in symbolic form on its input tape and (2) attach a copy of that same blueprint to the machine once it is constructed. Self-reproduction is the special case where C s input tape actually contains the blueprint data for C itself. Alas, there are a few subtleties. 

Since, as we have continually been reminded throughout this book, the capacity for some kind of signal propagation is critical for being able to perform arbitrary computational processes, it should come as no surprise that there is a finite intersection between both context-sensitive and unrestricted Chomsky languages - the latter, of which, we recall require the class of universal computers as their accept-... 

We make three additional comments concerning algorithmic complexity, as defined by equation 12.9. First, while Ku(s) clearly depends on the universal computer [/ that is chosen to run the program V, because of the ability of universal computers to simulate one another, the difference between algorithmic complexities computed for universal computers U and U2 will be bounded by the 0 ) size of the prefix code allowing any program V that is executed on U to be executed... 

Finiteness is the basic assumption a finite total volume of space-time and a finite amount of information in a finite volume of space-time. We require universality, of course, since we know that without it nothing much of interest can happen. We can also take a strong cue from our own universe, which allows us to build universal computers. If the underlying micro-physics was not universal we would not be able to do this. Reversibility is desirable because it ensures a strict conservation of information and can be used to create systems that conserve various quantities such as energy and angular momentum despite underlying anisotropies. 

It can be shown that the BBM is capable of universal computation ([fredkin82, marg84, marg88]). Unfortunately, as shown by Zurek [zurek84], the model is also unlikely to ever be realized in practice. Because BBM computations all depend so critically on initial ball and mirror placement, the fact that any errors in the initial placement grow exponentially in time effectively renders their results either suspect or meaningless. 

We have already seen at least one example of a physical system capable of acting as a universal computer in our discussion of Predkin and Toffoli s [fredkin82]... 

A universal, computer oriented representation of the relevant structural features of molecular systems and their interconversion by chemical reactions is possible with the pairwise combinations (E, C) of BE-matrices and CC-matrices. The transformation... 

Despite its simplicity, the Turing machine models the computing capability of a general-purpose computer, and since 1936 it has been the standard accepted model of universal computation. The proposition, often called the Church-Turing thesis, says that any process which could naturally be called an effective procedure can be realized by a Turing machine. In other words, this thesis states that no realizable computing device can be more powerful than a Turing machine [150,151]. It is, however, of interest to discuss the... 

The work reported here was supported by grants from The Petroleum Research Fund of the American Chemical Society and the National Science Foundation. Without the cooperation of the Staff and the free use of the facilities of the Columbia University Computer Center, this work could never have been undertaken. 

The pecularities of solving the various versions of the Hartree-Fock equations are described in more detail in monographs [16, 45], There are a number of widely used universal computer programs to solve the non-relativistic [16, 45] and relativistic [57, 182] versions of the Hartree-Fock equations, used separately or as a part of the more general complex, e.g. calculating energy spectra, etc. [183]. 

---