No Cover Image

Journal article 578 views

An analogue-digital Church-Turing Thesis / Edwin J Beggs; Felix Costa; Diogo Pocas; John Tucker

International Journal of Foundations of Computer Science, Volume: 25, Issue: 4, Pages: 373 - 389

Swansea University Author: Tucker, John

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

DOI (Published version): 10.1142/S0129054114400012

Abstract

We argue that dynamical systems involving discrete and continuous data can be modelledby Turing machines with oracles that are physical processes. Using the theory introducedin Beggs et al. [2,3], we consider the scope and limits of polynomial time computationsby such systems. We propose a general p...

Full description

Published in: International Journal of Foundations of Computer Science
Published: 2014
Online Access: http://www.worldscientific.com/doi/abs/10.1142/S0129054114400012
URI: https://cronfa.swan.ac.uk/Record/cronfa21457
Tags: Add Tag
No Tags, Be the first to tag this record!
Abstract: We argue that dynamical systems involving discrete and continuous data can be modelledby Turing machines with oracles that are physical processes. Using the theory introducedin Beggs et al. [2,3], we consider the scope and limits of polynomial time computationsby such systems. We propose a general polynomial time Church-Turing Thesis for feasi-ble computations by analogue-digital systems, having the non-uniform complexity classBPP//log⋆ as theoretical upper bound. We show why BPP//log⋆ and we examinewhether other sources of hypercomputation can be found in analogue-digital systemsbesides the oracle itself. We prove that the higher polytime limit P/poly can be attainedvia non-computable analogue-digital interface protocols.
Keywords: Analogue computation; analogue-digital systems; hybrid systems; non- uniform complexity; Church-Turing Thesis.
College: College of Science
Issue: 4
Start Page: 373
End Page: 389