Within the framework of a seminar on logic and computer science, the Centre for Logic and Philosophy of Science organizes a small workshop, under the name SLI-2003.  The topic of this year's workshop will be devoted to the area of research involving logics dealing with "processes", "changes" or "interactions" in the fields of computer science and quantum physics.  Indeed, changes of states and interactions between a particular system and its context or environment, is of crucial importance in both mentioned fields.  As such we essentially present a program where the talks touch upon current research in : game semantics, dynamic logic,  epistemic logic, game theory and quantum logic.  Capturing the points of focus in several keywords, we surely have to mention "flow of information", "interaction", "(quantum) strategy", "(quantum) computation", "logic of knowledge".

We are proud to announce the participation of three visitors from Oxford University. Samson Abramsky recently succeeded Tony Hoare as holder of the prestigious Christopher Strachey Chair of Computing at Oxford University. He is a world authority in theoretical computer science and logic. For example, he was the main developer of game semantics, he is the general chair of the international symposium series "Logic in Computer Science" and is the series editor of the Handbook of Logic in Computer Science.  Alexandru Baltag who obtained his PhD from Indiana University under supervision of John Barwise, is a leading researcher in epistemic and game logic.  Bob Coecke obtained his PhD at the VUB in theoretical physics, recently joined Comlab and is specialized in the area of quantum structures.

Due to the interdisciplinary nature, the workshop is intended to be of interest at least to philosophical and mathematical logicians, computer scientists as well as theoretical physicists.
 

PROGRAM   -   ABSTRACTS   - LOCATION  -  ORGANIZATION

 

PROGRAM :

1st session takes place in ROOM: D.2.01 (Promotiezaal, building D) :
 
 

9.30  -   9.40 :    Opening

9.40  - 10.40 :    Samson Abramsky : "Games and Interaction in Logic and Computation"

10.40 - 11.00 :    coffee

11.00 - 12.00 :   Alexandru Baltag : "Probabilistic Epistemic Updates"

12.00 - 13.00 :   Jean Paul Van Bendegem : "Classical Arithmetic is Quite Unnatural"

13.00 - 14.30 :    lunch break

 
2nd session takes place in ROOM: M429 (Zaal De Brock, building M) :
 

14.30 - 15.30 :   Bob Coecke : "Probability = Logic + Partiality + Entropy"

15.30 - 16.10 :   Haroun Amira : "A brief introduction to quantum game theory"

16.10 - 16.30 :    coffee

16.30 - 17.10 :   Isar Stubbe : "Causal duality for processes as (co)tensors in a quantaloid enriched category"

17.10 - 17.50 :   Sonja Smets : "On Quantum Modality"

[back to top SLI-2003]

 

ABSTRACTS :

 
• "Games and Interaction in Logic and Computation"

 Samson Abramsky (COMLAB,Oxford)
 
We discuss models of logic and computation which take *interaction
between a system and its environment* as basic. This idea of interaction
can be formalized using notions from two-person games. An area of
research on `Game Semantics' for both programming languages and logical
systems has developed significantly over the past decade. It has led to
`full completeness' theorems for a number of logical systems, which
delineate the `space of proofs' for that system; and to full abstraction
results for a range of programming languages embodying many significant
computational effects.
Current developments include an algorithmic turn, where the semantics is
captured by a machine representation as a basis for program analysis and
model-checking; and the exploration of connections with issues of
physical computation, notably reversible and quantum computation.
The talk will give an informal introduction and overview to this body of
research.
 
• "Probabilistic Epistemic Updates"

Alexandru Baltag (COMLAB,Oxford)

I give a general probabilistic modeling for "epistemic programs". These are
programs for jointly updating every  agent's state of knowledge (or belief)
in a multi-agent system, in which the agent's uncertainty (about the current
state of the world or about the current interaction he/she is engaged in) is given
by a discrete probabilistic measure. Such programs are ways of computing the
effect of (ex)changes of information ("communication", "observation") between agents,
or between an agent and Nature. They can be intuitively understood as programs for
"interactive learning", or more generally for inducing belief changes in the participants.

I present my solution to the general problem of computing the information-updating
effects of a specific communication act: an operation of "Probabilistic-Epistemic Product
Update", which generalizes Bayesian belief revision to the case of many agents and of
uncertainty about announcements as well. (Both epistemic programs and the product
update can be understood in terms of functors and natural transformations on the category
of coalgebras for a specific functor.) I use these models to discuss various properties of
dialogues (publicity, normalcy, responsiveness, truthfulness, appropriateness of questions),
but also interesting types of dialogues which break these assumptions (rhetorical questions,
cheating and lying, impersonation, leading questions, Socratic dialogues).

I introduce a (qualitative, non-probabilistic) dynamic-epistemic logic and a Hoare logic
(both decidable), to reason about epistemic programs, and in particular to prove the
"partial correctness" of communication strategies with respect to given epistemic goals
(and given epistemic presuppositions).
 
 

• "Classical Arithmetic is Quite Unnatural"

Jean Paul Van Bendegem (CLWF,VUB)

Based on the discussion concerning supertasks - basically, these
are tasks that consist of an infinite number of steps to be executed in a
finite time and whereby the central question concerns the connection between
the properties of the end-state and the properties of the preceeding states
- I define a supertask such that (a) every step is a strictly finite
arithmetic possessing all "nice" properties one can imagine, and (b) the
end-state is classical arithmetic where all the "nice" properties have
disappeared. In that sense classical arithmetic is not informative about the
preceeding stages and can thus be called "unnatural". In short, this paper
is a subtle way to defend strict finitism.


 
• "Probability = Logic + Partiality + Entropy"

Bob Coecke (COMLAB,Oxford)

By introducing the notion of partiality in logic at an epistemic level
we can construct a space of probabilities. This gives chance a purely
qualitative status as compared to the quantative one in terms of
distributions -- which has dominated mathematics for a century.
In particular do we have:

Quantitative Probability = Qualitative probability + Shannon Entropy

where

Qualitative probability = Logic + Partiality on knowledge.

Actually, the above equations are understatements. We do not only
produce a space of probabilities, but one that goes equipped with
a partial order. We obtain a domain of probability measures!

This perspective is in perfect harmony with F.P. Ramsey's conception of
probability, Dana Scott's motivation underlying domain theory,
and the operational quantum logic schools. (the above indeed
holds as well for algebraic classical, intuitionistic as for
quantum logic, in that case resulting in quantum probability).
At a more advanced level, the above analysis reveals two distinct
epistemic ingredients in quantum theory.

Everything will be illustrated with beautiful pictures.
 
 

• "A brief introduction to quantum game theory"

Haroun Amira (MAPO/CLEA,VUB)

In theories such as quantum computation, quantum information and quantum cryptography
the physical representation of information as a quantum system is more successful than
the classical situation. In his 1999 seminal paper [1]Meyer proposes a 'quantization' of
game theory where the classical strategies space is replaced by a quantum version, consisting
of unitary operations on a quantum state. Implementing a quantum strategy can lead to new
and improved results. The foundations of modern game theory were largely developed by
Von Neumann [2] in order to study rational decision making in conflict situations.
Von Neumann also played a role of paramount importance for the foundations of Quantum
Theory [3].  In that regard quantum game theory can be seen as a (late) unification of the basic
ideas in both fields. In this presentation we propose an introduction to the subject and provide
an overview of the recent developments.

[1] D.A. Meyer, Quantum Strategies, Phys. Rev. Lett. 82, 1052-1055, 1999.
[2] J. Von Neumann and O. Morgenstern, Theory of Games and Economic Behavior, Princeton
        University Press, Princeton, 1944.
[3] G. Birkhoff and J. Von Neumann, The Logic of Quantum Mechanics, Annals of Mathematics 37,
        823-843, 1936.
 
 

•  "Causal duality for processes as (co)tensors in a quantaloid enriched category"

Isar Stubbe (AGEL,UCL)

The principle of "causal duality" is all about cause and consequence for processes.
In a setting where a system is described by an ordered set of properties
(usually a complete lattice in which infimum is conjunction), the principle of
causal duality for a given process that such a system undergoes, is mathematically
encoded as an adjunction of order preserving maps. Organizing all processes that a
given system may undergo in a quantale (or even quantaloid) allows to express
the principle of causal duality in a very precise way: as tensors and cotensors in a
quantaloid enriched category whose objects are the properties of the system.
 
 

• "On Quantum Modality"

Sonja Smets (CLWF,VUB)

We put forward a characterization of quantum logic that supports our pluralistic view on logic,
favouring a perspective that allows for the comparison of different logical systems.
First we focus on the characterization of minimal quantum logic (i.e. orthologic) in terms
of a modal logic or algebra with a unitary modal operator. That such an approach is possible,
is supported by the research presented in [1].  We characterize "modal quantum logic" as MQL
and analyse its place in the landscape of other non-classical logics. In particular, MQL is related
to the so-called "propositional flat logic" which computer scientists introduced in the context of
hardware verification and to the structure, which has been put forward in the research on
mathematical modalities, known as a "local Algebra".
Second, we focus on the origin of the orthomodular law and explain how this law exposes the
inherent dynamic nature of quantum logic (see [2]).  We ask which dynamic operators are needed to
extend MQL in order to express the orthomodular law itself.

[1] B. Coecke: "Quantum Logic in Intuitionistic Perspective", Studia Logica, 70, 411-440, 2002.
[2] B. Coecke and S. Smets: "The Sasaki Hook is not a [Static] Implicative Connective but Induces a
      Backward [in Time] Dynamic One that Assigns Causes", International Journal of
      Theoretical Physics, to appear (quant-ph/0111076)
 
 

 

LOCATION :

Vrije Universiteit Brussel
Pleinlaan 2
1050 Brussel

Take a look at the campus-map:
 

The first session takes place in building D:
Building D is located next to building C where the library is.
Take the main entrance, go upstairs, Room 2.01 (also called "promotiezaal") is on the first floor, first door at the left.
 

The second session takes place in building M:
Building M is the main administration building on the VUB-campus (the only one with a half-round shape), Room M429 (also called "zaal De Brock") is at the end of the hallway on the 4th floor.
 

Reaching the VUB by car: look at the following area-map
There is parking space under building B and C where you automatically end up by taking campus interance-number 12 from the pleinlaan.

Reaching the VUB by train: "Station Etterbeek" located on the Generaal Jaqueslaan, is just a 3 min. walk away

Reaching the VUB by metro:  Metro station Petillion and Metro station Delta are a 15 min. walk away from the VUB-campus, look at the subway-map.

Reaching the VUB by bus/tram:

Tram 3: (to Churchill) exit 2nd stop Lansiers
Tram 90: (to Rogier) exit 2nd stop Lansiers
Bus 34: via Waverse Steenweg
Bus 71: (to Delta) exit Fraiteur
Bus 95 and 96: exit Kroonlaan - Gen. Jacqueslaan

ORGANIZATION :

 

Centre for Logic and Philosophy of Science (CLWF), Free University of Brussels

Local Organization, Contact person: Sonja Smets

With financial support from the National Centre for Logical Investigation (CNRL/NCNL)