No Cover Image

Book Chapter 456 views

An Analogue-Digital Model of Computation: Turing Machines with Physical Oracles / Tânia Ambaram; Edwin Beggs; José Félix Costa; Diogo Poças; John V. Tucker

Advances in Unconventional Computing, Volume: 22, Pages: 73 - 115

Swansea University Author: Tucker, John

Full text not available from this repository: check for access using links below.

Abstract

This chapter introduces and surveys the basic theory of 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 Turin...

Full description

Published in: Advances in Unconventional Computing
ISBN: 978-3-319-33923-8 978-3-319-33924-5
ISSN: 2194-7287 2194-7295
Published: Springer 2016
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa29301
Tags: Add Tag
No Tags, Be the first to tag this record!
Abstract: This chapter introduces and surveys the basic theory of 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.
Keywords: analogue-digital, physical oracle, Turing machine, polynomial time, non-uniform complexity class, meaurement theory
College: College of Science
Start Page: 73
End Page: 115