Passer à la navigation principale Passer à la recherche Passer au contenu principal

Polynomial differential equations compute all real computable functions on computable compact intervals

  • LORIA and INRIA Lorraine
  • LORIA Laboratoire Lorrain de Recherche en Informatique et ses Applications
  • Instituto Superior de Agronomia, Universidade Tecnica de Lisboa
  • SQIG, Instituto de Telecomunicações
  • Universidade do Algarve
  • Nancy Université

Résultats de recherche: Contribution à un journalArticleRevue par des pairs

58 Citations (Scopus)

Résumé

In the last decade, there have been several attempts to understand the relations between the many models of analog computation. Unfortunately, most models are not equivalent. Euler's Gamma function, which is computable according to computable analysis, but that cannot be generated by Shannon's General Purpose Analog Computer (GPAC), has often been used to argue that the GPAC is less powerful than digital computation. However, when computability with GPACs is not restricted to real-time generation of functions, it has been shown recently that Gamma becomes computable by a GPAC. Here we extend this result by showing that, in an appropriate framework, the GPAC and computable analysis are actually equivalent from the computability point of view, at least in compact intervals. Since GPACs are equivalent to systems of polynomial differential equations then we show that all real computable functions over compact intervals can be defined by such models.

langue originaleAnglais
Pages (de - à)317-335
Nombre de pages19
journalJournal of Complexity
Volume23
Numéro de publication3
Les DOIs
étatPublié - 1 janv. 2007
Modification externeOui

Empreinte digitale

Examiner les sujets de recherche de « Polynomial differential equations compute all real computable functions on computable compact intervals ». Ensemble, ils forment une empreinte digitale unique.

Contient cette citation