AN ANALOGUE-DIGITAL CHURCH-TURING THESIS

作者：Beggs Edwin^*; Costa Jose Felix; Pocas Diogo; Tucker John V

来源：International Journal of Foundations of Computer Science, 2014, 25(4): 373-389.

DOI：10.1142/S0129054114400012

• Analogue computation
• analogue-digital systems
• hybrid systems
• non-uniform complexity
• 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 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.

• 出版日期2014-6