文章基本信息

标题：Computability, Complexity and Programming with Ordinary Differential Equations (Invited Talk)
本地全文：下载
作者：Olivier Bournez
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：154
页码：3:1-3:13
DOI：10.4230/LIPIcs.STACS.2020.3
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Ordinary Differential Equations (ODEs) appear to be a universally adopted and very natural way for expressing properties for continuous time dynamical systems. They are intensively used, in particular in applied sciences. There exists an abundant literature about the hardness of solving ODEs with numerical methods. We adopt a dual view: we consider ODEs as a way to program or to describe our mathematical/computer science world. We survey several results considering ODEs under this computational perspective, with a computability and complexity theory point of view. In particular, we provide various reasons why polynomial ODEs should be considered as the continuous time analog of Turing machines for continuous-time computations, or should be used as a way to talk about mathematical logic. This has already applications in various fields: determining whether analog models of computation can compute faster than classical digital models of computation; solving complexity issues for computations with biochemical reactions in bioinformatics; machine independent characterizations of various computability and complexity classes such as PTIME or NPTIME, or proof of the existence of a universal polynomial ordinary differential equation whose solutions can approximate any continuous function if provided with a suitable well-chosen initial condition.
关键词：Ordinary differential equations; Models of computation; Analog Computations; discrete ordinary differential equations; Implicit complexity; recursion scheme