English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The Church-Turing thesis states that any sufficiently powerful computationalmodel which captures the notion of algorithm is computationally equivalent tothe Turing machine. This equivalence usually holds both at a computabilitylevel and at a computational complexity level modulo polynomial reductions.However, the situation is less clear in what concerns models of computationusing real numbers, and no analog of the Church-Turing thesis exists for thiscase. Recently it was shown that some models of computation with real numberswere equivalent from a computability perspective. In particular it was shownthat Shannon's General Purpose Analog Computer (GPAC) is equivalent toComputable Analysis. However, little is known about what happens at acomputational complexity level. In this paper we shed some light on theconnections between this two models, from a computational complexity level, byshowing that, modulo polynomial reductions, computations of Turing machines canbe simulated by GPACs, without the need of using more (space) resources thanthose used in the original Turing computation, as long as we are talking aboutbounded computations. In other words, computations done by the GPAC are asspace-efficient as computations done in the context of Computable Analysis.

Turing machines can be efficiently simulated by the General Purpose Analog Computer