AN ANALOGUE-DIGITAL CHURCH-TURING THESIS

We argue that dynamical systems involving discrete and continuous data can be modelled by Turing machines with oracles that are physical processes. Using the theory introduced in Beggs et al. [2,3], we consider the scope and limits of polynomial time computations by such systems. We propose a genera...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2014-06, Vol.25 (4), p.373-389
Main Authors: BEGGS, EDWIN, COSTA, JOSÉ FÉLIX, POÇAS, DIOGO, TUCKER, JOHN V.
Format: Article
Language:English
Subjects:
Analog computers
Computation
Computer simulation
Digital systems
Dynamical systems
Foundations
Neural networks
Polynomials
Protocol (computers)
Turing machines
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We argue that dynamical systems involving discrete and continuous data can be modelled by Turing machines with oracles that are physical processes. Using the theory introduced in Beggs et al. [2,3], we consider the scope and limits of polynomial time computations by such systems. We propose a general polynomial time Church-Turing Thesis for feasible computations by analogue-digital systems, having the non-uniform complexity class BPP//log* as theoretical upper bound. We show why BPP//log* should be replace P/poly, which was proposed by Siegelmann for neural nets [23,24]. Then we examine whether other sources of hypercomputation can be found in analogue-digital systems besides the oracle itself. We prove that the higher polytime limit P/poly can be attained via non-computable analogue-digital interface protocols.
ISSN:0129-0541
1793-6373
DOI:10.1142/S0129054114400012