[FOM] What can physical systems compute?

[Tucker J.V.]

Colleagues,

1. In a recent response to Dan Schwarts' question about invariance and complexity (March 20) I posted some observations about equivalence theorems for different computational models. I pointed out that the invariance we find in classical computability theory (= computability on natural numbers or strings) is special. For example, in the general case of universal algebras, or in the specific case of the reals, there are significant distinctions between models that we wish to preserve and use (rather than neglect). Invariance questions can be a great source of mathematical guidance in computability theory.


2. Some FOMers have asked me further questions, especially about my final point, which was:

"5. If you look at computational models equipped with simple physical systems as oracles you get a variety of classes that break the Church-Turing barrier, e.g. Turing machines even under the restriction of polynomial time can give you P/poly or P/log*."

This posting gives some background and references.


3. Felix Costa, Edwin Beggs and I have been exploring the question,

What can physical systems compute?,

by using physical systems as oracles to algorithms. Specifically, we have taken physical models of experiments that measure quantities and used them as oracles to polynomial-time Turing machines.

Of immediate interest is the way oracles are queried. A rational is presented as initial data to the equipment and a physical theory determines what happens next.  The experiment requires us to look at three cases: the initial data is given exactly, or with arbitrary accuracy, or with a fixed finite error. There is delay for the answer to the query.

Our methodology has been

(i)  to study extensively different particular experiments acting as oracles (we have considered 9 with varying levels of detail).

(ii) to seek axiomatisations of the oracle protocols.


4. The research programme started with a specific experiment to measure the vertex of a wedge. We developed the methodology and exactly characterised the computational classes in:

E J Beggs, J F Costa, B Loff and J V Tucker, Computational complexity with experiments as oracles, Proceedings Royal Society Series A, 464 (2008) 2777-2801.

E J Beggs, J F Costa, B Loff and J V Tucker, Computational complexity with experiments as oracles II: Upper bounds, Proceedings Royal Society Series A, 465 (2009) 1453-1465.

For queries that were exact and arbitrary accurate we first found the non-uniform complexity class P/poly.


5. Later, when we made a different physical model of the wedge we were able to characterise the computational classes as P/log* in:


E J Beggs, J F Costa and J V Tucker, The impact of models of a physical oracle on computational power, Mathematical Structures in Computer Science, Mathematical Structures in Computer Science, 22 (2012) 853-879.  doi:10.1017/S0960129511000557


6. Actually, many of the other experiments we studied led to P/log* and recently we have axiomatised the class of experiments in the paper:

E J Beggs, J F Costa and J V Tucker, Axiomatising physical experiments as oracles to algorithms, Philosophical Transactions Royal Society, A 370 (2012) 3359–3384.  doi:10.1098/rsta.2011.0427


7. Other non-uniform complexity classes arise (especially probabilistic classes) and we are in search of new axiomatisations to map the computational powers and relate them to physical attributes. The argument as to which of the 4 or 5 classes are important will ultimately be a physical argument.





John




-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20130405/b76f8113/attachment.html>