Preface

The goal of the workshop series is to bring together researchers working on the interaction between physics and the theory of computation. This intrinsically interdisciplinary domain of research strives to go beyond the traditional use of mathematics as a tool to model and understand the behaviour of physical systems. Instead, it looks to the theory of computation and information to provide new insights into physical systems and processes, and, in turn, how these insights can lead to new methods, models and notions of computation and new approaches to computational and mathematical problems. Topics falling into this category at the interface of physics and computation that are within the scope of the conference include, amongst many others: the axiomatisation of physics, hypercomputation, the role of information in physical systems, quantum information, randomness in physics, theories of measurement, and the philosophy of physics and computation.

Submissions to the workshop were each reviewed by three members of the programme committee, who selected 5 for presentation at the conference, of which 3 were full papers and 2 were extended abstracts. This volume contains revised versions of these original scientific contributions to the conference, and was published prior to the workshop taking place. Following the workshop, authors of selected submissions will be invited to submit extended and revised versions of their contributions to a special issue of the International Journal of Unconventional Computing (IJUC). In addition to the contributions appearing in this volume, two invited lectures were also given at the workshop by Gilles Dowek (INRIA, CNRS and ENS Cachan, France) and Ana Belén Sainz (University of Bristol, UK).

We would like to thank the programme committee for their work in reviewing and selecting the submissions to the workshop, as well as the organisers of UCNC 2016 for inviting us to hold this workshop in conjunction with the conference and for handling the local logistics.

July 2016,
Alastair Abbott and Dominic Horsman.

Programme Committee

• Alastair Abbott (co-chair, Institut Néel, Grenoble)
• Pablo Arrighi (Aix-Marseille University)
• Edwin Beggs (Swansea University)
• Cristian Calude (University of Auckland)
• Peter Dittrich (Friedrich-Schiller-University Jena)
• Jerzy Górecki (Institute of Physical Chemistry, Polish Academy of Sciences)
• Dominic Horsman (co-chair, Durham University)
• Viv Kendon (Durham University)
• Oron Shagrir (Hebrew University of Jerusalem)
• Mike Stannett (University of Sheffield)
• Susan Stepney (University of York)

Quantitative Informational Aspects in Discrete Physics

Discrete physics investigates the hypothesis that natural phenomena can be described using finite mathematics only. This hypothesis has a deep connection with another: that the density of information in nature is bounded. In this talk, I will discuss whether it is possible to measure the complexity of physical phenomena by the amount of information their description requires, focusing on three examples: free fall according to Newtonian physics, to Special Relativity, and to General Relativity.

Postquantum Steering

The discovery of postquantum nonlocality, i.e. the existence of nonlocal correlations stronger than any quantum correlations but nevertheless consistent with the no-signalling principle, has deepened our understanding of the foundations quantum theory. In this work, we investigate whether the phenomenon of Einstein-Podolsky-Rosen steering, a different form of quantum nonlocality, can also be generalised beyond quantum theory. While postquantum steering does not exist in the bipartite case, we prove its existence in the case of three observers. Importantly, we show that postquantum steering is a genuinely new phenomenon, fundamentally different from postquantum nonlocality. Our results provide new insight into the nonlocal correlations of multipartite quantum systems.