Bjorndahl: The Epistemology of Nondeterminism

The Epistemology of Nondeterminism
Adam Bjorndahl (Carnegie Mellon)
4:10 pm, Friday, March 29th, 2019
Faculty House, Columbia University

Abstract. Propositional dynamic logic (PDL) is a framework for reasoning about nondeterministic program executions (or, more generally, nondeterministic actions). In this setting, nondeterminism is taken as a primitive: a program is nondeterministic iff it has multiple possible outcomes. But what is the sense of “possibility” at play here? This talk explores an epistemic interpretation: working in an enriched logical setting, we represent nondeterminism as a relationship between a program and an agent deriving from the agent’s (in)ability to adequately measure the dynamics of the program execution. More precisely, using topology to capture the observational powers of an agent, we define the nondeterministic outcomes of a given program execution to be those outcomes that the agent is unable to rule out in advance. In this framework, determinism coincides exactly with continuity: that is, determinism is continuity in the observation topology. This allows us to embed PDL into (dynamic) topological (subset space) logic, laying the groundwork for a deeper investigation into the epistemology (and topology) of nondeterminism.

Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s