Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T17:56:53.561Z Has data issue: false hasContentIssue false

THREE FORMS OF PHYSICAL MEASUREMENT AND THEIR COMPUTABILITY

Published online by Cambridge University Press:  09 September 2014

EDWIN BEGGS*
Affiliation:
Department of Mathematics, Swansea University
JOSÉ FÉLIX COSTA*
Affiliation:
Instituto Superior Técnico and Centro de Matemática e Aplicações Fundamentais, Universidade de Lisboa
JOHN V TUCKER*
Affiliation:
Department of Computer Science, Swansea University
*
*DEPARTMENT OF MATHEMATICS, COLLEGE OF SCIENCE SWANSEA UNIVERSITY, SINGLETON PARK, SWANSEA, SA2 8PP WALES, U.K. E-mail: e.j.beggs@swansea.ac.uk
†INSTITUTO SUPERIOR TÉCNICO UNIVERSIDADE DE LISBOA PORTUGAL and CENTRO DE MATEMÁTICA E APLICAÇÕES FUNDAMENTAIS UNIVERSIDADE DE LISBOA PORTUGAL3 E-mail: fgc@math.tecnico.ulisboa.pt
‡DEPARTMENT OF COMPUTER SCIENCE, COLLEGE OF SCIENCE SWANSEA UNIVERSITY, SINGLETON PARK, SWANSEA, SA2 8PP WALES, U.K. E-mail: j.v.tucker@swansea.ac.uk
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We have begun a theory of measurement in which an experimenter and his or her experimental procedure are modeled by algorithms that interact with physical equipment through a simple abstract interface. The theory is based upon using models of physical equipment as oracles to Turing machines. This allows us to investigate the computability and computational complexity of measurement processes. We examine eight different experiments that make measurements and, by introducing the idea of an observable indicator, we identify three distinct forms of measurement process and three types of measurement algorithm. We give axiomatic specifications of three forms of interfaces that enable the three types of experiment to be used as oracles to Turing machines, and lemmas that help certify an experiment satisfies the axiomatic specifications. For experiments that satisfy our axiomatic specifications, we give lower bounds on the computational power of Turing machines in polynomial time using nonuniform complexity classes. These lower bounds break the barrier defined by the Church-Turing Thesis.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2014