The Oxford Advanced Seminar on Informatic Structures

Introduction to OASIS

Michaelmas 2004

Hilary 2005

Trinity 2005

Michaelmas 2005

Hilary 2006

Trinity 2006

Michaelmas 2006

Hilary 2007

Trinity 2007

Michaelmas 2007

Hilary 2008

Trinity 2008

Michaelmas 2007

MODELS, ... AND MORE MODELS

Talks are Friday afternoons at 2:00 pm in the NEW Lecture Theatre B in the NEW building of the Computing Laboratory - ask at the reception for directions. The Computing Laboratory is located at the corner of Parks road and Keble road; the reception is on Parks road. Abstracts can be found at the bottom of this page. Everyone is welcome!

• Friday 26 October (week 3) [John Power] (Bath) Structural Operational Semantics for Computational Effects

• Friday 2 November (week 4) [Basil Hiley] (Birkbeck, London) Clifford algebras and shadow phase spaces in quantum theory: the way to unite Schrodinger, Pauli and Dirac with Bohm in one algebraic structure

• Friday 16 November (week 6) [Tim Palmer FRS] ([ECMWF]) Bell Inequalities, Free Variables and the Undecidability of Chaotic Invariant Sets.

• Friday 23 November (week 7) [Viv Kendon] (Leeds) Optimal computation with noisy quantum walks

• Friday 30 November (week 8) [Wilfrid Hodges] (Queen Mary, London) Ibn Sina's syllogistic: a logic between modal and many-valued

John Power's abstract (joint work with Gordon Plotkin): In seeking a unified study of computational effects, a fundamental task is to give a unified structural operational semantics, together with an adequate denotational semantics for it, in such a way that, for the leading examples of computational effects, the general definitions are consistent with the usual operational semantics for the relevant effects. One can readily produce a unified operational semantics that works fine for examples that include various forms of nondeterminism and probabilistic nondeterminism. But that simple semantics fails to yield a sensible result in the vitally important case of state or variants of state. The problem is that one must take serious account of coalgebraic structure. I shall not formally enunciate a general operational semantics and adequacy theorem in this talk, but I shall explain the category theory that supports such a semantics and theorem. I shall investigate, describe, and characterise a kind of tensor of a model and a comodel of a countable Lawvere theory, calculating it in leading examples, primarily involving state. Ultimately, this research supports a distinction between what one might call coalgebraic effects, such as state, and algebraic effects, such as nondeterminism.

Tim Palmer's abstract: Based on an analysis of the concept of free variable in physical theory, the following is demonstrated: it is impossible to prove that all members of the class of chaotic locally-causal, objectively-realistic physical theories satisfy Bell inequalities, if the states are constrained to lie on chaotic invariant subsets. This result follows from the fact that nontrivial properties of chaotic invariant sets are undecidable in the computational-theoretic sense of the word.

This motivates the formulation of what is referred to as the Invariant Set Hypothesis: not only are nonlinear dynamics fundamental to physical theory, a fortiori the global state-space geometry of the invariant set is a more primitive representation of these dynamics, than are local differential-equation expressions. In this latter sense the Invariant Set Hypothesis is fundamentally non-classical. The Invariant Set Hypothesis provides a geometric and hence relativistic framework within which the apparently nonlocal and atemporal paradoxes of quantum theory can be understood.

Wilfrid Hodges' abstract: Although the proof theory of Aristotle's categorical syllogisms has been studied to exhaustion for two thousand years or so, there has been strangely little significant work on the mathematical structures underlying them. (A rare exception is Haskell Curry in 1936.) Ibn Sina's syllogisms require us to go to a higher level of generality, which is helpful for understanding the mathematical scenery. Ibn Sina's generalisation of Aristotle is natural and could in theory be applied to any logic, though I don't know where else it might be useful.