This essay, based on a series of discussions between the authors, is a loosely edited collage in which we work to flesh out our shared interests in non-traditional machines and coding mechanisms. We primarily focused on the idea that all human language can usefully be viewed in programming language terms — as “natural code”. Programming languages and natural languages differ in many ways, such as having relatively formal definitions versus not, emphasizing strong syntax versus large dictionaries, and demanding rigid implementations versus building on the vagaries of living systems. Still, we saw deep unities as well, much more than mere metaphor, and we glimpsed the possibility of applying humanity’s decades of programming language design and software engineering experience to the task of debugging and refactoring the natural codebase that we all share. These fragmentary and overlapping dialogues represent both a description and an example of natural code, and we offer them here, with a simple “natural API” illustration, in hopes of programming people to join in natural code development.

Emerging hardware that trades reliability guarantees for resource savings presents a challenge to software engineered for deterministic execution. Research areas like approximate computing, however, embrace non-determinism by abandoning strict correctness in favor of maximizing the probability and degree of correctness. Existing work has used stochastic failure sampling to perform white-box searches along software execution paths, producing criticality assessments of which selected operations are likely most damaging if they fail. Here, we apply these assessments to a new domain and employ them using failure shaping , an automated method for reducing a computation’s expected output damage in a model where failures can be relocated but not eliminated. In two case studies, we demonstrate error reductions of 38% to 63% on Strassen’s matrix multiplication algorithm despite a virtually identical failure count. We discuss how our framework helps provide a smooth landscape for performing the search-based software engineering that will be required to apply this technology to larger problems.

In a question-and-answer format, this summary paper presents background material for the AAAI-16 Senior Member Presentation Track “Blue Sky Ideas” talk of the same name.

Software-based artficial life will increase the robustness, and enable vastly increased size, of computing systems. To enhance human potential and protect individual liberty in future society-scale systems, the boundary between private and public digital spacesknown in telephone networks as a demarcation point or demarc should be set so that a significant amount of physical computing machinery can be counted as fundamentally personal, for assigning rights and responsibilities. To that end, this note offers a principle called the carried network demarc: The machines that you routinely carry under your own power, and their contents and interactions, should be considered part of your body as a matter of law and social norm. Such machines today may be as prosaic as a watch, pacemaker, or cellphone, but in the future you may regularly carry machines inhabited by multitudes of beneficial alife creaturesakin to the bacterial microbiomes that surround and perfuse our biological bodiesthat would likewise be considered you and yours in both their physical and computational aspects. The author solicits input from others with expertise bearing on this topic.

Traditional digital computing demands perfectly reliable memory and processing, so programs can build structures once then use them forever-but such deterministic execution is becoming ever more costly in large-scale systems. By contrast, living systems, viewed as computations, naturally tolerate fallible hardware by repairing and rebuilding structures even while in use-and suggest ways to compute using massive amounts of unreliable, merely best-effort hardware. However, we currently know little about programming without deterministic execution, in architectures where traditional models of computation-and deterministic ALife models such as the Game of Life-need not apply. This expanded article presents ulam, a language designed to balance concurrency and programmability upon best-effort hardware, using lifelike strategies to achieve robust and scalable computations. The article reviews challenges for traditional architecture, introduces the active-media computational model for which ulam is designed, and then presents the language itself, touching on its nomenclature and surface appearance as well as some broader aspects of robust software engineering. Several ulam examples are presented; then the article concludes with a brief consideration of the couplings between a computational model and its physical implementation.

We describe the content and outcomes of the First Workshop on Open-Ended Evolution: Recent Progress and Future Milestones (OEE1), held during the ECAL 2015 conference at the University of York, UK, in July 2015. We briefly summarize the content of the workshop's talks, and identify the main themes that emerged from the open discussions. Two important conclusions from the discussions are: (1) the idea of pluralism about OEE-it seems clear that there is more than one interesting and important kind of OEE; and (2) the importance of distinguishing observable behavioral hallmarks of systems undergoing OEE from hypothesized underlying mechanisms that explain why a system exhibits those hallmarks. We summarize the different hallmarks and mechanisms discussed during the workshop, and list the specific systems that were highlighted with respect to particular hallmarks and mechanisms. We conclude by identifying some of the most important open research questions about OEE that are apparent in light of the discussions. The York workshop provides a foundation for a follow-up OEE2 workshop taking place at the ALIFE XV conference in Cancún, Mexico, in July 2016. Additional materials from the York workshop, including talk abstracts, presentation slides, and videos of each talk, are available at http://alife.org/ws/oee1 .

Fault tolerance techniques often presume that the end-user computation must complete flawlessly. Though such strict correctness is natural and easy to explain, it's increasingly unaffordable for extreme-scale computations, and blind to possible preferences among errors, should they prove inevitable. In a case study on traditional sorting algorithms, we present explorations of a criticality measure defined over expected fault damage rather than probability of correctness. We discover novel 'error structure' in even the most familiar algorithms, and observe that different plausible error measures can qualitatively alter criticality relationships, suggesting the importance of explicit error measures and criticality in the wise deployment of the limited spare resources likely to be available in future extreme-scale computers.

For open-ended computational growth, we argue that: (i) instead of hardwiring and hiding component spatial relationships, computer architecture should soften and expose them; and (2) instead of relegating reliability to hardware, robustness must climb the computational stack toward the end users. We suggest that eventually all truly large-scale computers will be robust spatial computers—even if intended neither for spatial tasks nor harsh environments. This paper is an extended introduction for the spatial computing community to the Movable Feast Machine (MFM), a computing model in the spirit of an object-oriented asynchronous cellular automata. We motivate the approach and then present the model, touching on robustness mechanisms such as redundancy, compartmentalization and homeostasis. We provide simulation data from prototype movable elements such as self-healing wire for data transport and movable ‘membrane’ rings for spatial segregation, and illustrate how some larger computations like sorting or evaluating a lambda expression can be reconceived for robustness and movability within a spatial computing architecture.

This paper examines how the choice of the selection mechanism in an evolutionary algorithm impacts the objective function it optimizes, specifically when the fitness function is noisy. We provide formal results showing that, in an abstract infinite-population model, proportional selection optimizes expected fitness, truncation selection optimizes order statistics, and tournament selection can oscillate. The "winner" in a population depends on the choice of selection rule, especially when fitness distributions differ between individuals resulting in variable risk. These findings are further developed through empirical results on a novel stochastic optimization problem called "Die4", which, while simple, extends existing benchmark problems by admitting a variety of interpretations of optimality.

Injecting binary code into a running program is a common form of attack. Most defenses employ a “guard the doors” approach, blocking known mechanisms of code injection. Randomized instruction set emulation (RISE) is a complementary method of defense, one that performs a hidden randomization of an application's machine code. If foreign binary code is injected into a program running under RISE, it will not be executable because it will not know the proper randomization. The paper describes and analyzes RISE, describing a proof-of-concept implementation built on the open-source Valgrind IA32-to-IA32 translator. The prototype effectively disrupts binary code injection attacks, without requiring recompilation, linking, or access to application source code. Under RISE, injected code (attacks) essentially executes random code sequences. Empirical studies and a theoretical model are reported which treat the effects of executing random code on two different architectures (IA32 and PowerPC). The paper discusses possible extensions and applications of the RISE technique in other contexts.

Binary code injection into an executing program is a common form of attack. Most current defenses against this form of attack use a 'guard all doors' strategy, trying to block the avenues by which execution can be diverted. We describe a complementary method of protection, which disrupts foreign code execution regardless of how the code is injected. A unique and private machine instruction set for each executing program would make it difficult for an outsider to design binary attack code against that program and impossible to use the same binary attack code against multiple machines. As a proof of concept, we describe a randomized instruction set emulator (RISE), based on the open-source Valgrind x86-to-x86 binary translator. The prototype disrupts binary code injection attacks against a program without requiring its recompilation, linking, or access to source code. The paper describes the RISE implementation and its limitations, gives evidence demonstrating that RISE defeats common attacks, considers how the dense x86 instruction set affects the method, and discusses potential extensions of the idea.