Accumulative knowledge under bounded resources

摘要

A possible purpose of performing an action is to gather information. Such information-collecting actions are usually resource-consuming. The resources needed for performing them can be for example time or memory, but also money, specialized equipment, etc. In this work, we propose a formal framework to study how the ability of an agent to improve its knowledge changes as a result of changing the available resources. We introduce a model for resource-consuming information-collecting actions, and show how the process of accumulating knowledge can be modelled. Based on this model, we propose a modal logic for reasoning about the epistemic abilities of agents. We present some validities of the logic, and show that the model-checking problem sits in the first level of polynomial hierarchy. We also discuss the connection between our framework and classic information theory. More specifically, we show that the notion of uncertainty given by Hartley measure can be seen as a special case of an agent's ability to improve its knowledge using information-collecting actions.