Volume 25, Number 4 (2016)
Introduction to "Black Hole Tech?"
This short article is an introduction to the republication of "Black Hole Tech?" for the audience of Complex Systems.
Black Hole Tech?
We've observed one pair of black holes, a billion light years away. And no doubt now we'll get evidence for a steady stream of others around the universe. What if somehow we could get our hands on our very own black holes, and maybe even lots of them? What could we—or, for that matter, any putative extraterrestrials—do with them? What kind of perhaps extremely exotic structures or technology could eventually be made with them?
Code 1599 Cellular Automaton New Patterns
Code 1599 is a cellular automaton rule that produces complex patterns that resemble the phenomenon of free will under simple initial conditions. However, by expanding the range of initial conditions considered to include complex backgrounds, we find that code 1599 can produce patterns that are entirely different from its ordinary structure, but similar or even structurally identical to some elementary cellular automata rules.
A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory
Adam Yedidia and Scott Aaronson
Since the definition of the busy beaver function by Rado in 1962, an interesting open question has been the smallest value of n for which BB(n) is independent of Zermelo–Fraenkel set theory with the axiom of choice (ZFC). Is this n approximately 10, or closer to 1 000 000, or is it even larger? In this paper, we show that it is at most 7910 by presenting an explicit description of a 7910-state Turing machine Z with one tape and a two-symbol alphabet that cannot be proved to run forever in ZFC (even though it presumably does), assuming ZFC is consistent. The machine is based on work of Harvey Friedman on independent statements involving order-invariant graphs. In doing so, we give the first known upper bound on the highest provable busy beaver number in ZFC. To create Z, we develop and use a higher-level language, Laconic, which is much more convenient than direct state manipulation. We also use Laconic to design two Turing machines, G and R, that halt if and only if there are counterexamples to Goldbach's conjecture and the Riemann hypothesis, respectively.
On the Number of NK-Kauffman Networks Mapped into a Functional Graph
NK-Kauffman networks , where N is the number of Boolean variables and K the average number of connections, are studied. The K connections are random and chosen with equal probability, while the Boolean functions are randomly chosen with a bias p. The injectivity of the map , where is the set of functional graphs with nodes, is studied. In the asymptotic regime N ≫ 1, it is found that a critical connectivity exists such that ψ is many-to-one for and injective for . The analysis is extended when the tautology and contradiction Boolean functions are excluded from the construction of . For such a case, it is found that ψ always remains injective.
Complex Systems ISSN 0891-2513
Complex Systems Publication, Inc.
Published four times annually
Complex Systems Publications, Inc.
P.O. Box 6149
Champaign, IL 61826 USA
Join the leading edge of complex systems research today. There are no publication charges. Authors are provided with 25 reprints of papers published in Complex Systems. Papers may be submitted via the web or email. Find out more »