首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Polynomial differential equations compute all real computable functions on computable compact intervals
Authors:Olivier Bournez  Manuel L Campagnolo  Daniel S Graça  Emmanuel Hainry
Institution:1. Inria Lorraine, France;2. LORIA (UMR 7503 CNRS-INPL-INRIA-Nancy2-UHP), Campus Scientifique, BP 239, 54506 Vandœuvre-Lès-Nancy, France;3. DM/ISA, Technical University of Lisbon, 1349-017 Lisboa, Portugal;4. SQIG/IT, Technical University of Lisbon, 1049-001 Lisboa, Portugal;5. DM/FCT, Universidade do Algarve, C. Gambelas, 8005-139 Faro, Portugal;6. Institut National Polytechnique de Lorraine, France
Abstract: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.
Keywords:Analog computation  Computable analysis  General Purpose Analog Computer  Church&ndash  Turing thesis  Differential equations
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号