Incompatibilities Between Iterated and Relevance-Sensitive Belief Revision

The AGM paradigm for belief change, as originally introduced by Alchourron, Gärdenfors and Makinson, lacks any guidelines for the process of iterated revision. One of the most influential work addressing this problem is Darwiche and Pearl's approach (DP approach, for short), which, despite its well-documented shortcomings, remains to this date the most dominant. In this article, we make further observations on the DP approach. In particular, we prove that the DP postulates are, in a strong sense, inconsistent with Parikh's relevance-sensitive axiom (P), extending previous initial conflicts. Immediate consequences of this result are that an entire class of intuitive revision operators, which includes Dalal's operator, violates the DP postulates, as well as that the Independence postulate and Spohn's conditionalization are inconsistent with axiom (P). The whole study, essentially, indicates that two fundamental aspects of the revision process, namely, iteration and relevance, are in deep conflict, and opens the discussion for a potential reconciliation towards a comprehensive formal framework for knowledge dynamics.

Full Characterization of Parikh's Relevance-Sensitive Axiom for Belief Revision

In this article, the epistemic-entrenchment and partial-meet characterizations of Parikh's relevance-sensitive axiom for belief revision, known as axiom (P), are provided. In short, axiom (P) states that, if a belief set $K$ can be divided into two disjoint compartments, and the new information $\varphi$ relates only to the first compartment, then the revision of $K$ by $\varphi$ should not affect the second compartment. Accordingly, we identify the subclass of epistemic-entrenchment and that of selection-function preorders, inducing AGM revision functions that satisfy axiom (P). Hence, together with the faithful-preorders characterization of (P) that has already been provided, Parikh's axiom is fully characterized in terms of all popular constructive models of Belief Revision. Since the notions of relevance and local change are inherent in almost all intellectual activity, the completion of the constructive view of (P) has a significant impact on many theoretical, as well as applied, domains of Artificial Intelligence.

Self-referential basis of undecidable dynamics: From the Liar paradox and the halting problem to the edge of chaos

In this paper we explore several fundamental relations between formal systems, algorithms, and dynamical systems, focussing on the roles of undecidability, universality, diagonalization, and self-reference in each of these computational frameworks. Some of these interconnections are well-known, while some are clarified in this study as a result of a fine-grained comparison between recursive formal systems, Turing machines, and Cellular Automata (CAs). In particular, we elaborate on the diagonalization argument applied to distributed computation carried out by CAs, illustrating the key elements of Gödel's proof for CAs. The comparative analysis emphasizes three factors which underlie the capacity to generate undecidable dynamics within the examined computational frameworks: (i) the program-data duality; (ii) the potential to access an infinite computational medium; and (iii) the ability to implement negation. The considered adaptations of Gödel's proof distinguish between computational universality and undecidability, and show how the diagonalization argument exploits, on several levels, the self-referential basis of undecidability.