Category: Papers

Rule Primality, Minimal Generating Sets and Turing-Universality in the Causal Decomposition of Elementary Cellular Automata

New Universality results in Elementary Cellular Automata by emulation of Rule 110 just published by the Journal of Cellular Automata: https://goo.gl/vWQsCk . Also available at: https://arxiv.org/abs/1802.08769  includes a minimal set of only 38 ECAs generating all others under composition and 2 new Turing universal 4-colour cellular automata.

 

"We introduce several concepts such as prime and composite rule, tools and methods for causal composition and decomposition. We discover and prove new universality results in ECA, namely, that the Boolean composition of ECA rules 51 and 118, and 170, 15 and 118 can emulate ECA rule 110 and are thus Turing-universal coupled systems. We construct two 4-colour Turing-universal cellular automata that carries the Boolean composition of the 2 and 3 ECA rules emulating ECA rule 110 under multi-scale coarse-graining. We find that rules generating the ECA rulespace by Boolean composition are of low complexity and comprise prime rules implementing basic operations that when composed enable complex behaviour. We also found a candidate minimal set with only 38 ECA prime rules — and several other small sets — capable of generating all other (non-trivially symmetric) 88 ECA rules under Boolean composition."

Source: www.oldcitypublishing.com

Tomorrow’s Earth

As the human population has grown over recent decades, our profound impact on the entire planet has become starkly apparent. Increasing affluence has led to expectations of good-quality health care, full employment, and the ability to live in cities that are safe, affordable, and clean. Yet these advantages for some come at a cost to others and to the planet itself. Human activities have led to a warming climate, massive landscape conversion, pollution, depletion of natural resources (crucially, fresh water and soil), defaunation, and loss of biodiversity. Today, global human society stands at a decision point. Business-as-usual approaches are likely to lead to catastrophic changes to our planet and our health and well-being. What will it take for universal recognition of our perilous position, and how can we begin to make the often-difficult changes required to live in a more sustainable, cooperative, and compassionate way? In this special series, we call attention to these choices and explore some of the possible routes to a more sustainable future.

Source: science.sciencemag.org

The power of many

Three billion years ago, more or less, life crossed a threshold and began moving toward a multicellular existence. Evidence from multiple directions is showing how this hard-to-fathom leap might have been less difficult than once believed. The evolutionary histories of some groups of organisms record numerous transitions from single-celled to multicellular forms, suggesting the hurdles could not have been so high. Genetic comparisons between simple multicellular organisms and their single-celled relatives have revealed that much of the molecular equipment needed for cells to band together and coordinate their activities may have been in place well before multicellularity evolved. And clever experiments have shown that in the test tube, single-celled life can evolve the beginnings of multicellularity in just a few hundred generations—an evolutionary instant. The end result: the incredible diversity of life seen today.

 

The power of many
Elizabeth Pennisi
Science  29 Jun 2018:
Vol. 360, Issue 6396, pp. 1388-1391
DOI: 10.1126/science.360.6396.1388

Source: science.sciencemag.org

Social Physics: Uncovering Human Behaviour from Communication

In the post year 2000 era the technologies that facilitate human communication have rapidly multiplied. While the adoption of these technologies has hugely impacted the behaviour and sociality of people, specifically in urban but also in rural environments, their "digital footprints" on different data bases have become an active area of research. The existence and accessibility of such large population-level datasets, has allowed scientists to study and model innate human tendencies and social patterns in an unprecedented way that complements traditional research approaches like questionnaire studies. In this review we focus on data analytics and modelling research – we call Social Physics – as it has been carried out using the mobile phone data sets to get insight into the various aspects of human sociality, burstiness in communication, mobility patterns, and daily rhythms.

 

Social Physics: Uncovering Human Behaviour from Communication
Kunal Bhattacharya, Kimmo Kaski

Source: arxiv.org

Assessing diversity in multiplex networks

Diversity, understood as the variety of different elements or configurations that an extensive system has, is a crucial property that allows maintaining the system’s functionality in a changing environment, where failures, random events or malicious attacks are often unavoidable. Despite the relevance of preserving diversity in the context of ecology, biology, transport, finances, etc., the elements or configurations that more contribute to the diversity are often unknown, and thus, they can not be protected against failures or environmental crises. This is due to the fact that there is no generic framework that allows identifying which elements or configurations have crucial roles in preserving the diversity of the system. Existing methods treat the level of heterogeneity of a system as a measure of its diversity, being unsuitable when systems are composed of a large number of elements with different attributes and types of interactions. Besides, with limited resources, one needs to find the best preservation policy, i.e., one needs to solve an optimization problem. Here we aim to bridge this gap by developing a metric between labeled graphs to compute the diversity of the system, which allows identifying the most relevant components, based on their contribution to a global diversity value. The proposed framework is suitable for large multiplex structures, which are constituted by a set of elements represented as nodes, which have different types of interactions, represented as layers. The proposed method allows us to find, in a genetic network (HIV-1), the elements with the highest diversity values, while in a European airline network, we systematically identify the companies that maximize (and those that less compromise) the variety of options for routes connecting different airports.

Assessing diversity in multiplex networks
L.C. Carpi, T.A. Schieber, P.M. Pardalos, G. Marfany, C. Masoller, A. Díaz-Guilera, M.G. Ravetti

Source: arxiv.org