Abduction, Unpredictability and Garden of Eden

Chiaki Sakama and Katsumi Inoue

Logic Journal of the IGPL, vol.21(6), pages 980-998, 2013.

Abstract

The notion of unpredictability has been a central theme in both natural and social sciences. In this paper, we first provide a formal account of unpredictability based on abduction. An abductive framework is defined as a pair where B is a background theory and H is a hypothesis space. Then, an event E is predictable under if there is a hypothesis h in H such that B & h implies E. By contrast, an event E is unpredictable under if it is not predictable under . We investigate formal properties of (un)predictability of events and argue its computational complexity. Next, we apply the notion of (un)predictability to the problem of identifying patterns in cellular automata (CAs). In CAs it is generally unforeseen whether a particular pattern is produced by a transition rule from the initial configuration. We represent CAs in abductive frameworks and relate the emergence of configurations to the predictability of events from the initial configuration. On the other hand, a configuration that cannot be reached by any initial configuration is called a Garden of Eden (GOE). We then characterize a GOE as an unpredictable event in an abductive framework. We show methods of computing CA configurations and checking GOE in logic programming.

Full Paper (PDF 160K)

Slide