Volume 18, Issue 4

In this paper we present an implementation of the computational method in [1] that allows ranking mathematical statements by their complexity. We introduce the complexity classes , and, accordingly, show that Legendre’s conjecture, Fermat’s last theorem, and Goldbach’s conjecture are in , Dyson’s conjecture is in , the Riemann hypothesis is in , and the four color theorem is in .

Bruno Grenet
Acceptable Complexity Measures of Theorems

In 1931 Gödel [1] presented his famous incompleteness theorem in Königsberg, stating that some true mathematical statements are unprovable. Yet, this result gives us no idea about those independent (i.e., true and unprovable) statements, about their frequency, the reason they are unprovable, and so on. In 2005 Calude and Jürgensen [2] proved Chaitin’s “heuristic principle” for an appropriate measure: the theorems of a finitely specified theory cannot be significantly more complex than the theory itself [3]. In this paper, we investigate the existence of other measures, different from the original, that satisfy this heuristic principle. Toward this end, we introduce a definition for acceptable complexity measures of theorems.

Paul-Jean Letourneau
Persistent Structures in Elementary Cellular Automaton Rule 146

Two types of spacetime structures found in the evolution of rule 146 are presented: very large white triangles, called monoliths, and persistent structures formed by sequential white triangles of even width. The monoliths are discussed in terms of large fluctuations away from equilibrium in a many-body system. The persistent structures are derived by highlighting the nonadditive portions of the rule 146 evolution, and some of their statistical properties are presented. The use of these structures for directing information flow in this class 3 rule are discussed.

Alexander G. D. Lamb
A Glider for Every Graph: Exploring the Algorithmic Requirements for Rotationally Invariant, Straight-Line Motion

The primary goal of digital physics research is to provide a description of the physical universe in terms of simple programs. One approach to attaining this goal is creating a toolbox of algorithms that reproduce the behavior of basic quantum phenomena. As a step in this direction, a simple pseudo-particle algorithm has been developed that exhibits rotationally invariant, glider-like motion across graphs in two or more dimensions. This algorithm is applied to a range of lattice and irregular graphs from the sparse to the densely connected, and it is shown that rotationally invariant motion can be easily obtained from irregular graphs that are sufficiently densely connected. Such graphs are also shown to be potentially compatible with spatial curvature and relativistic invariance. This work points the way toward a class of algorithms that can be used to tightly approximate the basic phenomena encountered in particle physics, while maintaining the desired properties of discreteness, determinism, and algorithmic simplicity.

Abigail Nussey
Outer Median and Probabilistic Cellular Automata on Network Topologies

One- and two-dimensional cellular automata have traditionally modeled systems with an underlying regular lattice well. However, for other systems, such as those with nonlocal phenomena, running cellular automata over different topologies could result in a simpler, more natural model. The creation of so-called “outer median” rules, and the use of modified probabilistic rules, make it possible to run cellular automata over network topologies. In this way, the rules themselves remain simple while more complicated nonlocal information is encoded in the topology. In this manner we can model systems with nonlocal elements, and briefly consider two examples of such systems: country border relationships and forest fire spread.

Paul Tarau
“Everything Is Everything” Revisited: Shapeshifting Data Types with Isomorphisms and Hylomorphisms

This paper is an exploration of isomorphisms between elementary data types (e.g., natural numbers, sets, finite functions, graphs, hypergraphs) and their extension to hereditarily finite universes through hylomorphisms derived from ranking/unranking and pairing/unpairing operations. An embedded higher order combinator language provides any-to-any encodings automatically. A few examples of free algorithms obtained by transferring operations between data types are shown. Other applications range from stream iterators on combinatorial objects to succinct data representations and the generation of random instances.