This special issue of Mathematical Structures in Computer Science contains several contributions to the Workshop

3 corps, classique-quantique, discret-continu.

The Workshop was held at the Ecole Normale Supérieure, Paris on 28–29 September 2004 in the framework of the Collectif Histoire Philosophie Sciences. The Workshop was organised by Giuseppe Longo and Thierry Paul with the aim of bringing together mathematicians, physicists, computer scientists and philosophers.

We present a discussion concerning the opposition between discreteness and the continuum in quantum mechanics. In particular, it is shown that this duality was not restricted to the early days of the theory, but remains current, and features different aspects of discretisation. In particular, the discreteness of quantum mechanics is key for quantum information and quantum computation. We propose a conclusion involving a concept of completeness linking discreteness and the continuum.

This paper presents a sample of the deep and multiple interplay between discrete and continuous behaviours and the corresponding modellings in physics. The aim of this overview is to show that discrete and continuous features coexist in any natural phenomenon, depending on the scales of observation. Accordingly, different models, either discrete or continuous in time, space, phase space or conjugate space can be considered. Some caveats about their limits of validity and their interrelationships (discretisation and continuous limits) are pointed out. Difficulties and gaps arising from the singular nature of continuous limits and from the information loss accompanying discretisation are discussed.

The three body Coulomb problem is one of the oldest unsolved problems of theoretical physics, and holds a variety of puzzling problems, on both the classical and quantum levels. It is of paradigmatic importance since it bears dynamical and spectral features that establish a link between single and many-particle dynamics, with the absolute minimum of ingredients. When additionally exposed to a time-periodic external perturbation, the effective dimension of the classical phase space as well as of Hilbert space increases dramatically. This gives rise to new phenomena, which stimulate research in such remote areas as mathematical physics, semiclassics and intense-field laser–matter interactions. In the present review, we illustrate how these different areas are interconnected by three interacting particles.

Computers are used extensively to simulate continuous dynamical systems. However, different conceptual and mathematical structures underlie discrete machines and continuous dynamics, so the question arises as to the ability of the computer to simulate or, more generally, to check the properties of a continuous system.

We discuss and compare two notions of stability for a continuous dynamical system, viz. shadowing and robustness, and relate them to both the practical and theoretical computability of the system. We first discuss what we can learn from the stability of a system, using a finite-precision machine. We then show, following the work in Collins (2005), that shadowing fails but robustness succeeds in ensuring the checkability of a reachability property.

The relationship between continuous-time dynamics and the corresponding discrete schemes, and its generally limited validity, is an important and widely acknowledged field within numerical analysis. In this paper, we propose another, more physical, viewpoint on this topic in order to understand the possible failure of discretisation procedures and the way to fix it. Three basic examples, the logistic equation, the Lotka–Volterra predator–prey model and Newton's law for planetary motion, are worked out. They illustrate the deep difference between continuous-time evolutions and discrete-time mappings, hence shedding some light on the more general duality between continuous descriptions of natural phenomena and discrete numerical computations.

Perturbation theory has always been an important component of the natural sciences. From celestial mechanics to the quantum theory of fields, it has always played a central role, which this little note sets out to analyse briefly. We will show, in particular, how its epistemological position has changed from being just a ‘tool’ to being the basis of definition for objects in quantum field theory.

This paper provides a conceptual analysis of the role of the mathematical continuum versus the discrete in the understanding of randomness as a notion with a physical meaning or origin. The presentation is ‘informal’ as we will not write formulas; however, we will refer to non-obvious technical results from various scientific domains, and we will also propose a conceptual framework for understanding randomness (and predictability), which we believe is, essentially, original. As a matter of fact, unpredictability and randomness may be conveniently identified in various physico-mathematical contexts. This will allow us to explore these concepts in continuous versus discrete frameworks, with particular emphasis on the relationships and differences between classical approaches and quantum theories in Physics.

Before one can attach a meaning to a sentence, one must distinguish different ways of parsing it. When analysing a language with pregroup grammars, we are thus led to replace the free pregroup by a free compact strict monoidal category. Since a strict monoidal category is a 2-category with one 0-cell, we investigate the free compact 2-category generated by a given category, and describe its 2-cells as labelled transition systems. In particular, we obtain a decision procedure for the equality of 2-cells in the free compact 2-category.

We study full completeness and syntactical separability of MLL proof nets with the mix rule. The general method we use consists of first addressing these two questions in the less restrictive framework of proof structures, and then adapting the results to proof nets.

At the level of proof structures, we find a semantical characterisation of their interpretations in relational semantics, and define an observational equivalence that is proved to be the equivalence induced by cut elimination. Hence, we obtain a semantical characterisation (in coherent spaces) and an observational equivalence for the proof nets with the mix rule.