In this lecture we will discuss another line of research linking formal learning theory and modal-temporal logics of belief change: the syntactic counterparts of our logical approach to identifiability, focusing on both finite identifiability (Dégremont and Gierasimczuk 2011) and identifiability in the limit (Gierasimczuk 2010, Ch. 5).
We will show how the semantics of learning can be reflected in an appropriate syntax for knowledge, belief, and their changes over time. The approach to inductive learning in the context of dynamic epistemic and epistemic temporal logic is as follows: the initial class of sets forms the range of possible worlds in an epistemic model, which mirrors Learner’s initial uncertainty over the range of sets. The incoming pieces of information are taken to be events that modify the initial model. We will show that iterated update on epistemic models based on finitely identifiable classes of sets is bound to lead to the emergence of irrevocable knowledge. In a similar way identifiability in the limit leads to the emergence of stable belief. Next, we observe that the structure resulting from updating the model with a sequence of events can be viewed as an epistemic temporal forest. We explicitly focus on protocols that are assigned to worlds in set-learning scenarios. We give a temporal characterization of forests that are generated from learning situations of finite identifiability and identifiability in the limit. We observe that a special case of this protocol-based setting, in which only one stream of events is allowed in each state, can be used to model the function-learning paradigm. We show that the simple setting of iterated epistemic update cannot account for all possible learning situations. Time permitting in the end we will discuss computational complexity results related to this work (Gierasimczuk and De Jongh 2012).
Dégremont, C., Gierasimczuk, N. (2011). Finite Identification from the Viewpoint of Epistemic Update, Information and Computation 209(3): 383-396.
Gierasimczuk, N. (2010). Knowing One’s Limits. Logical Analysis of Inductive Inference. PhD thesis, Universiteit van Amsterdam.
Gierasimczuk, N., De Jongh, D. (2012), On the Complexity of Conclusive Update, The Computer Journal 2012, Oxford University Press. doi:10.1093/comjnl/bxs059