This paper studies the expressive and computational power of discrete Ordinary Differential Equations (ODEs), a.k.a. (Ordinary) Difference Equations. It presents a new framework using these equations as a central tool for computation and algorithm design. We present the general theory of discrete ODEs for computation theory, we illustrate this with various examples of algorithms, and we provide several implicit characterizations of complexity and computability classes. The proposed framework presents an original point of view on complexity and computation classes. It unifies several constructions that have been proposed for characterizing these classes including classical approaches in implicit complexity using restricted recursion schemes, as well as recent characterizations of computability and complexity by classes of continuous ordinary differential equations. It also helps understanding the relationships between analog computations and classical discrete models of computation theory. At a more technical point of view, this paper points out the fundamental role of linear (discrete) ODEs and classical ODE tools such as changes of variables to capture computability and complexity measures, or as a tool for programming many algorithms.
翻译:本文研究了离散普通差异方程式(ODEs)的表达力和计算力, a.k.a.(常规)差异方程式。它提出了一个新的框架,使用这些方程式作为计算和算法设计的核心工具。我们提出了用于计算理论的离散普通差异方程式的一般理论,我们用各种算法的例子来说明这一点,我们提供了复杂和可比较类别的若干隐含特征特征。拟议框架对复杂和计算类别提出了原始观点。它统一了为这些类别定性而提议的若干构思,包括使用限制递解办法进行隐含复杂性的典型方法,以及最近按连续普通差异方程式的类别对可比较性和复杂性所作的定性。它也有助于理解模拟计算与典型离散计算理论模型之间的关系。从更技术性的观点看,本文指出了线性(discrete) 代码和古典的内分解工具的基本作用,例如改变变量以捕捉可比较性和复杂度计量,或作为许多算算法的工具。