Room P3.10, Mathematics Building

Diogo Poças, Instituto Superior Técnico

Complexity with costing and stochastic oracles

We study the idea of coupling a Turing machine with an analog device as oracle, thus defining a new class of machines called the analog-digital Turing machines. An example of analog device is the Scatter Machine (SME, proposed by Beggs and Tucker in 2007, then coupled with a Turing machine in a model proposed by Beggs, Costa, Loff and Tucker later on in 2008). Following studies of different physical experiments of measurement led to the conclusion that the analog devices can be cathegorized in one of three different types: two-sided, threshold and vanishing, corresponding to three different oracles to Turing machines. (The SME is an example of two-sided type.) We analyze the computational power of such hybrid systems subject to polynomial resources. We shall present techniques to prove lower and upper bounds, considering different degrees of precision in the measurement procedure. Joint work with José Félix Costa