Analog models of computations \& Effective Church Turing Thesis: Efficient simulation of Turing machines by the General Purpose Analog Computer

Details Analog models of computations \& Effective Church Turing Thesis: Efficient simulation of Turing machines by the General Purpose Analog Computer Analog models of computations \& Effective Church Turing Thesis: Efficient simulation of Turing machines by the General Purpose Analog Computer

2012-03-21

arxiv.org/abs/1203.4667v1

Computer Science

Computational Complexity

Scientific paper

\emph{Are analog models of computations more powerful than classical models of computations?} From a series of recent papers, it is now clear that many realistic analog models of computations are provably equivalent to classical digital models of computations from a \emph{computability} point of view. Take, for example, the probably most realistic model of analog computation, the General Purpose Analog Computer (GPAC) model from Claude Shannon, a model for Differential Analyzers, which are analog machines used from 1930s to early 1960s to solve various problems. It is now known that functions computable by Turing machines are provably exactly those that are computable by GPAC. This paper is about next step: understanding if this equivalence also holds at the \emph{complexity} level. In this paper we show that the realistic models of analog computation -- namely the General Purpose Analog Computer (GPAC) -- can simulate Turing machines in a computationally efficient manner. More concretely we show 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 we recently proved that functions computable by a GPAC in a polynomial time with similar restrictions can always be simulated by a Turing machine, this opens the way to, first, a proof that realistic analog models of computations do satisfy the effective Church Turing thesis, and second to a well founded theory of complexity for analog models of computations.

Affiliated with

Also associated with

No associations

Rating

Analog models of computations \& Effective Church Turing Thesis: Efficient simulation of Turing machines by the General Purpose Analog Computer does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Analog models of computations \& Effective Church Turing Thesis: Efficient simulation of Turing machines by the General Purpose Analog Computer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analog models of computations \& Effective Church Turing Thesis: Efficient simulation of Turing machines by the General Purpose Analog Computer will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-488192