Title: Logic omniscience and algorithmic knowledge

Speaker: Yiting Wang (PKU)

Time: 15:10 ~ 18:00  (Mar.1st)

Abstract: An ongoing research on “knowing how to solve” drives us to review the concept of“algorithmic knowledge” which was designed to overcome the problem in epistemic logic so-called “logical omniscience” by modelling resources bounded agents. Thus, this talk contains two parts. We will first discuss different forms of logical omniscience and ask how they are against our intuition about rational agents. Then we follow [Artemov and Kuznets 2014]’s approach to show that in general there exists an interesting tension between (infeasible) logical omniscience and the rules epistemic logics adapt. In the second half of this talk, we will formally talk about algorithmic knowledge which uses external resources to bound the epistemic ability of agents. In the end, we will see that algorithmic knowledge may bring more unsatisfactory “logical omniscience” like problems in applications.

Backround readings: 

Artemov, Sergei and Roman Kuznets (Jan. 1, 2014). “Logical Omniscience as Infeasibility”. In: Annals of Pure and Applied Logic. The Constructive in Logic and Applications 165.1, pp. 6–25

Halpern, Joseph Y., Moshe Y. Vardi, and Yoram Moses (1994). “Algorithmic Knowledge”. In: Proc. Second Conference on Theoretical Aspects of Reasoning about Knowledge. Morgan Kaufmann, pp. 255–266