Turing machines can be efficiently simulated by the general purpose analog computer

DOI10.1007/978-3-642-38236-9_16zbMATH Open1382.68067arXiv1203.4667OpenAlexW3099579506MaRDI QIDQ4922124FDOQ4922124

Authors: Amaury Pouly, Olivier Bournez, Daniel Graça 

Publication date: 28 May 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: The Church-Turing thesis states that any sufficiently powerful computational model which captures the notion of algorithm is computationally equivalent to the Turing machine. This equivalence usually holds both at a computability level and at a computational complexity level modulo polynomial reductions. However, the situation is less clear in what concerns models of computation using real numbers, and no analog of the Church-Turing thesis exists for this case. Recently it was shown that some models of computation with real numbers were equivalent from a computability perspective. In particular it was shown that Shannon's General Purpose Analog Computer (GPAC) is equivalent to Computable Analysis. However, little is known about what happens at a computational complexity level. In this paper we shed some light on the connections between this two models, from a computational complexity level, by showing that, modulo polynomial reductions, computations of Turing machines can be simulated by GPACs, without the need of using more (space) resources than those used in the original Turing computation, as long as we are talking about bounded computations. In other words, computations done by the GPAC are as space-efficient as computations done in the context of Computable Analysis.

Full work available at URL: https://arxiv.org/abs/1203.4667

Recommendations

• Theory and Applications of Models of Computation
• Analog computers and recursive functions over the reals.
• Polynomial time corresponds to solutions of polynomial ordinary differential equations of polynomial length: the general purpose analog computer and computable analysis are two efficiently equivalent models of computations
• Some recent developments on Shannon's General Purpose Analog Computer
• scientific article; zbMATH DE number 5064401

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78) Turing machines and related notions (03D10)

Cites Work

• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Computability with polynomial differential equations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the complexity of solving initial value problems
• Title not available (Why is that?)
• Analog computers and recursive functions over the reals.
• Polynomial differential equations compute all real computable functions on computable compact intervals
• Title not available (Why is that?)
• Building Infinite Machines
• Title not available (Why is that?)
• Mathematical Theory of the Differential Analyzer
• Classical recursion theory. The theory of functions and sets of natural numbers
• A survey on continuous time computations
• Achilles and the tortoise climbing up the arithmetical hierarchy
• The stability of saturated linear dynamical systems is undecidable
• A theory of complexity for continuous time systems

Cited In (3)

• Simulation of Turing machine with uEAC-computable functions
• Computable analysis with applications to dynamic systems
• New Computational Paradigms

This page was built for publication: Turing machines can be efficiently simulated by the general purpose analog computer

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4922124)