Theory of Two-sided Experiments A new insight on measurable numbers (Extended Abstract)
Tânia Filipa, Nascimento Ambaram, Universidde de Lisboa · 2014
In this work we proceed with the investigation of the power of an abstract model of computation that considers Turing machines coupled with physical oracles. A physical oracle is an experiment controlled by the Turing machine with the purpose of measuring some quantity or parameter, possibly suitable to boost the power of the Turing machine. We consider one of the three known types of measurement experiments — the two-sided case. Researches on the computational power under bounded resources of the two other types — threshold and vanishing — have been considered and are settle by other authors up to some hard open problems. Herein we address the unfinished case of the two-sided oracle, establishing the corresponding upper bounds. We consider three types of communication between the Turing machine and the oracle (infinite precision, unbounded precision and fixed precision), that simulate the error propagation common to physical experiments. These three types of precision introduce variants of the two-sided oracle machines. We fix the upper bounds for the three cases. In the context of the infinite precision protocol of two-sided machines, we then address the question of knowing if a number, a physical parameter, is measurable or not. This problem was first put out by the physicists Geroch and Hartle without a formal framework to reason upon definition. We characterize the measurable and the non measurable numbers and we analyze some of their properties.