cellular automata
description: discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling
62 results
The Man From the Future: The Visionary Life of John Von Neumann
by Ananyo Bhattacharya · 6 Oct 2021 · 476pp · 121,460 words
of the first in a stream of visionaries to pass through the doors of the group was Tommaso Toffoli, who started a graduate thesis on cellular automata there in 1975. Toffoli was convinced there was a deep link between automata and the physical world. ‘Von Neumann himself devised
…
cellular automata to make a reductionistic point about the plausibility of life being possible in a world with very simple primitives,’ Toffoli explained. ‘But even von Neumann,
…
who was a quantum physicist, neglected completely the connections with physics – that a cellular automata could be a model of fundamental physics.’34 Perhaps, Toffoli conjectured, the complex laws of physics might be rewritten more simply in terms of automata
…
be traced backwards (or forwards) to any other point in time (as long as we have complete knowledge of its state now). None of the cellular automata that had been invented, however, had this property. In Conway’s Life, for example, there are many different configurations that end in an empty board
…
Toffoli’s contributions to the field would be to design, with computer scientist Norman Margolus, a computer specifically to run cellular automata programs faster than even the supercomputers of the time. The Cellular Automata Machine (CAM) would help researchers ride the wave of interest triggered by Conway’s Life. Complex patterns blossomed and faded
…
least by himself – and he is dismissive of his predecessors. ‘When I started,’ he told journalist Steven Levy, ‘there were maybe 200 papers written on cellular automata. It’s amazing how little was concluded from those 200 papers. They’re really bad.’37 Like Fredkin, Wolfram thinks that the complexity of the
…
.40 Fredkin insists he discussed his theories of digital cosmogenesis with Wolfram at the meeting in the Caribbean, and there catalysed his incipient interest in cellular automata. Wolfram says he discovered automata independently, and only afterwards found the work of von Neumann and others describing similar phenomena to those appearing on his
…
be laughable had Wolfram not, in fact, begun publishing on quantum theory in respectable academic journals from 1975, aged fifteen. Wolfram’s first paper on cellular automata only appeared in 1983,42 after the Moskito Island meeting, though he says he began work in the field two years earlier.43 He was
…
’s programs ran, a picture emerged on his screen that showed, line by line, the entire evolutionary history of his automata. He called them ‘elementary cellular automata’ because the rules that determined the fate of a cell were very straightforward. In Wolfram’s scheme, a cell communicates only with its immediate neighbours
…
of each trio will be a ‘1’ or a ‘0’ next. Wolfram’s numbering convention for his elementary cellular automata. Wolfram systematically studied all 256 different sets of rules available to his elementary cellular automata, sorting them carefully into groups like a mathematical zoologist. Some of the rule sets produced very boring results. Rule
…
looks the same at different scales, is known as a fractal, and this particular one, a Sierpiński triangle, crops up in a number of different cellular automata. In Life, for example, all that is required for the shape to appear is to start the game with a long line of live cells
…
hardly surprising. Looking at them, one could guess that a simple rule applied many times over might account for their apparent complexity. Would all elementary cellular automata turn out to produce patterns that were at heart also elementary? Rule 30 would show decisively that they did not. The same sorts of rule
…
behaviour. Finally, Class 4 automata, like Rule 110, produce disordered patterns punctuated by regular structures that move and interact. This class is home to all cellular automata capable of supporting universal computation.45 The stream of papers that Wolfram was producing on automata was causing a stir, but not everyone approved. Attitudes
…
to join the illustrious ranks of the permanent staff. A year later, busy with his new company he paused his foray into the world of cellular automata – only to stage a dramatic return to the field in 2002, with A New Kind of Science.46 That book, the result of ten years
…
code to be found in his lifetime – perhaps by himself.47 The book presents in dazzling detail the results of Wolfram’s painstaking investigations of cellular automata of many kinds. His conclusion is that simple rules can yield complex outputs but adding more rules (or dimensions) rarely adds much complexity to the
…
to be an important one. The jury, however, is still very much out. Whatever the ultimate verdict of his peers, Wolfram had succeeded in putting cellular automata on the map like no one else. His groundwork would help spur those who saw automata not just as crude simulations of life, but as
…
the bottom up by injecting into oil bubbles called liposomes the biological machinery necessary for the cells to grow and divide.68 Von Neumann’s cellular automata seeded grand theories of everything and inspired pioneers who dared to imagine life could be made from scratch. His unfinished kinematic automaton too has borne
…
work to stand as a monument to himself, as indeed it does.’90 Over seven decades since von Neumann first lectured on his theory of cellular automata, its possible implications are still being worked out. Plausibly, it could yet give us nanomachines, self-building moon bases and even a theory of everything
…
of rules that allow the brain’s incredible organization to grow from simple beginnings in the womb. That makes them in some ways kin to cellular automata, which von Neumann, Wolfram and others have shown can produce great complexity without the help of intricate machinery or a guiding plan. At the logical
…
, Harvard University Press, Cambridge, Mass. 33. Levy, Artificial Life. 34. Quoted in ibid. 35. Published as Tommaso Toffoli, 1977, ‘Computation and Construction Universality of Reversible Cellular Automata’, Journal of Computer and System Sciences, 15(2), pp. 213–31. 36. Quoted in Levy, Artificial Life. 37. Ibid. 38. Fredkin made the case for
…
this in Edward Fredkin, 1990, ‘Digital Mechanics: An Informational Process based on Reversible Universal Cellular Automata’, Physica D, 45 (1990), pp. 254–70. 39. Steven Levy, ‘Stephen Wolfram Invites You to Solve Physics’, Wired (2020), https://www.wired.com/story/stephen
…
.com/reference/notes/876b. 43. See Wolfram, A New Kind of Science. 44. Matthew Cook, ‘Universality in Elementary Cellular Automata’, Complex Systems, 15 (2004), pp. 1–40. 45. Steven Wolfram, 1984, ‘Universality and Complexity in Cellular Automata’, Physica D, 10(1–2), pp. 1–35. 46. Steven Wolfram, 2002, A New Kind of Science
…
March 2021, https://doi.org/10.1016/j.cell.2021.02.014. 58. Quoted in Levy, Artificial Life. 59. Christopher G. Langton, ‘Self-reproduction in Cellular Automata’, Physica 10D (1984), pp. 135–44. 60. Quoted in Levy, Artificial Life. 61. Quoted in ibid. 62. Christopher G. Langton, 1990, ‘Computation at the Edge
…
dioxide emissions 283 cardinality 23 Carleton University, Ottawa 225 Carter, Jimmy 264 causality 29, 48–9, 51, 60, 76, 298n63 Cayley, Arthur 32 cellular automata see self-reproducing automata Cellular Automata Machine 245 chain reaction, nuclears, Monte Carlo bomb simulations 8, 80, 81–2, 87–8, 133–4 Champernowne, David 151 Champlain, SS 77
Complexity: A Guided Tour
by Melanie Mitchell · 31 Mar 2009 · 524pp · 120,182 words
Complexity PART TWO Life and Evolution in Computers CHAPTER EIGHT Self-Reproducing Computer Programs CHAPTER NINE Genetic Algorithms PART THREE Computation Writ Large CHAPTER TEN Cellular Automata, Life, and the Universe CHAPTER ELEVEN Computing with Particles CHAPTER TWELVE Information Processing in Living Systems CHAPTER THIRTEEN How to Make Analogies (if You
…
science is information processing writ large across all of nature. —Chris Langton (Quoted in Roger Lewin, Complexity: Life at the Edge of Chaos) CHAPTER 10 Cellular Automata, Life, and the Universe Computation in Nature A recent article in Science magazine, called “Getting the Behavior of Social Insects to Compute,” described the work
…
interesting. In this spirit of simplification, many people have studied computation in nature via an idealized model of a complex system called a cellular automaton. Cellular Automata Recall from chapter 4 that Turing machines provide a way of formalizing the notion of “definite procedure”—that is, computation. A computation is the transformation
…
, back in the 1940s, based on a suggestion by his colleague, the mathematician Stan Ulam. (This is a great irony of computer science, since cellular automata are often referred to as non -von-Neumann-style architectures, to contrast with the von-Neumann-style architectures that von Neumann also invented.) As I
…
ability to form complex patterns in order to achieve computations in a nontraditional way. The first step is to characterize the kinds of patterns that cellular automata can form. The Four Classes In the early 1980s, Stephen Wolfram, a physicist working at the Institute for Advanced Study in Princeton, became fascinated
…
what was going on in these seemingly ultra-simple systems, there was no chance of understanding more complex (e.g., two-dimensional or multistate) cellular automata. Figure 10.4 illustrates one particular elementary cellular automaton rule. Figure 10.4a shows the lattice—now just a line of cells, each connected to
…
the notes for a review on how to convert base 2 numbers to decimal.) FIGURE 10.5. An illustration of the numbering system for elementary cellular automata used by Stephen Wolfram. FIGURE 10.6. Rule 110 space-time diagram. The one-dimensional cellular automaton lattice has 200 cells, which are shown
…
an initial configuration of random states. Looking at figures 10.6 and 10.7, perhaps you can sense why Wolfram got so excited about elementary cellular automata. How, exactly, did these complex patterns emerge from the very simple cellular automaton rules that created them? Seeing such complexity emerge from simple rules
…
by Rule 30 that he patented its use as part of a pseudo-random number generator. In Wolfram’s exhaustive survey of all 256 elementary cellular automata, he viewed the behavior over time of each one starting from many different initial configurations. For each elementary cellular automaton and each initial configuration,
…
Fredkin had both theorized that the universe is a cellular automaton as early as the 1960s). However, whatever its other merits might be, we cellular-automata addicts can all agree that NKS provided a lot of welcome publicity for our obscure passion. CHAPTER 11 Computing with Particles IN 1989 I HAPPENED
…
the “local majority vote” cellular automaton starting from a majority black initial configuration. (Figure adapted from Mitchell, M., Crutchfield, J. P., and Das, R., Evolving cellular automata to perform computations: A review of recent work. In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA ’96). Moscow, Russia
…
cells and the cellular automaton iterates to a fixed configuration of all white. (Figure adapted from Mitchell, M., Crutchfield, J. P., and Das, R., Evolving cellular automata to perform computations: A review of recent work. In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA ’96). Moscow, Russia
…
technique for detecting what he called “information processing structures” in the behavior of dynamical systems and he suggested that we apply this technique to the cellular automata evolved by the GA. Crutchfield’s idea was that the boundaries between simple regions (e.g., sides A, B, C, and the vertical boundary
…
regions of “simple patterns” filtered out, leaving the boundaries between these regions (“particles”). (Figure adapted from Mitchell, M., Crutchfield, J. P., and Das, R., Evolving cellular automata to perform computations: A review of recent work. In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA ’96). Moscow, Russia
…
: Russian Academy of Sciences, 1996.) We were able to apply this kind of analysis to several different cellular automata evolved to perform the majority classification task as well as other tasks. This analysis allowed us to predict things such as the fitness of a
…
also allowed us to understand why one cellular automaton had higher fitness than another and how to describe the mistakes that were made by different cellular automata in performing computations. Particles give us something we could not get by looking at the cellular automaton rule or the cellular automaton’s space-
…
a description imposed by us (the scientists) rather than anything explicit taking place in a cellular automaton or used by the genetic algorithm to evolve cellular automata. But somehow the genetic algorithm managed to evolve a rule whose behavior can be explained in terms of information-processing particles. Indeed, the language
…
of particles and their interactions form an explanatory vocabulary for decentralized computation in the context of one-dimensional cellular automata. Something like this language may be what Stephen Wolfram was looking for when he posed the last of his “Twenty Problems in the Theory of
…
Cellular Automata”: “What higher-level descriptions of information processing in cellular automata can be given?” All this is relatively recent work and needs to be developed much further. I believe that this
…
are the scaffolding for information-carrying waves of activity and their information-processing interactions. Brain computation is of course a long jump from one-dimensional cellular automata. However, there is one natural system that might be explained by something very much like our particles: the stomata networks of plants. Every leafy
…
Turing machines and von Neumann-style computers. The work described in the previous chapter was an attempt to address this issue in the context of cellular automata. The purpose of this chapter is to explore the notion of information processing or computation in living systems. I describe three different natural systems
…
understand computations in a human-friendly way that is abstracted from particular details of machine code and hardware. INFORMATION PROCESSING IN CELLULAR AUTOMATA For non-von-Neumann-style computers such as cellular automata, the answers are not as straightforward. Consider, for example, the cellular automaton described in the previous chapter that was evolved
…
chapter I proposed that particles and their interactions are one approach toward such a high-level language for describing how information processing is done in cellular automata. Information is communicated via the movement of particles, and information is processed via collisions between particles. In this way, the intermediate steps of information
…
. Computer science has given us automatic compilers and decompilers that do the translation, allowing us to understand how a particular program is processing information. For cellular automata, no such compilers or decompilers exist, at least not yet, and there is still no practical and general way to design high-level “programs.”
…
it communicated and processed? How does this information acquire meaning? And to whom? WHAT PLAYS THE ROLE OF INFORMATION? As was the case for cellular automata, when I talk about information processing in these systems I am referring not to the actions of individual components such as cells, ants, or enzymes
…
have provided inspiration for new kinds of technology and computing methods. For example, Turing machines inspired programmable computers; von Neumann’s self-reproducing automaton inspired cellular automata; minimal models of Darwinian evolution, the immune system, and insect colonies inspired genetic algorithms, computer immune systems, and “swarm intelligence” methods, respectively. To illustrate
…
shallowness is a virtue. Physical Review E, 59 (1), 1999, pp. 275–283. “Stephen Wolfram, for example, has proposed”: Wolfram, S., Universality and complexity in cellular automata. Physica D, 10, 1984, pp. 1–35. “However, as Charles Bennett and others have argued”: e.g., see Bennett, C. H., Dissipation, information, computational
…
Kind of Science. Champaign, IL, Wolfram Media, 2002, p. 235. “Matthew Cook … finally proved that rule 110 was indeed universal”: Cook, M., Universality in elementary cellular automata. Complex Systems 15(1), 2004, 1–40. “A New Kind of Science”: Wolfram, S., A New Kind of Science. Champaign; IL: Wolfram Media, 2002,
…
Darwin, Volume 1. Cambridge, UK: Cambridge University Press, 1985. Burks, A. W. Von Neumann’s self-reproducing automata. In A. W. Burks (editor), Essays on Cellular Automata. Urbana: University of Illinois Press, 1970. Calvino, I. Invisible Cities. New York: Harcourt Brace Jovanovich, 1974. (Translated by W. Weaver.) Carlson, J. M. and
…
Connell, J. H. Minimalist Mobile Robotics: A Colony-Style Architecture for an Artificial Creature. San Diego, CA: Academic Press, 1990. Cook, M. Universality in elementary cellular automata. Complex Systems 15(1), 2004, pp. 1–40. Coullet, P. and Tresser, C. Itérations d’endomorphismes et groupe de renormalization. Comptes Rendues de Académie des
…
importance of being noisy. Bulletin of the Santa Fe Institute, Summer, 1994. Minsky, M. The Society of Mind, Simon & Schuster, 1987. Mitchell, M. Computation in cellular automata: A selected review. In T. Gramss et al. (editors), Nonstandard Computation. Weinheim, Germany: Wiley-VCH, 1998, pp. 95–140. Mitchell, M. Analogy-Making as
…
361–383. Mitchell, M. Complex systems: Network thinking. Artificial Intelligence, 170(18), 2006, pp. 1194–1212. Mitchell, M. Crutchfield, J. P., and Das, R. Evolving cellular automata to perform computations: A review of recent work. In Proceedings of the First International Conference on Evolutionary Computation and its Applications (EvCA ’96). Moscow: Russian
…
Leon, 46 Brown, James, 262–267, 294, 300 Buddha, 71 Buffon, Louis Leclerk de, 72 Burks, Alice, 57 Burks, Arthur, 57, 123, 145 CA. See cellular automata calculus, 18, 301–302 of complexity, 301–303 Calvino, Italo, 225 Carnot, Sadi, 302 Carroll, Sean, 278 carrying capacity, 25, 27 cascading failure, 255–258
…
C. elegans, 158, 238, 247 cellular automata architecture of 146–148 classes of behavior in, 155–156 computation in, 157–158, 161, 164–168, 171–172, 303 elementary, 152–153 (see also
…
common properties of, 294–295 as computational capacity, 102 definitions of, 13, 94–111 as degree of hierarchy, 109–111 effective, 98–100 in elementary cellular automata, 155 as entropy, 96–98 as fractal dimension, 102–109 future of, 301–303 Horgan’s article on, 291–292 Latin root, 4 as
…
303 complex systems. See complexity computable problem (or process), 157 computation biologically inspired, 184–185, 207 (see also genetic algorithms) in the brain, 168 in cellular automata, 157–158, 161, 164–168, 171–172, 303 courses on theory of, 67 defined as Turing machine (see Turing machines) definite procedures as, 63–64
…
, Albert, 69, 72, 124, 210, 215, 293, 295 Eisenstein, Robert, 94 Eldredge, Niles, 84–85, 87 emergence, xii, 13, 286, 293, 301, 303 in cellular automata, 155 of complexity, 4, 155, 286 of cooperation, 215–220 general theories of, 303 of parallel terraced scan, 195–196 predicting, 301 of randomness, 38
…
for, 278–280 transcription of, 90–91 translation of, 91–92 genetic algorithms applications of, 129–130, 142 balancing exploration and exploitation in, 184 evolving cellular automata with, 160, 162–164 evolving Prisoner’s dilemma strategies with, 217–218 as example of idea model, 211 origin of, 128 recipe for, 128–129
…
loop, 66 infinite loop detector, 66 information acquisition of meaning in complex systems, 184, 208 bit of, 45 as central topic in cybernetics, 296 in cellular automata, 171–172 in cellular automaton particles, 165–168 in complex systems, 40–41, 146, 157–158, 179–185 content, 52–54, 96–97, 99,
…
out-links, 240 Packard, Norman, 160–161, 293 Pagels, Heinz, 1, 101 PageRank algorithm, 240, 244 parallel terraced scan, 182–183, 195–197 particles (in cellular automata), 166–168, 171–172 path length (network), 237–239, 245, 257, 318 pathogens, 8, 172–176, 180, 182, 195 effect on gene transcription and
…
Rosenfield, Israel, 181 Rothman, Tony, 43 Rubner, Max, 258, 260, 266, 268 rule 110 cellular automaton, 153–157 rule 30 cellular automaton, 154–156 rules, cellular automata, 147–149 Santa Fe Institute, x, xi, 94, 156, 160, 164, 254, 264, 282, 291 Complex Systems Summer School, 94, 300 Savage, Leonard, 297
…
of the Halting problem, 65–68 See also noncomputable problem (or process) unified principles. See universal principles unimodal map, 35, 36, 38 universal computation in cellular automata, 149–150, 156 in defining complexity, 102, 156 definition of, 149 in nature, 157–158 See also universal Turing machine universal computer. See universal Turing
…
–295 skepticism about, 293–295, 299 universal properties of chaotic systems, 34–38 universal Turing machine, 64–65, as blueprint for programmable computers, 65, 69 cellular automata equivalent to, 149–150, 156 in defining complexity, 102, 156 Varela, Francisco, 298 variable (in computer program), 119 von Neumann, John, 28, 117–118,
…
124–127, 146, 149, 156, 209, 211–212, 294, 296–297 invention of cellular automata, 149 self-reproducing automaton, 122–124, 156 von-Neumann-style architecture, 146, 169–171, 209 Wang, Hao, 69 Watson, James, 89, 93, 274 Watts, Duncan
Turing's Vision: The Birth of Computer Science
by Chris Bernhardt · 12 May 2016 · 210pp · 62,771 words
Functions and Calculations Church-Turing Thesis Computational Power Machines That Don’t Halt 5. Other Systems for Computation The Lambda Calculus Tag Systems One-Dimensional Cellular Automata 6. Encodings and the Universal Machine A Method of Encoding Finite Automata Universal Machines Construction of Universal Machines Modern Computers Are Universal Machines Von Neumann
…
of these. We begin with the lambda calculus (λ-calculus) of Alonzo Church, then look at an example of a tag system, finally we consider cellular automata. These views of computation seem very different, but each perspective has its own strengths. The λ-calculus leads to programming languages; tag systems are useful
…
for proving different systems equivalent; cellular automata give pictures of complete computations. After this brief detour we return to Turing’s arguments. Chapter 6 Up until now, machines have been described by
…
will look at other ways of manipulating strings. First we look at Church’s λ-calculus (lambda calculus), then Post’s tag systems, and finally cellular automata. All of these have been shown to be able to do computations. In fact, rather surprisingly, all have computational power equivalent to Turing machines. We
…
simplicity, they are able to do any computation. Their simplicity is often useful in proving the equivalence of computational systems. For example, the proof that cellular automata can do anything that Turing machines can do involves emulating Turing machines by tag systems. The final topic is the study one-dimensional
…
cellular automata. These are interesting because they yield two-dimensional pictures that show the entire computation. From these pictures it is possible to make conjectures about the
…
read in any order. Though this book is about a paper written in 1936, the examples that we consider using tag systems and one-dimensional cellular automata were developed quite recently. In writing a book of this type it is very easy to give the impression that everything has been done and
…
lefthand column. Since the Collatz conjecture is unsolved it is not known whether De Mol’s system will halt for every initial string. One-Dimensional Cellular Automata A one-dimensional cellular automaton consists of an infinite tape divided into cells. Each cell can have one of a number of states. We will
…
it is being applied to; and for computations using Turing machines, the tape head often has to travel large distances. It is quite remarkable that cellular automata are computationally equivalent to these other systems — that anything computed by a Turing machine can be computed by a one-dimensional cellular automaton. Though these
…
of the eight “T”s. We can then think of this as a number in binary There are a total of 256 rules for these cellular automata. The one we have looked at is called Rule 129. Stephen Wolfram in his book A New Kind of Science gives an extensive description of
…
cellular automata. We will look at one of the examples that he gives of a simple computation being done by one. Consider Rule 132. For those whose
…
black cells will be left. This rule can be thought of as telling us whether a number is odd or even. One nice property of cellular automata is that we have a picture that shows the whole computation. Wolfram, in his book, looks at all 256 rules and classifies them into four
…
. Consequently, anything a Turing machine, or computer, can do a tag system can do — at least in theory.4 When we looked at one-dimensional cellular automata, we made the observation that some of the rules could be considered as algorithms for computations. Surprisingly, they can also simulate universal Turing machines. Stephen
…
by Aaranson, The Beginning of Infinity: Explanations That Transform the World by Deutsch, and Gödel, Escher, Bach by Hofstadter are all fascinating. Cellular automata We only looked briefly looked at cellular automata, but they have a long and interesting history. They were first studied by Ulam and von Neumann as the first computers were
…
of cells. George Dyson’s Turing’s Cathedral gives a good historical description of this work John Conway, in 1970, defined Life involving two-dimensional cellular automata. These were popularized by Martin Gardner in Scientific American. William Poundstone’s The Recursive Universe is a good book on the history of these automata
…
in 1985, but was been republished by Dover Press in 2013.) Stephen Wolfram’s A New Kind of Science is an encyclopedia of one-dimensional cellular automata with extensive notes. Theory of computation A.K. Dewdney’s The New Turing Omnibus contains sixty six short chapters. Each chapter is a short article
…
consist of a string of as with length n + (n + 1)/2 which is equal to (3n + 1)/2. 13. Matthew Cook, “Universality in Elementary Cellular Automata.” Complex Systems, 15 (2004) 1-40. Chapter 6 1. These machines were first introduced by Stephen Cook and Robert Reckhow in 1973. 2. This requires
…
,” Proceedings of the National Academy of Sciences of the United States of America 50 (6): pp.1143–1148, 1964. [6] Cook, Matthew. “Universality in Elementary Cellular Automata,” Complex Systems, 15, 2004, pp. 1–40. [7] Cook, S. A; Reckhow, R. A. “Time bounded random access machines,” J. Computer and Systems Sciences 7
…
Theorem, 132 CAPTCHA (Completely Automated Public Turing Test To Tell Computers and Humans Apart), 158 Cardinality, 124 computations, 140 real numbers, 136 Cells, 25, 43 Cellular automata, 82 Central Limit Theorem, 1 Central processing unit, 98 Chinese Room Argument, 158 Church, Alonzo, 16, 24, 62, 63, 71, 148 Church-Turing thesis, 61
…
, 147, 148, 152, 156 Newton, Isaac, 62 Non-accepting trap, 34, 51 Non-computable number, 142 Non-deterministic Turing machine, 65 NP, 66 One-dimensional cellular automata, 82, 103, 164 Oracle, 149 P, 66 Pardon, 161, 162 Parity checking, 29 Peano, Giuseppe, 73 Peano axioms, 73 Peirce, Charles Sanders, 6, 73 Petzold
The Singularity Is Near: When Humans Transcend Biology
by Ray Kurzweil · 14 Jul 2005 · 761pp · 231,902 words
. Fractal Dimensions and the Brain. DNA Sequencing, Memory, Communications, the Internet, and Miniaturization 75 Information, Order, and Evolution: The Insights from Wolfram and Fredkin's Cellular Automata. Can We Evolve Artificial Intelligence from Simple Rules? The Singularity as Economic Imperative 94 Get Eighty Trillion Dollars—Limited Time Only. Deflation ... a Bad Thing
…
dominate the first half of this century represent different facets of the information revolution. Information, Order, and Evolution: The Insights from Wolfram and Fredkin's Cellular Automata: As I've described in this chapter, every aspect of information and information technology is growing at an exponential pace. Inherent in our expectation of
…
of adjacent nearby cells according to a transformation rule.) In his view, it is feasible to express all information processes in terms of operations on cellular automata, so Wolfram's insights bear on several key issues related to information and its pervasiveness. Wolfram postulates that the universe itself is a giant cellular
…
.62 In commenting on Fredkin's theory of digital physics, Wright writes, Fredkin ... is talking about an interesting characteristic of some computer programs, including many cellular automata: there is no shortcut to finding out what they will lead to. This, indeed, is a basic difference between the "analytical" approach associated with traditional
…
a system susceptible to the analytic approach without figuring out what states it will occupy between now and then, but in the case of many cellular automata, you must go through all the intermediate states to find out what the end will be like: there is no way to know the future
…
the universe. Wolfram builds his theory primarily on a single, unified insight. The discovery that has so excited Wolfram is a simple rule he calls cellular automata rules 110 and its behavior. (There are some other interesting automata rules, but rule 110 makes the point well enough.) Most of Wolfram's analyses
…
deal with the simplest possible cellular automata, specifically those that involve just a one-dimensional line of cells, two possible colors (black and white), and rules based only on the two immediately
…
correct. I agree with Wolfram that computation is all around us, and that some of the patterns we see are created by the equivalent of cellular automata. But a key issue to ask is this: Just how complex are the results of class automata? Wolfram effectively sidesteps the issue of degrees of
…
(one-dimensional, two-color, two-neighbor rules). What happens if we increase the dimensionality—for example, go to multiple colors or even generalize these discrete cellular automata to continuous function? Wolfram address all of this quite thoroughly. The results produced from more complex automata are essentially the same as those of the
…
make the converse point that we are unable to increase the complexity of the end results through either more complex rules or further iteration. So cellular automata get us only so far. Can We Evolve Artificial Intelligence from Simple Rules? So how do we get from these interesting but limited patterns to
…
concept we need into consideration is conflict—that is, evolution. If we add another simple concept—an evolutionary algorithm—to that of Wolfram's simple cellular automata, we start to get far more exciting and more intelligent results. Wolfram say that the class 4 automata and an evolutionary algorithm are "computationally equivalent
…
true that some phenomena in nature that may appear complex at some level are merely the results of simple underlying computational mechanisms that are essentially cellular automata at work. The interesting pattern of triangles on a "tent oliuve" (cited extensively by Wolfram) or the intricate and varied patterns of a snowflake are
…
by General Dynamics has demonstrated the feasibility of self-replicating nanoscale machines.86 Using computer simulations, the researchers showed that molecularly precise robots called kinematic cellular automata, built from reconfigurable molecular modules, were capable of reproducing themselves. The designs also used the broadcast architecture, which established the feasibility of this safer form
…
have been impossible. The universe appears to have exactly the right rules and constants. (The situation is reminiscent of Steven Wolfram's observation that certain cellular-automata rules [see the sidebar on p. 85] allow for the creation of remarkably complex and unpredictable patterns, whereas other rules lead to very uninteresting patterns
…
point here is that a simple design rule can create a lot of apparent complexity. Stephen Wolfram makes a similar point using simple rules on cellular automata (see chapter 2). This insight holds true for the brain's design. As I've discussed, the compressed genome is a relatively compact design, smaller
…
theory of physics, we would then be tempted to examine what sorts of deeper mechanisms are actually implementing the computations and links of the cellular automata. Perhaps underlying the cellular automata that run the universe are yet more basic analog phenomena, which, like transistors, are subject to thresholds that enable them to perform digital
…
, but no simpler." So the real question is whether we can express the basic relationships that we are aware of in more elegant terms, using cellular-automata algorithms. One test of a new theory of physics is whether it is capable of making verifiable predictions. In at least one important way, that
…
might be a difficult challenge for a cellular automata-based theory because lack of predictability is one of the fundamental features of cellular automata. Wolfram starts by describing the universe as a large network of nodes. The nodes do not exist in
…
"cellular gliders," which are patterns that are advanced through the network for each cycle of computation. Fans of the game Life (which is based on cellular automata) will recognize the common phenomenon of gliders and the diversity of patterns that can move smoothly through a cellular-automaton network. The speed of light
…
one represents normal curvatures in three-dimensional space. Alternatively, the network can become denser in certain regions to represent the equivalent of such curvature. A cellular-automata conception proves useful in explaining the apparent increase in entropy (disorder) that is implied by the second law of thermodynamics. We have to assume that
…
the cellular-automata rule underlying the universe is a class 4 rule (see main text)—otherwise the universe would be a dull place indeed. Wolfram's primary observation
…
-antiparticle pairs. The randomness could be the same sort of randomness that we see in class 4 cellular automata. Although predetermined, the behavior of class 4 automata cannot be anticipated (other than by running the cellular automata) and is effectively random. This is not a new view. It's equivalent to the "hidden variables
…
work out in a very precise way.Yethere we are. A bigger question is, How could a hidden-variables theory be tested? If based on cellular-automata-like processes, the hidden variables would be inherently unpredictable, even if deterministic. We would have to find some other way to "unhide" the hidden variables
…
. Einstein called this "spooky action at a distance" and rejected it, although recent experiments appear to confirm it. Some phenomena fit more neatly into this cellular automata-network conception than others. Some of the suggestions appear elegant, but as Wolfram's "Note for Physicists" makes clear, the task of translating all of
…
physics into a consistent cellular-automata-based system is daunting indeed. Extending his discussion to philosophy, Wolfram "explains" the apparent phenomenon of free will as decisions that are determined but unpredictable
…
place in processes such as fluid turbulence. Some of the phenomena in nature (for example, clouds, coastlines) are characterized by repetitive simple processes such as cellular automata and fractals, but intelligent patterns (such as the human brain) require an evolutionary process (or alternatively, the reverse engineering of the results of such a
…
so that we can build a more robust vision of the ubiquitous role of algorithms in the world. The lack of predictability of class 4 cellular automata underlies at least some of the apparent complexity of biological systems and does represent one of the important biological paradigms that we can seek to
…
possible, however, that such methods can explain all of physics. If Wolfram, or anyone else for that matter, succeeds in formulating physics in terms of cellular-automata operations and their patterns, Wolfram's book will have earned its title. In any event, I believe the book to be an important work of
…
Nanomachines Feasible," June 2, 2004, http://www.smalltimes.com/document_display.cfm?section_id=53&document_id=8007, reporting on Tihamer Toth-Pejel, "Modeling Kinematic Cellular Automata," April 30, 2004, http://www.niac.usra.edu/files/studies/final_report/pdf/883Toth-Fejel.pdf. 87. W. U. Dittmer, A. Reuter, and F. C
In Our Own Image: Savior or Destroyer? The History and Future of Artificial Intelligence
by George Zarkadakis · 7 Mar 2016 · 405pp · 117,219 words
. And yet the names, as well as the deeds, of the pioneering cyberneticians remain with us still: von Neumann’s computer architectures, game theory and cellular automata; Ashby’s and von Foerster’s analysis of self-organisation; Braitenberg’s autonomous robots; and McCulloch’s artificial neural nets, perceptrons, and classifiers, still inspire
…
. This deeper link between the emergence of complex behaviour at criticality and recursive computations has also been demonstrated in digital computers using cellular automata, another great invention by John von Neumann. Cellular automata are patterns of 0s and 1s that evolve step-by-step according to a simple set of rules. A new pattern
…
step towards the discovery of a general, mathematical, law for life. There are too many things about cellular automata that make them profoundly similar to physical, living, things. By operating near the edge of chaos, cellular automata evolve with time by responding to their changing environment. They look like a form of ‘artificial life
…
separates them from self-collapse.22 Biological systems are essentially autopoietic: their parts make their structures that make their parts. Research into autocatalytic reactions and cellular automata has shown how autopoietic systems might have emerged: given the right initial conditions simple local interactions become emergent features of extended hierarchical networks. In the
…
algorithm that is Turing complete and lifelike – and there might be more.23 This profound correlation between cellular automata and biological phenomena suggests that life is governed by recursive computations, probably similar – or identical – to cellular automata. There is one more special feature of complex computations that is worth noting. They are fractal-like
…
life and cognition. For instance, instead of writing software to represent knowledge about the world, we could perhaps compel interconnected neuristors to become autopoietic using cellular automata. Knowledge from the study of the neural correlates, or signatures, of consciousness will also be applied to this newly engineered, brain-like medium. Instead of
…
of abrupt phase transitions on the scale of an ecosystem. 23There exist 88 possible unique elementary cellular automata, but only Rule 110 has been proven to be Turing complete so far. It is possible that other unique cellular automata are also Turing complete, but more complex. 24Baron-Cohen, S. (1997), Mindblindness: an essay on
…
33–4 calculating machines 219–27 Cameron, James 66 Capgras Syndrome 70–3 Cars (film) 20 cave paintings 9, 10, 16, 17, 20–1, 23 cellular automata 295–6 Chabris, Christopher 160 Chalmers, David xiv–xvi, 121 Chambers, John 252 Changeux, Jean-Pierre 166–7 chemistry, organic and inorganic 39–40 chess
Applied Cryptography: Protocols, Algorithms, and Source Code in C
by Bruce Schneier · 10 Nov 1993
.2 DSA Variants 20.3 Gost Digital Signature Algorithm 20.4 Discrete Logarithm Signature Schemes 20.5 Ong-Schnorr-Shamir 20.6 ESIGN 20.7 Cellular Automata 20.8 Other Public-Key Algorithms Chapter 21—Identification Schemes 21.1 Feige-Fiat-Shamir 21.2 Guillou-Quisquater 21.3 Schnorr 21.4 Converting
…
going to do it; he designed 3-Way instead (see Section 14.5). 13.11 CA-1.1 CA is a block cipher built on cellular automata, designed by Howard Gutowitz [677, 678, 679]. It encrypts plaintext in 384-bit blocks and has a 1088-bit key (it’s really two keys
…
, a 1024-bit key and a 64-bit key). Because of the nature of cellular automata, the algorithm is most efficient when implemented in massively parallel integrated circuits. CA-1.1 uses both reversible and irreversible cellular automaton rules. Under a
…
to correlation attacks [1451]. Cellular Automaton Generator In [1608,1609], Steve Wolfram proposed using a one-dimensional cellular automaton as a pseudo-random-number generator. Cellular automata is not the subject of this book, but Wolfram’s generator consisted of a one-dimensional array of bits, a1, a2, a3,..., ak,..., an, and
…
function based on the knapsack problem (see Section 19.2) [414]; it can be broken in about 232 operations [290, 1232, 787]. Steve Wolfram’s cellular automata [1608] have been proposed as a basis for one-way hash functions. An early implementation [414] is insecure [1052, 404]. Another one-way hash function
…
, Cellhash [384,404], and an improved version, Subhash [384,402, 405], are based on cellular automata; both are designed for hardware. Boognish mixes the design principles of Cellhash with those of MD4 [402, 407]. StepRightUp can be implemented as a hash
…
ISBN: 0471128457 Publication Date: 01/01/96 Search this book: Go! Previous Table of Contents Next ----------- 20.7 Cellular Automata A new and novel idea, studied by Papua Guam [665], is the use of cellular automata in public-key cryptosystems. This system is still far too new and has not been studied extensively, but
…
examination suggests that it may have a cryptographic weakness similar to one seen in other cases [562]. Still, this is a promising area of research. Cellular automata have the property that, even if they are invertible, it is impossible to calculate the predecessor of an arbitrary state by reversing the rule for
…
Linear Transform Public Key Cryptosystem,” Acta Electronica Sinica, v. 20, n. 4, Apr 1992, pp. 21–24. (In Chinese.) 83. P.H. Bardell, “Analysis of Cellular Automata Used as Pseudorandom Pattern Generators,” Proceedings of 1990 International Test Conference, pp. 762–768. 84. T. Baritaud, H. Gilbert, and M. Girault, “FFT Hashing is
…
, R. Govaerts, and J. Vandewalle, “A Framework for the Design of One–Way Hash Functions Including Cryptanalysis of Damgård’s One–Way Function Based on Cellular Automata,” Advances in Cryptology—ASIACRYPT ’91 Proceedings, Springer–Verlag, 1993, pp. 82–96. 405. J. Daeman, R. Govaerts, and J. Vandewalle, “A Hardware Design Model for
…
Apparatus for Encryption, Decryption, and Authentication Using Dynamical Systems,” U.S. Patent #5,365,589, 15 Nov 1994. 679. H. Gutowitz, “Cryptography with Dynamical Systems,” Cellular Automata and Cooperative Phenomenon, Kluwer Academic Press, 1993. 680. R.K. Guy, “How to Factor a Number,” Fifth Manitoba Conference on Numeral Mathematics Congressus Numerantium, v
…
Ciphers,” Journal of Cryptology, v. 1, n. 3, 1989, pp. 159–176. 1052. W. Meier and O. Staffelbach, “Analysis of Pseudo Random Sequences Generated by Cellular Automata,” Advances in Cryptology—EUROCRYPT ’91 Proceedings, Springer–Verlag, 1991, pp. 186–199. 1053. W. Meier and O. Staffelbach, “Correlation Properties of Combiners with Memory in
…
the 1984 Symposium on Security and Privacy, 1984, pp. 88–90. 1608. S. Wolfram, “Random Sequence Generation by Cellular Automata,” Advances in Applied Mathematics, v. 7, 1986, pp. 123–169. 1609. S. Wolfram, “Cryptography with Cellular Automata,” Advances in Cryptology—CRYPTO ’85 Proceedings, Springer–Verlag, 1986, pp. 429–432. 1610. T.Y.C. Woo
…
cash Cassells, Ian, 381 CAST, 334–335 S-boxes, 349 CBC, see Cipher block chaining mode CCEP, 269, 598–599 CDMF, 366, 574 Cellhash, 446 Cellular automata, 500 Cellular automaton generator, 414 Certificates: Privacy-Enhanced Mail, 579 public-key, 185–187 X.509, 574–575 Certification authority, 186 Certification path, 576 Certified
…
with, 50 multiple, 39–40 Guillou-Quisquater, 510 nonrepudiation, 40 oblivious, 117 protocol, 40 proxy, 83 public-key algorithms, 483–502 Cade algorithm, 500–501 cellular automata, 500 Digital Signature Algorithm, see Digital Signature Algorithm discrete logarithm signature schemes, 496–498 ESIGN, 499–500 GOST digital signature algorithm, 495–496 Digital signatures
Turing's Cathedral
by George Dyson · 6 Mar 2012
Neumann at this time about information propagation and switching among hypothetical arrays of cells,” remembers Bigelow, “and I believe that some germs of his later cellular automata studies may have originated here.”20 “We did not move information from one place to another except in a positive way,” emphasizes James Pomerene. “That
…
year.”70 Four of the twentieth century’s most imaginative ideas for leveraging our intelligence—the Monte Carlo method, the Teller-Ulam invention, self-reproducing cellular automata, and nuclear pulse propulsion—originated with help from Stan. Three of the four proved to be wildly successful, and the fourth was abandoned before it
…
than the sun by letting a burst of radiation in, and then, for an equilibrium-defying instant, not letting radiation out. Ulam’s self-reproducing cellular automata—patterns of information persisting across time—evolve by letting order in but not letting order out. When Nicholas Metropolis and Stanley Frankel began coding the
…
no matter how large model),” noted Ulam, who then sketched out how he and von Neumann had hypothesized the evolution of Turing-complete (or “universal”) cellular automata within a digital universe of communicating memory cells. The definitions had to be made mathematically precise: A “universal” automaton is a finite system which given
…
on error-correcting codes in translating from one generation to the next. “Ulam!” probably refers to Ulam’s interest in the powers of Turing-complete cellular automata, now evidenced by many of the computational processes surrounding us today. The triplicate appearance of “Turing!” reflects how central Turing’s proof of universality was
…
, 14.1, 16.1, 18.1 Atomic Energy for Military Purposes (Smyth, 1945), 7.1, 18.1 Auerbach, Anna Augenstein, Bruno (1923–2005) automata, see cellular automata; self-reproducing automata Automatic Computing Engine (ACE), 8.1, 13.1, 15.1, 17.1 AVIDAC (Argonne Version of the Institute’s Digital Automatic Computer
…
, 18.1 cathode-ray tube (CRT), 1.1, 5.1, 8.1, 14.1 proposed as memory (1945) see also Williams (memory) tubes cell phones cellular automata, 8.1, 11.1, 11.2, 11.3, 15.1 central arithmetic unit, 5.1, 8.1, 8.2, 8.3, 12.1 Central Park
…
, 10.2, 10.3, 11.1, 11.2, 11.3, 11.4, 14.1, 14.2, 15.1, 15.2, 16.1, 16.2 on cellular automata, 11.1, 11.2 childhood and education and digital universe, 11.1, 11.2, 16.1 on Gödel and Leibniz on Hungarians and hydrogen bomb
…
Neumann at this time about information propagation and switching among hypothetical arrays of cells,” remembers Bigelow, “and I believe that some germs of his later cellular automata studies may have originated here.” (Shelby White and Leon Levy Archives Center, Institute for Advanced Study) Left to right: James Pomerene, Julian Bigelow, and Herman
Darwin Among the Machines
by George Dyson · 28 Mar 2012 · 463pp · 118,936 words
, ed., Views on General Systems Theory, Proceedings of the Second Systems Symposium at Case Institute of Technology, 1964; reprinted in Arthur Burks, ed., Essays on Cellular Automata (Urbana: University of Illinois Press, 1970), 218. 41.John von Neumann, 1948, “The General and Logical Theory of Automata,” in Lloyd A. Jeffress, ed., Cerebral
The Singularity Is Nearer: When We Merge with AI
by Ray Kurzweil · 25 Jun 2024
computation. In his 2002 book A New Kind of Science, Wolfram sheds light on phenomena that have both deterministic and nondeterministic properties—mathematical objects called cellular automata.[18] Cellular automata are simple models represented by “cells” that alternate between states (e.g., black or white, dead or alive) based on one of many possible
…
of nearby cells. This process unfolds over a series of discrete steps and can produce highly complex behavior. One of the most famous examples of cellular automata is called Conway’s Game of Life and uses a two-dimensional grid.[19] Hobbyists and mathematicians have found numerous interesting shapes that form predictably
…
, all exhibit a class 4 type of coding.[27] We inhabit a world that is deeply affected by the kind of patterning found in such cellular automata—a very simple algorithm producing highly complex behavior straddling the boundary between order and chaos. It is this complexity in us that may give rise
…
range of other natural phenomena. Wolfram makes a forceful case that the laws of physics themselves arise from some kinds of computational rules related to cellular automata. In 2020 he announced the Wolfram Physics Project—an ambitious ongoing effort to understand all of physics via a model that is analogous to
…
cellular automata but more generalized.[28] This would allow a sort of compromise between classical determinism and quantum indeterminism. While some parts of the macro-scale world
…
future states. That may be a good reason that the universe exists. Stated differently, if the rules of a universe are based on something like cellular automata, the only way for them to be expressed would be through unfolding step-by-step—through reality actually happening. By contrast, if a universe had
…
.uk/books?id=yEEITQSyxAMC. BACK TO NOTE REFERENCE 17 For deeper explanations and demonstrations of cellular automata, see Daniel Shiffman, “Cellular Automata,” chap. 7 in The Nature of Code (Magic Book Project, 2012), https://natureofcode.com/book/chapter-7-cellular-automata; Devin Acker, “Elementary Cellular Automaton,” Github.io, accessed March 10, 2023, http://devinacker.github.io
…
/celldemo; Francesco Berto and Jacopo Tagliabue, “Cellular Automata,” in Stanford Encyclopedia of Philosophy, ed. Edward N. Zalta (Fall 2017), https://plato.stanford
…
.edu/archives/fall2017/entries/cellular-automata. BACK TO NOTE REFERENCE 18 “John Conway’s Game of Life,” Bitstorm.org, accessed March 10
…
, wolframscience.com/nks. BACK TO NOTE REFERENCE 24 For Wolfram’s foundational paper on cellular automata and complexity, see Stephen Wolfram, “Cellular Automata as Models of Complexity,” Nature 311, no. 5985 (October 1984), https://www.stephenwolfram.com/publications/academic/cellular-automata-models-complexity.pdf. BACK TO NOTE REFERENCE 25 For a quick explainer on emergence, see
…
. See also autonomous vehicles CAR-T cell therapy reprogram, 190, 239 causal inference, 56 CBS TV, 220 cell phones. See smartphones cell therapies, 190, 239 cellular automata, 82–88, 83, 84, 85 cellular emulations, 104 Centers for Disease Control (CDC), 242–43 cerebellum, 11, 29–33 fixed action patterns, 32–33 functions
…
(EEGs), 69–70 electromagnetism, 7, 96 electromechanical relays, 40, 168 electron beam-based atom placement, 251 electronics, 143, 208, 252 electrons, 7, 97, 172 elementary cellular automata, 83, 83–86, 84, 85 elements, 30, 97, 268 elephants, 37, 46, 59 eliciting latent knowledge, 282 emergence, 86, 87–88 empathy, 109, 153, 291
…
France Asilomar Principles, 280 crime, 149 education and literacy, 125, 125, 127 nuclear weapons, 269 poverty rate, 117 free market, 283 free will, 82–90 cellular automata, 82–88 definition of, 82 dilemma of more than one brain per human, 88–90 freight shipping, 185 Freitas, Robert A., 263, 275, 277, 398n
…
in the US since 1900, 205 marginal cost, 211, 212 Mark 1 Perceptron, 27 Markman, Art, 116 Maslow’s hierarchy of needs, 228, 229 mathematics cellular automata, 82–88 singularity, 1–2 Matrioshka brains, 105 Mayflower (ship), 113 Mazurenko, Roman, 100, 102 McCarthy, John, 12–13 McKibben, Bill, 267 McKinsey & Company, 198
Think Complexity
by Allen B. Downey · 23 Feb 2012 · 247pp · 43,430 words
That? 5. Scale-Free Networks Zipf’s Law Cumulative Distributions Continuous Distributions Pareto Distributions Barabási and Albert Zipf, Pareto, and Power Laws Explanatory Models 6. Cellular Automata Stephen Wolfram Implementing CAs CADrawer Classifying CAs Randomness Determinism Structures Universality Falsifiability What Is This a Model Of? 7. Game of Life Implementing Life Life
…
discrete models of physical systems. In particular, it focuses on complex systems, which are systems with many interacting components. Complex systems include networks and graphs, cellular automata, agent-based models and swarms, fractals and self-organizing systems, chaotic systems, and cybernetic systems. These terms might not mean much to you at this
…
/Complex_systems. A New Kind of Science In 2002, Stephen Wolfram published A New Kind of Science, where he presents his and others’ work on cellular automata and describes a scientific approach to the study of computational systems. We’ll get back to Wolfram in Chapter 6, but I want to borrow
…
discrete Classical models tend to be based on continuous mathematics like calculus; models of complex systems are often based on discrete mathematics, including graphs and cellular automata. Linear non-linear Classical models are often linear or use linear approximations to non-linear systems; complexity science is more friendly to non-linear models
…
competing models? Do these criteria influence your opinion about the WS and BA models? Are there other criteria you think should be considered? Chapter 6. Cellular Automata A cellular automaton is a model of a world with very simple physics. “Cellular” means that the space is divided into discrete chunks, called cells
…
in space (if not time) and nonlinear, so the complexity of their behavior is not entirely surprising. Wolfram’s demonstration of complex behavior in simple cellular automata is more surprising—and disturbing, at least to a deterministic world view. So far I have focused on scientific challenges to determinism, but the longest
…
to Popper’s claim? Do you get the sense that practicing philosophers think highly of Popper’s work? What Is This a Model Of? Some cellular automata are primarily mathematical artifacts. They are interesting because they are surprising, useful, or pretty, or because they provide tools for creating new mathematics (like the
…
are not very detailed or realistic. For example, some species of cone snail produce a pattern on their shells that resembles the patterns generated by cellular automata (see http://en.wikipedia.org/wiki/Cone_snail). It is natural to suppose that a CA is a model of the mechanism that produces patterns
…
realism adds no explanatory power. Figure 6-7. The logical structure of a simple physical model Chapter 7. Game of Life One of the first cellular automata to be studied (and probably the most popular of all time) is a 2D CA called “The Game of Life,” or GoL for short. It
…
, is the limit of this ratio as goes to zero. Fractal CAs To investigate the behavior of the fractal dimension, we’ll apply it to cellular automata. Box counting for CAs is simple; we just count the number of “on” cells. As an example, consider Rule 254. Figure 8-1 shows what
…
. What we call “laws” are often computational shortcuts that allow us to predict the outcome of a system without building or observing it. But many cellular automata are computationally irreducible, which means that there are no shortcuts. The only way to get the outcome is to implement the system. The same may
…
, Turtles, Termites, and Traffic Jams Rucker, The Lifebox, The Seashell, and The Soul Sawyer, Social Emergence: Societies As Complex Systems Schelling, Micromotives and Macrobehaviors Schiff, Cellular Automata: A Discrete View of the World Strogatz, Sync Watts, Six Degrees Wolfram, A New Kind of Science Index A note on the digital index A
…
, Boids causation, Determinism, SOC, Causation, and Prediction, Thomas Schelling Cdf class, Cumulative Distributions CDFs, Cumulative Distributions, Cumulative Distributions plotting, Cumulative Distributions cells, Universality cellular automaton, Cellular Automata centralized system, A New Kind of Engineering chaos, Determinism Church-Turing thesis, Universality circular buffer, FIFO Implementation CircularCA, CADrawer Class 3 behavior, Randomness Class 4
…
behavior, Universality, Conway’s Conjecture classifying cellular automata, Classifying CAs client-server architecture, A New Kind of Engineering clique, Watts and Strogatz clustering, Watts and Strogatz clustering coefficient, Watts and Strogatz color map
…
Power Laws demarcation problem, Falsifiability deque, FIFO Implementation design, A New Kind of Engineering determinism, The Axes of Scientific Models, A New Kind of Thinking, Cellular Automata, Randomness, Determinism Detroit, A New Kind of Science DFT, Spectral Density DictFifo, FIFO Implementation dictionary, Representing Graphs, Iterators, FIFO Implementation nested dictionary, Representing Graphs dictionary
…
, The Axes of Scientific Models homogeneous, The Axes of Scientific Models hop, Stanley Milgram hurricane, Realism, Instrumentalism I id, Instrumentalism immutable objects, Representing Graphs implementing cellular automata, Implementing CAs implementing Game of Life, Implementing Life in operator, Analysis of Search Algorithms incompleteness, A New Kind of Thinking Incompleteness Theorem, A New Kind
…
get richer, Barabási and Albert road network, What’s a Graph? robust, Dijkstra, Zipf, Pareto, and Power Laws rule table, Stephen Wolfram rules, Pareto Distributions, Cellular Automata, Stephen Wolfram, Classifying CAs, Randomness, Randomness, Structures, Fractal CAs, Fractal CAs 80/20 rule, Pareto Distributions “Rule 110”, Structures “Rule 18”, Classifying CAs, Fractal CAs
…
, The Axes of Scientific Models square, Fractals stable sort, Analysis of Basic Python Operations Stanford Large Network Dataset Collection, Zipf, Pareto, and Power Laws state, Cellular Automata, Stephen Wolfram, Sand Piles stochastic process, The Axes of Scientific Models stock market, SOC, Causation, and Prediction StopIteration, Iterators __str__, Representing Graphs, Representing Graphs strategy
…
Die, A New Kind of Thinking Think Python, What Is This Book About?, Implementing Life threshold value, Paul Erdős: Peripatetic Mathematician, Speed Freak time step, Cellular Automata timeit, Summing Lists tipping point, Percolation top-down, A New Kind of Engineering topology, Barabási and Albert torus, Game of Life totalistic, Game of Life
The Deep Learning Revolution (The MIT Press)
by Terrence J. Sejnowski · 27 Sep 2018
Artificial Whiteness
by Yarden Katz
Fancy Bear Goes Phishing: The Dark History of the Information Age, in Five Extraordinary Hacks
by Scott J. Shapiro · 523pp · 154,042 words
Rage Inside the Machine: The Prejudice of Algorithms, and How to Stop the Internet Making Bigots of Us All
by Robert Elliott Smith · 26 Jun 2019 · 370pp · 107,983 words
How to Create a Mind: The Secret of Human Thought Revealed
by Ray Kurzweil · 13 Nov 2012 · 372pp · 101,174 words
The Demon in the Machine: How Hidden Webs of Information Are Finally Solving the Mystery of Life
by Paul Davies · 31 Jan 2019 · 253pp · 83,473 words
Darwin's Dangerous Idea: Evolution and the Meanings of Life
by Daniel C. Dennett · 15 Jan 1995 · 846pp · 232,630 words
Possible Minds: Twenty-Five Ways of Looking at AI
by John Brockman · 19 Feb 2019 · 339pp · 94,769 words
Radical Technologies: The Design of Everyday Life
by Adam Greenfield · 29 May 2017 · 410pp · 119,823 words
Masterminds of Programming: Conversations With the Creators of Major Programming Languages
by Federico Biancuzzi and Shane Warden · 21 Mar 2009 · 496pp · 174,084 words
Tools for Thought: The History and Future of Mind-Expanding Technology
by Howard Rheingold · 14 May 2000 · 352pp · 120,202 words
The Transhumanist Reader
by Max More and Natasha Vita-More · 4 Mar 2013 · 798pp · 240,182 words
Rationality: From AI to Zombies
by Eliezer Yudkowsky · 11 Mar 2015 · 1,737pp · 491,616 words
The Age of Spiritual Machines: When Computers Exceed Human Intelligence
by Ray Kurzweil · 31 Dec 1998 · 696pp · 143,736 words
Accelerando
by Stross, Charles · 22 Jan 2005 · 489pp · 148,885 words
The Blockchain Alternative: Rethinking Macroeconomic Policy and Economic Theory
by Kariappa Bheemaiah · 26 Feb 2017 · 492pp · 118,882 words
The Cultural Logic of Computation
by David Golumbia · 31 Mar 2009 · 268pp · 109,447 words
Some Remarks
by Neal Stephenson · 6 Aug 2012 · 335pp · 107,779 words
From eternity to here: the quest for the ultimate theory of time
by Sean M. Carroll · 15 Jan 2010 · 634pp · 185,116 words
Epigenetics: How Environment Shapes Our Genes
by Richard C. Francis · 14 May 2012
Machines of Loving Grace: The Quest for Common Ground Between Humans and Robots
by John Markoff · 24 Aug 2015 · 413pp · 119,587 words
When Things Start to Think
by Neil A. Gershenfeld · 15 Feb 1999 · 238pp · 46 words
The Road to Ruin: The Global Elites' Secret Plan for the Next Financial Crisis
by James Rickards · 15 Nov 2016 · 354pp · 105,322 words
The End of Theory: Financial Crises, the Failure of Economics, and the Sweep of Human Interaction
by Richard Bookstaber · 1 May 2017 · 293pp · 88,490 words
Future Politics: Living Together in a World Transformed by Tech
by Jamie Susskind · 3 Sep 2018 · 533pp
Singularity Sky
by Stross, Charles · 28 Oct 2003 · 448pp · 116,962 words
Practical OCaml
by Joshua B. Smith · 30 Sep 2006
Brief Peeks Beyond: Critical Essays on Metaphysics, Neuroscience, Free Will, Skepticism and Culture
by Bernardo Kastrup · 28 May 2015 · 244pp · 73,966 words
Making Sense of Chaos: A Better Economics for a Better World
by J. Doyne Farmer · 24 Apr 2024 · 406pp · 114,438 words
Anathem
by Neal Stephenson · 25 Aug 2009 · 1,087pp · 325,295 words
When Einstein Walked With Gödel: Excursions to the Edge of Thought
by Jim Holt · 14 May 2018 · 436pp · 127,642 words
The Musical Human: A History of Life on Earth
by Michael Spitzer · 31 Mar 2021 · 632pp · 163,143 words
Coders: The Making of a New Tribe and the Remaking of the World
by Clive Thompson · 26 Mar 2019 · 499pp · 144,278 words
Is God a Mathematician?
by Mario Livio · 6 Jan 2009 · 315pp · 93,628 words
Chaos: Making a New Science
by James Gleick · 18 Oct 2011 · 396pp · 112,748 words
Life After Google: The Fall of Big Data and the Rise of the Blockchain Economy
by George Gilder · 16 Jul 2018 · 332pp · 93,672 words
The Master Algorithm: How the Quest for the Ultimate Learning Machine Will Remake Our World
by Pedro Domingos · 21 Sep 2015 · 396pp · 117,149 words
Public Places, Urban Spaces: The Dimensions of Urban Design
by Matthew Carmona, Tim Heath, Steve Tiesdell and Taner Oc · 15 Feb 2010 · 1,233pp · 239,800 words
Blockchain: Blueprint for a New Economy
by Melanie Swan · 22 Jan 2014 · 271pp · 52,814 words
Our Final Invention: Artificial Intelligence and the End of the Human Era
by James Barrat · 30 Sep 2013 · 294pp · 81,292 words
The Hacker's Diet
by John Walker
Skin in the Game: Hidden Asymmetries in Daily Life
by Nassim Nicholas Taleb · 20 Feb 2018 · 306pp · 82,765 words
The Most Human Human: What Talking With Computers Teaches Us About What It Means to Be Alive
by Brian Christian · 1 Mar 2011 · 370pp · 94,968 words
Thinking Machines: The Inside Story of Artificial Intelligence and Our Race to Build the Future
by Luke Dormehl · 10 Aug 2016 · 252pp · 74,167 words
Bad Data Handbook
by Q. Ethan McCallum · 14 Nov 2012 · 398pp · 86,855 words
The system of the world
by Neal Stephenson · 21 Sep 2004 · 1,199pp · 384,780 words
All Your Base Are Belong to Us: How Fifty Years of Video Games Conquered Pop Culture
by Harold Goldberg · 5 Apr 2011 · 329pp · 106,831 words
Mathematics for Finance: An Introduction to Financial Engineering
by Marek Capinski and Tomasz Zastawniak · 6 Jul 2003
Cities Are Good for You: The Genius of the Metropolis
by Leo Hollis · 31 Mar 2013 · 385pp · 118,314 words
Debunking Economics - Revised, Expanded and Integrated Edition: The Naked Emperor Dethroned?
by Steve Keen · 21 Sep 2011 · 823pp · 220,581 words
The Data Revolution: Big Data, Open Data, Data Infrastructures and Their Consequences
by Rob Kitchin · 25 Aug 2014
Traffic: Why We Drive the Way We Do (And What It Says About Us)
by Tom Vanderbilt · 28 Jul 2008 · 512pp · 165,704 words