Scope
This workshop aims to address the question: what physical resources are
consumed during computation?
The standard, Turing-machine case is well studied, and the relevant complexity
resources—notably run-time and memory space—are accordingly routinely
considered. But what of the non-standard case? And what of trade-offs between
component models in hybrid computational models?
Some relevant questions are
- What resources are relevant to computation via quantum, analogue,
optical, ... computer?
- What can be said of complexity, entanglement, etc. in biological systems and in nature?
- Can we meaningfully view energy, precision of measurement, transfer of
information, ... as resources?
- What is the trade-off between classical and quantum resources in a
measurement-based quantum computer?
- Is there a trade-off between computational and spatio-temporally distributed
resources?
- A more fundamental trade-off question: is there an underlying 'overall'
resource, of which individual resources are facets?
- What complexity results follow from consideration of hypothetical resources
such as non-local boxes?
- What general framework of complexity is there that accommodates all
computational models?
- Can computational limitations be expressed as a physical law?
The workshop aims to bring together people interested in such questions, and
shed light on these issues.
The workshop is funded by EPSRC grant, Complexity and
Decidability in Unconventional Computational Models.
