Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Advances in Unconventional ComputingAn Analogue-Digital Model of Computation: Turing Machines with Physical Oracles

Advances in Unconventional Computing: An Analogue-Digital Model of Computation: Turing Machines... [We introduce an abstract analogue-digital model of computation that couples Turing machines to oracles that are physical processes. Since any oracle has the potential to boost the computational power of a Turing machine, the effect on the power of the Turing machine of adding a physical process raises interesting questions. Do physical processes add significantly to the power of Turing machines; can they break the Turing Barrier? Does the power of the Turing machine vary with different physical processes? Specifically, here, we take a physical oracle to be a physical experiment, controlled by the Turing machine, that measures some physical quantity. There are three protocols of communication between the Turing machine and the oracle that simulate the types of error propagation common to analogue-digital devices, namely: infinite precision, unbounded precision, and fixed precision. These three types of precision introduce three variants of the physical oracle model. On fixing one archetypal experiment, we show how to classify the computational power of the three models by establishing the lower and upper bounds. Using new techniques and ideas about timing, we give a complete classification.] http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

Advances in Unconventional ComputingAn Analogue-Digital Model of Computation: Turing Machines with Physical Oracles

Download PDF
42 pages

Loading next page...
 
/lp/springer-journals/advances-in-unconventional-computing-an-analogue-digital-model-of-ZMnna00yM9
Publisher
Springer International Publishing
Copyright
© Springer International Publishing Switzerland 2017
ISBN
978-3-319-33923-8
Pages
73 –115
DOI
10.1007/978-3-319-33924-5_4
Publisher site
See Chapter on Publisher Site

Abstract

[We introduce an abstract analogue-digital model of computation that couples Turing machines to oracles that are physical processes. Since any oracle has the potential to boost the computational power of a Turing machine, the effect on the power of the Turing machine of adding a physical process raises interesting questions. Do physical processes add significantly to the power of Turing machines; can they break the Turing Barrier? Does the power of the Turing machine vary with different physical processes? Specifically, here, we take a physical oracle to be a physical experiment, controlled by the Turing machine, that measures some physical quantity. There are three protocols of communication between the Turing machine and the oracle that simulate the types of error propagation common to analogue-digital devices, namely: infinite precision, unbounded precision, and fixed precision. These three types of precision introduce three variants of the physical oracle model. On fixing one archetypal experiment, we show how to classify the computational power of the three models by establishing the lower and upper bounds. Using new techniques and ideas about timing, we give a complete classification.]

Published: Jul 19, 2016

Keywords: Turing Machine; Physical Time; Explicit Time; Boundary Number; Vertex Position

There are no references for this article.