Computational aspects of physical experiments#

Tucker V. John#

Abstract

I will introduce a theory for combining algorithms with physical experiments devised by F. Costa (Lisbon), E. Beggs (Swansea) and myself. The theory has two aims: to classify the computational power of physical technologies and to explain how algorithms control physical equipment in performing measurements. I will explain current results, based upon non-uniform complexity classes, that prove that a wide range of physical systems boost the power of algorithms beyond the Turing barrier. I will also explain how modeling a technician following an experimental procedure leads to uncertainty in classical measurements.