In this paper I prove a long-standing (since 1985) conjecture of Wolfram, that one of the simplest possible cellular automata (number 110) is capable of universal computation. The proof involves a lengthy and intricate construction. This construction leads to significantly smaller universal Turing machines than were previously known.
Numerous articles have discussed my proof, including:
Nature (Jim Giles, v. 417, 216-218, 16 May 2002): "of particular interest"
Science (Melanie Mitchell, v. 298, Issue 5591, 65-68, 4 Oct 2002): "an impressive result"
Quantum Information and Computation (Scott Aaronson, v. 2(5):410-423, 2002): "a remarkable construction"
This paper shows how several common digital circuits (including demultiplexers, random access memory, and Walsh transforms) could be built in a bottom-up manner using biologically inspired self-assembly. This paper resolves a wager between myself and Paul Rothemund, in which he claimed that it seemed impossible for a single cellular automaton to create an arbitrarily large Walsh Transform matrix pattern, while I claimed it must be possible. In this paper I give a construction for such a cellular automaton. Some of the material about adorning Wang tiles with gates is from Paul's thesis, which gives a good theoretical foundation for topics in self-assembly.
The main reference on self-assembled circuits, this paper has become required reading in courses on chemical computation, such as by Goel at Stanford and by Savage at Brown.
In this paper I develop a new line of inquiry, regarding the time complexity of deciding whether a two dimensional pattern satisfies one of the most basic definitions regarding configurations in Conway's "Game of Life", that of being a "Still Life" (a single stable object). Among other findings, I present a quadratic time algorithm for this problem, which had previously been assumed to require exponential time.
The problem for which I found a quadratic time algorithm is one for which many people had previously written code taking exponential time to solve. I was asked to give an invited talk on the subject at the MSRI Combinatorial Game Theory Research Workshop, Berkeley, 2000.
In this report I outline a construction that allows a chemical reaction network to simulate a Turing machine with only a polynomial time slowdown. A proof sketch is given, and consequences are discussed.
Apart from being inherently interesting, this result for the first time places tight bounds on the speedups obtainable by researchers in stochastic simulation of chemical systems, who are trying to create faster approximate simulation algorithms. In computational complexity, it provides the first example we know of of a system where a randomized version of a process is not just more efficient, but qualitatively more powerful than the nondeterministic version. In other words, other algorithms are known where stochasticity dramatically increases efficiency, but here stochasticity increases what it is possible to compute, regardless of efficiency. Without stochasticity, computations are limited to primitive recursive functions, but with stochasticity, the full generality of Turing machine computation is attained.
In this paper we demonstrate that two sequences with unrelated definitions are actually the same sequence, and we present a new method for calculating sequence elements efficiently even though there is no efficient recurrence or generating function for them.
Donald Knuth points readers to our paper in his book Selected
Papers on Analysis of Algorithms.
Erich Neuwirth (Seminaire
Lotharingien de Combinatoire, v. 47, 2002) has since found an even
faster algorithm, although it is still O(n^6), like ours.
In this paper we present a rather complicated construction for optimally coloring any sufficiently large toroidal grid so that any two sites of the same color are at least t steps from each other. (This generalization of regular graph coloring is called 'interleaving'.)
This is a significant contribution in the area of interleaving. The conference version is already being cited by other research groups.
In this work I created an environment in which I thought learning of higher order concepts would be necessary. I created a general purpose physics-based hinged rigid body simulator and used it to simulate a bicycle for a learning agent to learn to ride. But as others have found in other contexts, most environments do not require higher order concepts, and in this case it turned out that a simple two neuron circuit was already sufficient for controlling the bicycle, indeed better than a human.
The physics simulator was a significant project in itself: I studied rigid body mechanics (which is more complex than most of us realize) and designed the simulator explicitly so as to simultaneously exactly preserve both angular momenta and kinetic energies, as previous simulations of mine (in quantum machanics) had shown me that exact preservation of conserved quantities is crucial for getting accurate results. The simulator works nicely, and I later read in Sam Buss's 2001 paper, Accurate and Efficient Simulation of Rigid Body Rotations, that my precautions were well warranted.
In this paper I give an outline of how a network of relations can be used as an associative memory, and how such a memory can be used to learn control tasks such as riding a bicycle. Some simple proofs are given, along with an experimental precursor to my current experimental direction. This is a "concept paper", avoiding difficult proofs.
This paper set the stage for my research into combining ideas of this paper with fuzzy value representations in a belief propagation network structure, where I found successful learning rules for abstract relations.
If we watch raindrops start to fall on the pavement, at the beginning we can trace long dry routes avoiding bounded wet regions, while later we can trace long wet routes avoiding bounded dry regions. Percolation theory is the study of the spot density at which this phase transition ('percolation') occurs, either on a grid or in continuous space. This paper considers continuum percolation using spot shapes other than circles. If we count the average number of neighbors that each spot has, then percolation for circles happens at about 4.5 neighbors. We give both theoretical and experimental evidence that all other shapes percolate with an even lower number of neighbors.
This paper resolves an issue that had been causing a growing rift between theory and practice in the use of percolation models for wireless networks, namely the use of circular discs to model the range of a wireless transmitter. Percolation is relevant in this context because it indicates whether long range connections are available in an ad hoc wireless network. In practice, the range of a wireless transmitter is highly irregular and anisotropic, leading many researchers to dismiss the theoretical results as irrelevant. This paper showed how the existing body of theoretical results can indeed be applied to the irregular shapes arising in practice, thus putting an end to this controversy.
This paper presents an algorithm for enclosing a given set of points with a small number of circles. Using circles centered at grid points, we obtain an approximation algorithm within a constant factor of the optimal non-grid solution.
As the technical report details, this is a problem which has attracted attention for over 20 years, and our algorithm is the first to achieve a linear running time. Our results also indicate how to compare the cost of a grid-based solution to the cost of an arbitrary solution, a question related to active interest of the wireless communications industry regarding the optimal placement of base stations for covering a given set of customers or substations.
In this thesis I explore how relations can be combined into networks, and how these networks implement larger relations. While the formalism is similar to that of constraint satisfaction problems, the methodology is inspired by neural considerations, particularly regarding the non-zero cost of duplicating information. Through a series of proofs of varying difficulty I show exactly which small relations are capable of implementing which others, while a complex construction shows that in contrast the general question is undecidable. This line of investigation leads serendipitously to the study of an existing subject, Chemical Reaction Networks, where among other things I show that the question of producibility of a species (equivalent to the question of implementability among functions without fan-out, analogous to the question of implementability among relations) turns out to be decidable.
My development of networks of relations provides a foundation for my own research on problems in machine learning. Although the thesis itself is more abstract and does not delve into machine learning per se, the paper listed above, Networks of Relations for Representation, Learning, and Generalization, gives an indication of the connection as its title indicates. This is an area of active research, as described above in more detail under that paper.
In the area of Chemical Reaction Networks, I and my colleague David Soloveichik have since managed to solve an open problem described at the end of the thesis, namely, we have found a construction that shows how a Chemical Reaction Network can simulate a Turing machine with only a polynomial time slowdown. The paper listed above, Metamathematics Meets Biochemistry, describes this further.
In this report I briefly present the implementability results from my thesis, but in the language of logic, wherein the results are about which predicates can implement which others with a 'predicate graph', where vertices represent predicates and edges represent variables. Most proofs are omitted, although the undecidability proof is included as an appendix.
The results here are comparable to Post's 1921 thesis work, which presented results on implementability among boolean functions. My work turned out to answer existing open questions from a paper of Valiant, Quantum Circuits that can be Simulated Classically in Polynomial Time (SIAM Journal of Computing, v. 31(4), pp. 1229-1254, 2002).