Abduction, Unpredictability and Garden of Eden
Chiaki Sakama and Katsumi Inoue
Logic Journal of the IGPL, vol.21(6), pages 980-998, 2013.
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)