# A characterization of polynomial time computable functions from the integers to the reals using discrete ordinary differential equations

Manon Blanc, Olivier Bournez

► To cite this version:

Manon Blanc, Olivier Bournez. A characterization of polynomial time computable functions from the integers to the reals using discrete ordinary differential equations. 9th International Conference MCU (Machines, Computations, and Universality), Aug 2022, Debrecen, Hungary. pp.58-74, 10.1007/978-3-031-13502-6_4. hal-04259376

HAL Id: hal-04259376

https://hal.science/hal-04259376v1

Submitted on 26 Oct 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# A characterization of polynomial time
computable functions from the integers to the
reals using discrete ordinary differential
equations*

Manon Blanc<fnref n="1" />,<fnref n="2" /> and Olivier Bournez<fnref n="1" />

**Abstract.** The class of functions from the integers to the integers computable in polynomial time has been recently characterized using discrete ordinary differential equations (ODE), also known as finite differences. Doing so, 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 was pointed out. In this article, we extend the approach to a characterization of functions from the integers to the reals computable in polynomial time in the sense of computable analysis. In particular, we provide a characterization of such functions in terms of the smallest class of functions that contains some basic functions, and that is closed by composition, linear length ODEs, and a natural effective limit schema.

# 1 Introduction

Ordinary differential equations are a natural tool for modeling many phenomena in applied sciences, with a very abundant literature (see e.g. [1–3]) and are rather well understood under many aspects. In a series of recent articles, they have been shown to also correspond to some natural computational model, with a nice computability and complexity theory: See [4] for a survey.

In a recent article [5, 6], their discrete counterpart, which are called discrete ODEs, also known as difference equations have been investigated. The basic principle is, for a function $f(x)$ to consider its discrete derivative defined as $\Delta f(x) = f(x + 1) - f(x)$. We will intentionally also write $f'(x)$ for $\Delta f(x)$ to help to understand statements with respect to their classical continuous counterparts. This associated derivative notion, called *finite differences*, has been widely studied in numerical optimization for function approximation [7] and in *discrete calculus* [8–11] for combinatorial analysis. While the underlying computational content of finite differences theory is clear and has been pointed out

<footnote n="1">¹ Institut Polytechnique de Paris, Ecole Polytechnique, Laboratoire d'Informatique de l'X (LIX), 91128 Palaiseau Cedex, France
{manon.blanc,olivier.bournez}@lix.polytechnique.fr</footnote>

<footnote n="2">² ENS Paris-Saclay, Gif-Sur-Yvette, France</footnote>

<footnote>* This work has been partially supported by ANR Project *∂IFFERENCE*.</footnote>
many times, no fundamental connections with algorithms and complexity had been formally established before [5, 6], where it was proved that many complexity and computability classes from computation theory can actually be characterized algebraically using discrete ODEs. Even if such results were initially motivated by helping to understand the relationships between analog computations and classical discrete models of computation theory, the relation between the two is currently unclear.

In the context of algebraic classes of functions, a classical notation is the following: Call *operation* a scheme of definition that takes finitely many functions, and returns some new function defined from them. Then,

$$[f_1, f_2, \dots, f_k; op_1, op_2, \dots, op_\ell],$$

denotes the smallest set of functions containing functions $f_1, f_2, \dots, f_k$ that is closed under operations $op_1, op_2, \dots, op_\ell$. Call *discrete function* a function of type $f: S_1 \times \dots \times S_d \to S'_1 \times \dots S'_d$, where each $S_i, S'_i$ is either $\mathbb{N}$ or $\mathbb{Z}$. Write **FPTIME** for the class of functions computable in polynomial time. A main result of [5, 6] is the following (LDL stands for linear derivation on length):

**Theorem 1 ([5]).** For discrete functions, we have

$$\mathbf{LDL} = \mathbf{FPTIME}$$

where $\mathbf{LDL} = [\mathbf{0}, \mathbf{1}, \pi_i^k, \ell(x), +, -, \times, \operatorname{sg}(x); \text{composition, linear length ODE}]$.

That is to say, $\mathbf{LDL}$ (and hence **FPTIME** for discrete functions) is the smallest subset of functions, that contains

- the constant functions $\mathbf{0}$ and $\mathbf{1}$,

- the projections $\pi_i^k : \mathbb{R}^k \to \mathbb{R}$ given by $\pi_i^k(x_1, \dots, x_k) = x_i$, for various integers $i$ and $k$,

- the length function $\ell(x)$, which maps an integer to the length of its binary representation,

- the addition function $x+y$,

- the subtraction function $x-y$,

- the multiplication function $x \times y$ (that we will also often denote $x \cdot y$),

- the sign function $\operatorname{sg}(x) : \mathbb{Z} \to \mathbb{Z}$ that takes value 1 for $x > 0$ and 0 in the other case,

and closed under composition (when defined) and linear length-ODE scheme: The linear length-ODE scheme basically (a formal definition is provided in Definition 4) corresponds in defining functions from linear ODEs with respect to derivation with respect to the length of the argument, that is to say, of the form

$$\frac{\partial \mathbf{f}(x, \mathbf{y})}{\partial \ell} = \mathbf{A}[\mathbf{f}(x, \mathbf{y}), x, \mathbf{y}] \cdot \mathbf{f}(x, \mathbf{y}) + \mathbf{B}[\mathbf{f}(x, \mathbf{y}), x, \mathbf{y}],$$

In all what follows, when we write some variable using some boldface letter, like $\mathbf{y}$, this means that it can be a vector of variable. A usual typography, like for
the $x$ above, means it is a single variable. In the above description, we use the notation $\frac{\partial f(x, y)}{\partial l}$, which corresponds in derivation of $f$ along the length function: Given some function $\mathcal{L}: \mathbb{N}^{p+1} \to \mathbb{Z}$, and in particular for the case of where $\mathcal{L}(x, y) = l(x)$,

$$ \frac{\partial f(x, y)}{\partial \mathcal{L}} = \frac{\partial f(x, y)}{\partial \mathcal{L}(x, y)} = \mathbf{h}(f(x, y), x, y), \qquad (1) $$

is a formal synonym for

$$ \mathbf{f}(x+1, \mathbf{y}) = \mathbf{f}(x, \mathbf{y}) + (\mathcal{L}(x+1, \mathbf{y}) - \mathcal{L}(x, \mathbf{y})) \cdot \mathbf{h}(f(x, \mathbf{y}), x, \mathbf{y}). $$

*Remark 1.* This concepts, introduced in [5, 6], is motivated by the fact that the latter expression is similar to classical formula for classical continuous ODEs:

$$ \frac{\delta f(x, \mathbf{y})}{\delta x} = \frac{\delta \mathcal{L}(x, \mathbf{y})}{\delta x} \cdot \frac{\delta f(x, \mathbf{y})}{\delta \mathcal{L}(x, \mathbf{y})}, $$

and hence this is similar in spirit to a change of variable. Consequently, a linear length-ODE is basically a linear ODE over variable $t$, once the change of variable $t = l(x)$ is done.

In particular, writing as usual $B^A$ for functions from $A$ to $B$, we have:

**Theorem 2 ([5]).** $\mathbb{L}\mathbb{D}\mathbb{L} \cap \mathbb{N}^\mathbb{N} = \mathbf{FPTIME} \cap \mathbb{N}^\mathbb{N}$.

This provides a characterization of **FPTIME** for discrete functions that does not require to specify an explicit bound in the recursion, in contrast to Cobham's work [12], nor to assign a specific role or type to variables, in contrast to safe recursion or ramification [13, 14]. The characterization happens to be very simple using only natural notions from the world of ODE.

Our purpose in this article is to extend this to more general classes of functions. In particular, this makes sense to try to characterize polynomial time functions from the reals to the reals. We consider here computability and complexity over the reals in the most classical sense, that is to say, computable analysis (see e.g. [15]). Indeed, considering that $\mathbb{N} \subset \mathbb{R}$, most of the basic functions and operations in the above characterization (for example, $+$, $-$, ...) have a clear meaning over the reals. One clear difficulty is that discrete ODEs are about discrete schemata, while we would like to talk about functions over the continuum. We did not succeed to do so yet, but we propose here a substantial step towards this direction: We provide a characterization of polynomial time computable functions from the integers to the reals using discrete linear ODEs: considering linear ODEs is very natural in the context of ODEs.

To do so, we naturally go to talking about algebra of functions more general than discrete functions, that is to say over more general space than $\mathbb{N}$ and $\mathbb{Z}$. This introduces some subtleties, and difficulties, that we discuss in this article, with our various concepts, definitions and statements. Hence, we consider in this article functions of type $f: S_1 \times \dots \times S_d \to S_0$, where each $S_i$ is either $\mathbb{N}$, $\mathbb{Z}$ or $\mathbb{Q}$ or $\mathbb{R}$, or is possibly vectorial functions whose components (that is
to say coordinates/projections) are of this type. We denote $\mathcal{F}$ for the class of such functions. Clearly, we can consider $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}$, but as functions may have different type of outputs, composition is an issue. We simply admit that composition may not be defined in some cases. In other words, we consider that composition is a partial operator: for example, given $f: \mathbb{N} \to \mathbb{R}$ and $g: \mathbb{R} \to \mathbb{R}$, the composition of $g$ and $f$ is defined as expected, but $f$ cannot be composed with a function such as $h: \mathbb{N} \to \mathbb{N}$.

We then consider the class

$$ \mathbb{L}\mathbb{D}\mathbb{L}^{\bullet} = [0, 1, \pi_i^k, \ell(x), +, -, \times, \overline{\text{cond}}(x), \frac{x}{2}; \text{composition, linear length ODE}] $$

of functions of $\mathcal{F}$. Here

- $\ell: \mathbb{N} \to \mathbb{N}$ is the length function, mapping some integer to the length of its binary representation,

- $\frac{x}{2}: \mathbb{R} \to \mathbb{R}$ is the function that divides by 2, and all other basic functions are defined exactly as for $\mathbb{L}\mathbb{D}\mathbb{L}$, but considered here as functions from the reals to reals.

- $\overline{\text{cond}}(x): \mathbb{R} \to \mathbb{R}$ is some piecewise affine function that takes value 1 for $x > \frac{3}{4}$ and 0 for $x < \frac{1}{4}$, and continuous piecewise affine. In particular, its restrictions to the integer is the function $\text{sg}(x)$ considered in $\mathbb{L}\mathbb{D}\mathbb{L}$.

We prove the following ($\|\cdot\|$ stands for the sup-norm).

**Theorem 3 (Main theorem 1).** A function $\mathbf{f}: \mathbb{N}^d \to \mathbb{R}^{d'}$ is computable in polynomial time if and only if there exists $\tilde{\mathbf{f}}: \mathbb{N}^{d+1} \to \mathbb{R}^{d'} \in \mathbb{L}\mathbb{D}\mathbb{L}^{\bullet}$ such that for all $\mathbf{m} \in \mathbb{N}^d$, $n \in \mathbb{N}$, $\|\tilde{\mathbf{f}}(\mathbf{m}, 2^n) - \mathbf{f}(\mathbf{m})\| \le 2^{-n}$.

From the fact that we have the reverse direction in the previous theorem, it is natural to consider the operation that maps $\tilde{\mathbf{f}}$ to $\mathbf{f}$. Namely, we introduce the operation $\text{ELim}$ ($\text{ELim}$ stands for Effective Limit):

**Definition 1 (Operation $\text{ELim}$).** Given $\tilde{\mathbf{f}}: \mathbb{N}^{d+1} \to \mathbb{R}^{d'} \in \mathbb{L}\mathbb{D}\mathbb{L}^{\bullet}$ such that for all $\mathbf{m} \in \mathbb{N}^d$, $n \in \mathbb{N}$, $\|\tilde{\mathbf{f}}(\mathbf{m}, 2^n) - \mathbf{f}(\mathbf{m})\| \le 2^{-n}$ for some function $\mathbf{f}$, then $\text{ELim}(\tilde{\mathbf{f}})$ is the (clearly uniquely defined) corresponding function $\mathbf{f}: \mathbb{N}^d \to \mathbb{R}^{d'}$.

We obtain our main result, that provides a characterization of polynomial time computable functions for functions from the integers to the reals.

**Theorem 4 (Main theorem 2).** A function $\mathbf{f}: \mathbb{N}^d \to \mathbb{R}^{d'}$ is computable in polynomial time if and only if all its components can be written through the $\overline{\mathbb{L}\mathbb{D}\mathbb{L}^{\bullet}}$ scheme, where:

$$ \overline{\mathbb{L}\mathbb{D}\mathbb{L}^{\bullet}} = [0, 1, \pi_i^k, \ell(x), +, -, \times, \overline{\text{cond}}(x), \frac{x}{2}; \text{composition, linear length ODE, } \text{ELim}]. $$

In particular:

**Theorem 5.** $\overline{\mathbb{L}\mathbb{D}\mathbb{L}^{\bullet}} \cap \mathbb{R}^{\mathbb{N}} = \text{FPTIME} \cap \mathbb{R}^{\mathbb{N}}$
In Section 2, we recall the theory of discrete ODEs. In Section 3, we recall required concepts from computable analysis. In Section 4, we prove that functions from $L^{DL^*}$ are polynomial time computable. Section 5 is proving a kind of reverse implication for functions over words. Then this is extended in Section 6 to functions from integers to the reals, and we obtain a proof of Theorem 3. Section 7 then proves Theorems 4 and 5. Section 8 is some generalizations of these results. Section 9 discusses future work and difficulties to go to functions of $R^R$.

*Related work.* Various computability and complexity classes have been recently characterized using (classical) continuous ODEs: The most up-to-date survey is [4]. Dealing with discrete ODEs is really different, as most of the constructions heavily rely on some closure properties of continuous ODEs not true for discrete ODEs, in particular because there is no chain rule formula for discrete derivation. The idea of considering discrete ODEs as a model of computation is due to [5, 6].

In a non-ODE centric point of view, we are characterizing some complexity classes using particular discrete schemata. Recursion schemes constitute a major approach of computability theory and to some extent of complexity theory. The foundational characterization of **FPTIME** due to Cobham [12], and then others based on safe recursion [13] or ramification ([16, 17]), or for other classes [18], gave birth to the very vivid field of *implicit complexity* at the interplay of logic and theory of programming: See [19, 20] for monographs.

Our ways of simulating Turing machines have some reminiscence of similar constructions used in other contexts such as Neural Networks [21, 22]. But with respect to all previous contexts, as far as we know, only a few papers have been devoted to characterizations of complexity, and even computability, classes in the sense of computable analysis. There have been some attempts using continuous ODEs [23], or the so-called $R$-recursive functions [4]. For discrete schemata, we only know [24] and [25], focusing on computability and not complexity.

## 2 Some concepts from the theory of discrete ODEs

In this section, we recall some concepts and definitions from discrete ODEs, either well-known or established in [5, 6]. We need to slightly extend the concept of sg-polynomial expression from [5, 6] to allow expressions with $cond()$ instead of $sg()$.

**Definition 2 (Extension of [5, 6]).** A *cond-polynomial expression* $P(x_1, ..., x_h)$ is an expression built-on +, -, x (often denoted ·) and *cond()* functions over a set of variables $V = \{x_1, ..., x_h\}$ and integer constants. The degree $deg(x, P)$ of a term $x \in V$ in $P$ is defined inductively as follows: $deg(x, x) = 1$ and for $x' \in V \cup \mathbb{Z}$ such that $x' \neq x$, $deg(x, x') = 0$; $deg(x, P+Q) = \max\{deg(x, P), deg(x, Q)\}$; $deg(x, P \times Q) = deg(x, P) + deg(x, Q)$; $deg(x, sg(P)) = 0$. A *cond-polynomial* expression $P$ is *essentially constant* in $x$ if $deg(x, P) = 0$.
Compared to the classical notion of degree in polynomial expression, all sub-terms that are within the scope of a sign (that is to say cond()) function contributes 0 to the degree. A vectorial function (respectively a matrix or a vector) is said to be a cond-polynomial expression if all its coordinates (respectively coefficients) are. It is said to be essentially constant if all its coefficients are.

**Definition 3 ([5, 6]).** A cond-polynomial expression $g(f(x, y), x, y)$ is essentially linear in $f(x, y)$ if it is of the form $g(f(x, y), x, y) = A[f(x, y), x, y] \cdot f(x, y) + B[f(x, y), x, y]$ where $A$ and $B$ are cond-polynomial expressions essentially constant in $f(x, y)$.

For example, the expression $P(x, y, z) = x \cdot \overline{\text{cond}}((x^2 - z) \cdot y) + y^3$ is essentially linear in $x$, essentially constant in $z$ and not linear in $y$. The expression: $z + (1 - \overline{\text{cond}}(x)) \cdot (1 - \overline{\text{cond}}(-x)) \cdot (y - z)$ is essentially constant in $x$ and linear in $y$ and $z$.

**Definition 4 (Linear length ODE [5, 6]).** Function $f$ is linear $\mathcal{L}$-ODE definable (from $\mathbf{u}$, $\mathbf{g}$ and $\mathbf{h}$) if it corresponds to the solution of

$$ \mathbf{f}(0, \mathbf{y}) = \mathbf{g}(\mathbf{y}) \quad \text{and} \quad \frac{\partial \mathbf{f}(x, \mathbf{y})}{\partial t} = \mathbf{u}(\mathbf{f}(x, \mathbf{y}), \mathbf{h}(x, \mathbf{y}), x, \mathbf{y}) \quad (2) $$

where $\mathbf{u}$ is essentially linear in $\mathbf{f}(x, y)$.

### 3 Some concepts from computable analysis

When we say that a function $f: S_1 \times \dots \times S_d \to \mathbb{R}^{d'}$ is (respectively: polynomial-time) computable this will always be in the sense of computable analysis. We recall here the basic concepts and definitions, mostly following the book [26], whose subject is complexity theory in computable analysis. Alternative presentations include [27, 15]. Actually, as we want to talk about functions in $\mathcal{F}$, we need to mix complexity issues dealing with integer and real arguments.

A dyadic number $d$ is a rational number with a finite binary expansion. That is to say $d = m/2^n$ for some integers $m \in \mathbb{Z}$, $n \in \mathbb{N}$, $n \ge 0$. Let $\mathbb{D}$ be the set of all dyadic rational numbers. We denote by $\mathbb{D}_n$ the set of all dyadic rationals $d$ with a representation $s$ of precision $\text{prec}(s) = n$; that is, $\mathbb{D}_n = \{m \cdot 2^{-n} \mid m \in \mathbb{Z}\}$.

**Definition 5 ([26]).** For each real number $x$, a function $\phi: \mathbb{N} \to \mathbb{D}$ is said to binary converge to $x$ if for all $n \in \mathbb{N}$, $\text{prec}(\phi(n)) = n$ and $|\phi(n) - x| \le 2^{-n}$. Let $CF_x$ (Cauchy function) denote the set of all functions binary converging to $x$.

Intuitively Turing machine $M$ computes a real function $f$ in the following way: 1. The input $x$ to $f$, represented by some $\phi \in CF_x$, is given to $M$ as an oracle; 2. The output precision $2^{-n}$ is given in the form of integer $n$ as the input to $M$; 3. The computation of $M$ usually takes two steps, though sometimes these two steps may be repeated for an indefinite number of times: 4. $M$ computes, from the output precision $2^{-n}$, the required input precision $2^{-m}$; 5. $M$ queries
the oracle to get $\phi(m)$, such that $\|\phi(m) - x\| \le 2^{-m}$, and computes from $\phi(m)$ an output $d \in \mathbb{D}$ with $\|d - f(x)\| \le 2^{-n}$.

More formally:

**Definition 6 ([26]).** A real function $f : \mathbb{R} \to \mathbb{R}$ is computable if there is a function-oracle TM $M$ such that for each $x \in \mathbb{R}$ and each $\phi \in CF_x$, the function $\psi$ computed by $M$ with oracle $\phi$ (i.e., $\psi(n) = M^{\phi}(n)$) is in $CF_{f(x)}$.

Assume that $M$ is an oracle machine which computes $f$ on domain $G$. For any oracle $\phi \in CF_x$, with $x \in G$, let $T_M(\phi, n)$ be the number of steps for $M$ to halt on input $n$ with oracle $\phi$, and $T'_M(x, n) = \max\{T_M(\phi, n) \mid \phi \in CF_x\}$. The time complexity of $f$ is defined as follows.

**Definition 7 ([26]).** Let $G$ be bounded closed interval $[a, b]$. Let $f : G \to \mathbb{R}$ be a computable function. Then, we say that the time complexity of $f$ on $G$ is bounded by a function $t : G \times \mathbb{N} \to \mathbb{N}$ if there exists an oracle TM $M$ which computes $f$ such that for all $x \in G$ and all $n > 0$, $T'_M(x, n) \le t(x, n)$.

In other words, the idea is to measure the time complexity of a real function based on two parameters: input real number $x$ and output precision $2^{-n}$. Sometimes, it is more convenient to simplify the complexity measure to be based on only one parameter, the output precision. For this purpose, we say the uniform time complexity of $f$ on $G$ is bounded by a function $t' : \mathbb{N} \to \mathbb{N}$ if the time complexity of $f$ on $G$ is bounded by a function $t : G \times \mathbb{N} \to \mathbb{N}$ with the property that for all $x \in G$, $t(x, n) \le t'(n)$.

However, if we do so, it is important to realize that if we had taken $G = \mathbb{R}$ in the previous definition, for unbounded functions $f$, the uniform time complexity would not exist, because the number of moves required to write down the integral part of $f(x)$ grows as $x$ approaches $+\infty$ or $-\infty$. Therefore, the approach of [26] is to do as follows (the bounds $-2^X$ and $2^X$ are somewhat arbitrary, but are chosen here because the binary expansion of any $x \in (-2^n, 2^n)$ has $n$ bits in the integral part).

**Definition 8 (Adapted from [26]).** For functions $f(x)$ whose domain is $\mathbb{R}$, we say that the (non-uniform) time complexity of $f$ is bounded by a function $t' : \mathbb{N}^2 \to \mathbb{N}$ if the time complexity of $f$ on $[-2^X, 2^X]$ is bounded by a function $t : \mathbb{N}^2 \to \mathbb{N}$ such that $t(x, n) \le t'(X, n)$ for all $x \in [-2^X, 2^X]$.

As we want to talk about general functions in $\mathcal{F}$, we extend the approach to more general functions. (for conciseness, when $\mathbf{x} = (x_1, \dots, x_p)$, $\mathbf{X} = (X_1, \dots, X_p)$, we write $\mathbf{x} \in [-2^{\mathbf{X}}, 2^{\mathbf{X}}]$ as a shortcut for $x_1 \in [-2^{X_1}, 2^{X_1}]$, $\dots$, $x_p \in [-2^{X_p}, 2^{X_p}]$).

**Definition 9 (Complexity for real functions: general case).** Consider a function $f(x_1, \dots, x_p, n_1, \dots, n_q)$ whose domain is $\mathbb{R}^p \times \mathbb{N}^q$. We say that the (non-uniform) time complexity of $f$ is bounded by a function $t' : \mathbb{N}^{p+q+1} \to \mathbb{N}$ if the time complexity of $f(\cdot, \dots, \cdot, \ell(n_1), \dots, \ell(n_q))$ on $[-2^{X_1}, 2^{X_1}] \times \dots \times [-2^{X_p}, 2^{X_p}]$ is bounded by a function $t(\cdot, \dots, \cdot, \ell(n_1), \dots, \ell(n_q), \cdot) : \mathbb{N}^p \times \mathbb{N} \to \mathbb{N}$ such that $t(\mathbf{x}, \ell(n_1), \dots, \ell(n_q), n) \le t'(\mathbf{X}, \ell(n_1), \dots, \ell(n_q), n)$ whenever $\mathbf{x} \in [-2^{\mathbf{X}}, 2^{\mathbf{X}}]$.
We say that $f$ is polynomial time computable if $t'$ can be chosen as a polynomial. We say that a vectorial function is polynomial time computable iff all its components are.

We do so that this measure of complexity extends the usual complexity for functions over the integers, where complexity of integers is measured with respects of their lengths, and over the reals, where complexity is measured with respect to their approximation. In particular, in the specific case of a function $f: \mathbb{N}^d \to \mathbb{R}^d$, that basically means there is some polynomial $t': \mathbb{N}^{d+1} \to \mathbb{N}$ so that the time complexity of producing some dyadic approximating $f(m)$ at precision $2^{-n}$ is bounded by $t'(\ell(m_1), \dots, \ell(m_d), n)$.

In other words, when considering that a function is polynomial time computable, it is in the length of all its integer arguments, as this is the usual convention. However, we need sometimes to consider also polynomial dependency directly in one of some specific integer argument, say $n_i$, and not on its length $\ell(n_i)$. We say that the function is polynomial time computable, with respect to the value of $n_i$ when this holds (keeping possible other integer arguments $n_j$, $j \neq i$, measured by their length).

A well-known observation is the following.

**Theorem 6.** Consider $f$ as in Definition 9 computable in polynomial time. Then $f$ has a polynomial modulus function of continuity, that is to say there is a polynomial function $m_f: \mathbb{N}^{p+q+1} \to \mathbb{N}$ such that for all $\mathbf{x}, \mathbf{y}$ and all $n > 0$, $\|\mathbf{x} - \mathbf{y}\| \le 2^{-m_f(\mathbf{x}, \ell(n_1), \dots, \ell(n_q), n)}$ implies $\|f(\mathbf{x}, n_1, \dots, n_q) - f(\mathbf{y}, n_1, \dots, n_q)\| \le 2^{-n}$, whenever $\mathbf{x}, \mathbf{y} \in [-2^\mathbf{x}, 2^\mathbf{y}]$.

# 4 Functions from LDL• are in FPTIME

The following proposition can be proved by induction from standard arguments. The hardest part is to prove that the class of polynomial time computable functions is preserved by the linear length ODE schema: This is Lemma 3.

**Proposition 1.** All functions of LDL• are computable (in the sense of computable analysis) in polynomial time.

The following lemmas are proved in [5, 6].

**Lemma 1 (Alternative view, case of Length ODEs, from [5, 6]).** Let $f: \mathbb{N}^{p+1} \to \mathbb{Z}^d, \mathcal{L}: \mathbb{N}^{p+1} \to \mathbb{Z}$ be some functions and assume that (1) holds considering $\mathcal{L}(\mathbf{x}, \mathbf{y}) = \ell(\mathbf{x})$. Then $f(\mathbf{x}, \mathbf{y})$ is given by $f(\mathbf{x}, \mathbf{y}) = \mathbf{F}(\ell(\mathbf{x}), \mathbf{y})$ where $\mathbf{F}$ is the solution of initial value problem

$$ \begin{aligned} \mathbf{F}(1, \mathbf{y}) &= \mathbf{f}(0, \mathbf{y}), \\ \frac{\partial \mathbf{F}(t, \mathbf{y})}{\partial t} &= \mathbf{h}(\mathbf{F}(t, \mathbf{y}), 2^t - 1, \mathbf{y}). \end{aligned} $$
**Lemma 2 (Solution of linear ODE, from [5,6]).** For matrices **A** and vectors **B** and **G**, the solution of equation $\mathbf{f}'(x, \mathbf{y}) = \mathbf{A}(\mathbf{f}(x, \mathbf{y}), \mathbf{h}(x, \mathbf{y}), x, \mathbf{y}) \cdot \mathbf{f}(x, \mathbf{y}) + \mathbf{B}(\mathbf{f}(x, \mathbf{y}), \mathbf{h}(x, \mathbf{y}), x, \mathbf{y})$ with initial conditions $\mathbf{f}(0, \mathbf{y}) = \mathbf{G}(\mathbf{y})$ is

$$ \mathbf{f}(x, \mathbf{y}) = \left( \bar{2} \int_{0}^{x} \mathbf{A}(\mathbf{f}(t, \mathbf{y}), \mathbf{h}(t, \mathbf{y}), t, \mathbf{y}) \delta t \right) \cdot \mathbf{G}(\mathbf{y}) + \int_{0}^{x} \left( \bar{2} \int_{u+1}^{x} \mathbf{A}(\mathbf{f}(t, \mathbf{y}), \mathbf{h}(t, \mathbf{y}), t, \mathbf{y}) \delta t \right) \cdot \mathbf{B}(\mathbf{f}(u, \mathbf{y}), \mathbf{h}(u, \mathbf{y}), u, \mathbf{y}) \delta u. $$

**Remark 2.** Notice, as in [5, 6], that this can be rewritten as

$$ \mathbf{f}(x, \mathbf{y}) = \sum_{u=-1}^{x-1} \left( \prod_{t=u+1}^{x-1} (1 + \mathbf{A}(\mathbf{f}(t, \mathbf{y}), \mathbf{h}(t, \mathbf{y}), t, \mathbf{y})) \right) \cdot \mathbf{B}(\mathbf{f}(u, \mathbf{y}), \mathbf{h}(u, \mathbf{y}), u, \mathbf{y}), \quad (3) $$

with the (not so usual) conventions that for any function $\kappa(\cdot)$, $\prod_{x}^{x-1} \kappa(x) = 1$ and $\mathbf{B}(-1, \mathbf{y}) = \mathbf{G}(\mathbf{y})$.

**Lemma 3.** The class of polynomial time computable functions is preserved by the linear length ODE schema.

We propose to write $\vec{x}$ for $2^x - 1$ for conciseness. We write $\|\cdot\|$ for the sup norm of integer part: given some matrix $\mathbf{A} = (A_{i,j})_{1\le i\le n, 1\le j\le m}$, $\|\mathbf{A}\| = \max_{i,j} [A_{i,j}]$. In particular, given a vector $\mathbf{x}$, it can be seen as a matrix with $m=1$, and $\|\mathbf{x}\|$ is the sup norm of the integer part of its components.

*Proof.* Using Lemma 1, when the schema of Definition 4 holds, we can do a change of variable to consider $\mathbf{f}(x, \mathbf{y}) = \mathbf{F}(\ell(x), \mathbf{y})$, with $\mathbf{F}$ solution of a discrete ODE of the form $\frac{\partial \mathbf{F}(t, \mathbf{y})}{\partial t} = \mathbf{A}(\mathbf{F}(t, \mathbf{y}), \mathbf{h}(\vec{t}, \mathbf{y}), \vec{t}, \mathbf{y}) \cdot \mathbf{F}(t, \mathbf{y}) + \mathbf{B}(\mathbf{F}(t, \mathbf{y}), \mathbf{h}(\vec{t}, \mathbf{y}), \vec{t}, \mathbf{y})$, that is to say, of the form (4) below. It then follows from:

**Lemma 4 (Fundamental observation).** Consider the ODE

$$ \mathbf{F}'(x, \mathbf{y}) = \mathbf{A}(\mathbf{F}(x, \mathbf{y}), \mathbf{h}(\vec{x}, \mathbf{y}), \vec{x}, \mathbf{y}) \cdot \mathbf{F}(x, \mathbf{y}) + \mathbf{B}(\mathbf{F}(x, \mathbf{y}), \mathbf{h}(\vec{x}, \mathbf{y}), \vec{x}, \mathbf{y}). \quad (4) $$

Assume:

1. The initial condition $\mathbf{G}(\mathbf{y}) \stackrel{\text{def}}{=} \mathbf{F}(0, \mathbf{y})$, as well as $\mathbf{h}(\vec{x}, \mathbf{y})$ are polynomial time computable with respect to the value of $x$.

2. $\mathbf{A}(\mathbf{F}(x, \mathbf{y}), \mathbf{h}(\vec{x}, \mathbf{y}), \vec{x}, \mathbf{y})$ and $\mathbf{B}(\mathbf{F}(x, \mathbf{y}), \mathbf{h}(\vec{x}, \mathbf{y}), \vec{x}, \mathbf{y})$ are sg-polynomial expressions essentially constant in $\mathbf{F}(x, \mathbf{y})$.

Then, there exists a polynomial $p$ such that $\ell(\|\mathbf{F}(x, \mathbf{y})\|) \le p(x, \ell(\|\mathbf{y}\|))$ and $\mathbf{F}(x, \mathbf{y})$ is polynomial time computable with respect to the value of $x$.

*Proof.* The fact that there exists a polynomial $p$ such that $\ell(\|\mathbf{F}(x, \mathbf{y})\|) \le p(x, \ell(\|\mathbf{y}\|))$, follows from the fact that we can write some explicit formula for the solution of (4): This is Lemma 2 below repeated from [5, 6]. Now, bounding the size of the right hand side of formula (3) provides the statement.
Now the fact that $\mathbf{F}(x, \mathbf{y})$ is polynomial time computable, follows from a reasoning similar to the one of following lemma (the lemma below restricts the form of the recurrence by lack of space, but the more general recurrence of (4) would basically not lead to any difficulty): The fact that the modulus of continuity of a linear expression of the form of the right hand side of (4) is necessarily affine in its first argument follows from the hypotheses and from previous paragraph, using the fact that $\text{cond}()$ has a linear modulus of convergence.

**Lemma 5.** Suppose that function the $\mathbf{f}: \mathbb{N} \times \mathbb{R}^d \to \mathbb{R}^{d'}$ is such that for all $x, \mathbf{y}$,

$$ \mathbf{f}(0, \mathbf{y}) = \mathbf{g}(\mathbf{y}) \quad \text{and} \quad \mathbf{f}(x+1, \mathbf{y}) = \mathbf{h}(\mathbf{f}(x, \mathbf{y}), x, \mathbf{y}) $$

for some functions $\mathbf{g}: \mathbb{R}^d \to \mathbb{R}^{d'}$ and $\mathbf{h}: \mathbb{R}^{d'} \times \mathbb{R} \times \mathbb{R}^d \to \mathbb{R}^{d'}$ both computable in polynomial time with respect to the value of $x$. Suppose that the modulus $m_h$ of continuity of $\mathbf{h}$ is affine in its first argument: For all functions $\mathbf{f}, \mathbf{f}'$ defined in $[-2\mathbf{F}, 2\mathbf{F}]$, $\mathbf{y} \in [-2\mathbf{Y}, 2\mathbf{Y}]$, $\|\mathbf{f} - \mathbf{f}'\| \le 2^{-m_h}(\mathbf{F}, \ell(x), \mathbf{Y}, n)$ implies $|\mathbf{h}(\mathbf{f}, x, \mathbf{y}) - \mathbf{h}(\mathbf{f}', x, \mathbf{y})| \le 2^{-n}$ with $m_h(\mathbf{F}, \ell(x), \mathbf{Y}, n) = \alpha n + p_h(\mathbf{F}, \ell(x), \mathbf{Y})$ for some $\alpha$. Suppose there exists a polynomial $p$ such that $\ell(\|\mathbf{f}(x, \mathbf{y})\|) \le p(x, \ell(\|\mathbf{y}\|))$.

Then $\mathbf{f}(x, \mathbf{y})$ is computable in polynomial time with respect to the value of $x$.

*Proof.* The point is that we can compute $\mathbf{f}(n, \mathbf{y})$ by $\mathbf{z}_0 = \mathbf{f}(0, \mathbf{y}) = \mathbf{g}(\mathbf{y})$, then $\mathbf{z}_1 = \mathbf{f}(1, \mathbf{y}) = \mathbf{h}(\mathbf{z}_0, 0, \mathbf{y})$, then $\mathbf{z}_2 = \mathbf{f}(2, \mathbf{y}) = \mathbf{h}(\mathbf{z}_1, 1, \mathbf{y})$, then ..., then $\mathbf{z}_m = \mathbf{f}(m, \mathbf{y}) = \mathbf{h}(\mathbf{z}_{m-1}, m-1, \mathbf{y})$. One needs to do so with some sufficient precision so that the result given by $\mathbf{f}(l, \mathbf{y})$ is correct, and so that the whole computation can be done in polynomial time.

Given $\mathbf{y}$, we can determine $\mathbf{Y}$ such that $\mathbf{y} \in [-2\mathbf{Y}, 2\mathbf{Y}]$. Assume for now that for all $m$,

$$ z_m \in [-2^{Z_m}, 2^{Z_m}] \qquad (5) $$

For $i = 0, 1, \dots, l$, consider $p(i) = \alpha^{l-i}n + \sum_{k=i}^{l-1} \alpha^{k-i}p_h(\mathbf{Z}_k, \ell(k), \mathbf{Y})$.

Using the fact that $\mathbf{g}$ is computable, approximate $\mathbf{z}_0 = \mathbf{g}(\mathbf{y})$ with precision $2^{-p(0)}$. This is doable polynomial time with respect to the value of $p(0)$.

Then for $i = 0, 1, \dots, l$, using the approximation of $\mathbf{z}_i$ with precision $2^{-p(i)}$, compute an approximation of $\mathbf{z}_{i+1}$ with precision $2^{-p(i+1)}$: this is feasible to get precision $2^{-p(i+1)}$ of $\mathbf{z}_{i+1}$, as $\mathbf{z}_{i+1} = \mathbf{f}(i+1, \mathbf{y}) = \mathbf{h}(\mathbf{z}_i, i, \mathbf{y})$, it is sufficient to consider precision $m_h(\mathbf{Z}_i, \ell(i), \mathbf{Y}, p(i+1)) = \alpha p(i+1) + p_h(\mathbf{Z}_i, \ell(i), \mathbf{Y}) = \alpha^{l-i-1+1}n + \sum_{k=i+1}^{l-1} \alpha^{k-i-1+1}p_h(\mathbf{Z}_k, \ell(k), \mathbf{Y}) + p_h(\mathbf{Z}_i, \ell(i), \mathbf{Y}) = p(i)$. Observing that $p(l) = n$, we get $z_l$ with precision $2^{-n}$. All of this is indeed feasible in polynomial time with respect to the value of $l$, under the condition that all the $\mathbf{Z}_i$ remain of size polynomial, that is to say, that we have indeed (5). But this follows from our hypothesis on $\ell(\|\mathbf{f}(x, \mathbf{y})\|)$.

# 5 Functions from FPTIME are in LDDL•

This section is devoted to prove a kind of reverse implication of Proposition 1: For any polynomial time computable function $\mathbf{f}: \mathbb{N}^d \to \mathbb{R}^{d'}$, we can construct
some function $\tilde{f} \in \text{LDL}^\bullet$ that simulates the computation of $f$. This basically requires to be able to simulate the computation of a Turing machine using some functions from $\text{LDL}^\bullet$.

Consider without loss of generality some Turing machine

$$M = (Q, \{0, 1\}, q_{\text{init}}, \delta, F)$$

using the symbols 0, 1, 3, where $B = 0$ is the blank symbol. The reason of the choice of symbols 1 and 3 will be made clear later. We assume $Q = \{0, 1, \dots, |Q|-1\}$. Let

$$\dots l_{-k}l_{-k+1}\dots l_{-1}l_0r_0r_1\dots r_n\dots$$

denote the content of the tape of the Turing machine $M$. In this representation, the head is in front of symbol $r_0$, and $l_i, r_i \in \{0, 1, 3\}$ for all $i$. Such a configuration $C$ can be denoted by $C = (q, l, r)$, where $l, r \in \Sigma^\omega$ are (possibly infinite, if we consider that the tape can be seen as a non finite word, in the case there is no blank on it) words over alphabet $\Sigma = \{1, 3\}$ and $q \in Q$ denotes the internal state of $M$.

The idea is that such a configuration $C$ can also be encoded by some element $\gamma_{\text{config}}(C) = (q, \tilde{l}, \tilde{r}) \in \mathbb{N} \times \mathbb{R}^2$, by considering

$$\begin{align*} \bar{r} &= r_0 4^{-1} + r_1 4^{-2} + \dots + r_n 4^{-(n+1)} + \dots, \\ \bar{l} &= l_0 4^{-1} + l_{-1} 4^{-2} + \dots + l_{-k} 4^{-(k+1)} + \dots \end{align*}$$

Basically, in other words, we encode the configuration of bi-infinite tape Turing machine $M$ by real numbers using their radix 4 encoding, but using only digits 1,3. If we write: $\gamma_{\text{word}} : \Sigma^\omega \to \mathbb{R}$ for the function that maps word $w = w_0 w_1 w_2 \dots$ to $\gamma_{\text{word}}(w) = w_0 4^{-1} + w_1 4^{-2} + \dots + w_n 4^{-(n+1)} + \dots$, we can also write $\gamma_{\text{config}}(C) = \gamma_{\text{config}}(q, l, r) = (q, \gamma_{\text{word}}(l), \gamma_{\text{word}}(r))$.

Notice that this lives in $Q \times [0, 1]^2$. Actually, if we denote the image of $\gamma_{\text{word}} : \Sigma^\omega \to \mathbb{R}$ by $\mathcal{I}$, this even lives in $Q \times \mathcal{I}^2$.

**Lemma 6.** We can construct some function $\text{Next}$ in $\text{LDL}^\bullet$ that simulates one step of $M$, i.e. that computes the Next function sending a configuration $C$ of Turing machine $M$ to the next one. This function is essentially linear.

*Proof.* We can write $l = l_0 l^\bullet$ and $r = r_0 r^\bullet$, where $l^\bullet$ and $r^\bullet$ corresponding to (possibly infinite) word $l_{-1} l_{-2} \dots$ and $r_1 r_2 \dots$ respectively.

$$\begin{tikzpicture}
\draw (0,0) -- (1,0) node[right] {$\dots l^\bullet | l_0 | r_0 | r^\bullet \dots$};
\node[below] at (0.5,0) {$\sim$};
\node[below] at (0.5,1) {$\sim$};
\node[left] at (-0.5,0) {$l$};
\node[right] at (0.5,1) {$r$};
\end{tikzpicture}$$

The function Next is basically of the form

$$\begin{align*} \text{Next}(q, l, r) &= \text{Next}(q, l^\bullet l_0, r_0 r^\bullet) = (q', l', r') \\ &= (q', l^\bullet l_0 x, r^\bullet) \quad \text{whenever } \delta(q, r_0) = (q', x, \rightarrow) \\ &\quad (q', l^\bullet, l_0 x r^\bullet) \quad \text{whenever } \delta(q, r_0) = (q', x, \leftarrow) \\ &\dots \end{align*}$$
where the dots is a list of lines of similar types for the various values of $q$ and $\bar{r}_0$. This rewrites as a function $\overline{Next}$ which is similar, working over the representation of the configurations as reals:

$$
\begin{align*}
\overline{Next}(q, \bar{l}, \bar{r}) &= \overline{Next}(q, \overline{l \bullet l_0}, \overline{r_0 r^\bullet}) = (q', \overline{l'}, \overline{r'}) \\
&= (q', \overline{l \bullet l_0 x}, \overline{r^\bullet}) \quad \text{whenever } \delta(q, r_0) = (q', x, \rightarrow) \\
&= (q', \overline{l \bullet}, \overline{l_0 x r^\bullet}) \quad \text{whenever } \delta(q, r_0) = (q', x, \leftarrow)
\end{align*}
$$

where $r_0 = \lfloor 4\bar{r} \rfloor$ and ...

• in the first case “→” : $\overline{l'} = 4^{-1}\overline{l} + 4^{-1}x$ and $\overline{r'} = \overline{r^\bullet} = \{4\overline{r}\}$ (6)

• in the second case “←” : $\overline{l'} = \overline{l^\bullet} = \{4\overline{l}\}$ and $\overline{r'} = 4^{-2}\overline{r^\bullet} + 4^{-2}x + \lfloor 4\overline{l} \rfloor$

Here {.} stands for fractional part.

The problem about such expressions is that we cannot expect the integer part and the fractional part function to be in $\overline{LDL^\bullet}$ (as functions of this class are computable, and hence continuous, unlike the fractional part). But, a key point is that from our trick of using only symbols 1 and 3, we are sure that in an expression like $\lfloor \bar{r} \rfloor$, either it values 0 (this is the specific case where there remain only blanks in $r$), or that $4\bar{r}$ lives in interval $[1, 1+1)$ or in interval $[3, 3+1)$. That means that we could replace $\{4\bar{r}\}$ by $\sigma(4\bar{r})$ where $\sigma$ is some (piecewise affine) function obtained by composing in a suitable way the basic functions of $\overline{LDL^\bullet}$. Namely, define $\text{If}(b, T, E)$ as a synonym for $\text{cond}(b) \times T + (1 - \text{cond}(b)) \times E$. Then, considering $i(x) = \text{If}(x, 0, \text{If}(x-1, 1, 3))$, $\sigma(x) = x - i(x)$, then $i(4\bar{r})$ would be the same as $\lfloor 4\bar{r} \rfloor$, and $\sigma(4\bar{r})$ would be the same as $\{4\bar{r}\}$ in our context in above expressions. In other words, we could replace the paragraph (6) above by:

where $r_0 = i(4\bar{r})$

• in the first case “→” : $\overline{l'} = 4^{-1}\overline{l} + 4^{-1}x$ and $\overline{r'} = \overline{r^\bullet} = \sigma(4\overline{r})$

• in the second case “←” : $\overline{l'} = \overline{l^\bullet} = \sigma(4\overline{l})$ and $\overline{r'} = 4^{-2}\overline{r^\bullet} + 4^{-1}x + i(4\overline{l})$

and get something that would be still work exactly, but using only functions from $\overline{LDL^\bullet}$. Notice that these imbrications of $\text{If}$ rewrite to an essentially constant expression.

We can then write:

$$
q' = \text{If}(q-0, \text{nextq}^0, \text{If}(q-1, \text{nextq}^1, \dots, \text{If}(q-|Q-2|, \text{nextq}^{|Q|-2}, \text{nextq}^{|Q|-1})))
$$

where

$$
\text{nextq}^q = \text{If}(v-0, \text{nextq}_0^q, \text{If}(v-1, \text{nextq}_1^q, \text{nextq}_3^q))
$$

and where $\text{nextq}_v^q = q'$ if $\delta(q, v) = (q', x, m)$ for $m \in \{\leftarrow, \rightarrow\}$, for $v \in \{0, 1, 3\}$.
Similarly, we can write

$$
r' = \text{If}(q-0, \text{nextr}^0, \text{If}(q-1, \text{nextr}^1, \dots, \text{If}(q-|Q-2|, \text{nextr}^{|Q|-2}, \text{nextr}^{|Q|-1})))
$$

where $\text{nextr}^q = \text{If}(v-0, \text{nextr}_0^q, \text{If}(v-1, \text{nextr}_1^q, \text{nextr}_3^q))$ and where $\text{nextr}_v^q$
that corresponds to the corresponding expression in the item above according
to the value of $\delta(q, v)$. We can clearly write a similar expression for $l'$. These
imbrications of $\text{If}$ rewrite to some essentially linear expressions.
Once we have one step, we can simulate some arbitrary computation of a Turing machine, using some linear length ODE:

**Proposition 2.** Consider some Turing machine *M* that computes some function *f*: Σ* → Σ* in some time *T*(*ℓ*(*ω*)) on input *ω*. One can construct some function **f**: $\mathbb{N} \times \mathbb{R} \to \mathbb{R}$ in $\mathbb{L}\mathbb{D}\mathbb{L}\bullet$ that does the same, with respect to the previous encoding: $\mathbb{f}(2^{T(\ell(\omega))}, \gamma_{\text{word}}(\omega))$ provides $f(\omega)$.

*Proof.* The idea is to define the function $\overline{Exec}$ that maps some time $2^t$ and some initial configuration $C$ to the configuration number at time $t$. This can be obtained using some linear length ODE using Lemma 6.

$$ \overline{Exec}(0, C) = C \quad \text{and} \quad \frac{\partial \overline{Exec}}{\partial \ell}(t, C) = \overline{Next}(\overline{Exec}(t, C)) $$

We can then get the value of the computation as $\overline{Exec}(2^{T(\ell(\omega))}, C_{init})$ on input $\omega$, considering $C_{init} = (q_0, 0, \gamma_{\text{word}}(\omega))$. By applying some projection, we get the following function $\mathbb{f}(x, y) = \pi_3(\overline{Exec}(x, q_0, 0, y))$ that satisfies the property.

# 6 Towards functions from integers to the reals

The purpose of this section is to prove Theorem 3. The reverse implication of Theorem 3 mostly follows from Proposition 1 and arguments from computable analysis. By lack of space, details are in appendix.

For the direct implication of Theorem 3, the difficulty is that we know from the previous section how to simulate Turing machines working over $\mathcal{I}$, while we want functions that work directly over the integers and over the reals. A key is to be able to convert from integers/reals to representations using only symbols 1 and 3, that is to say, to map integers to $\mathcal{I}$, and $\mathcal{I}$ to reals.

**Lemma 7 (From $\mathcal{I}$ to $\mathbb{R}$).** We can construct some function Encode: $\mathbb{N} \times [0, 1] \to \mathbb{R}$ in $\mathbb{L}\mathbb{D}\mathbb{L}\bullet$ that maps $\gamma_{\text{word}}(\bar{d})$ with $\bar{d} \in \{1, 3\}^*$ to some real $d$. It is surjective over the dyadic, in the sense that for any dyadic $d \in \mathbb{D}$, there is some (easily computable) such $\bar{d}$ with Encode($2^{\ell(\bar{d})}$, $\bar{d}$) = $d$.

*Proof.* Consider the following transformation: Every digit in the binary expansion of $d$ is encoded by a pair of symbols in the radix 4 encoding of $\bar{d} \in [0, 1]:$ digit 0 (respectively: 1) is encoded by 11 (respectively 13) if before the “decimal” point in $d$, and digit 0 (respectively: 1) is encoded by 31 (respectively 33) if after. For example, for $d = 101.1$ in base 2, $\bar{d} = 0.13111333$ in base 4.

The transformation from $\bar{d}$ to $d$ can be done by considering a function $F: [0, 1]^2 \to [0, 1]^2$ that satisfies

$$ F(\bar{r}_1, \bar{l}_2) = \begin{cases} (\sigma(16\bar{r}_1), 2\bar{l}_2 + 0) & \text{whenever } i(16\bar{r}_1) = 5 \\ (\sigma(16\bar{r}_1), 2\bar{l}_2 + 1) & \text{whenever } i(16\bar{r}_1) = 7 \\ (\sigma(16\bar{r}_1), (\bar{l}_2 + 0)/2) & \text{whenever } i(16\bar{r}_1) = 13 \\ (\sigma(16\bar{r}_1), (\bar{l}_2 + 1)/2) & \text{whenever } i(16\bar{r}_1) = 15 \end{cases} $$
A natural candidate for this is an expression such as $If(i(16\bar{r}_1)-0, (\sigma(16\bar{r}_1), 2\bar{l}_2+0), If(i(16\bar{r}_1)-7, (\sigma(16\bar{r}_1), 2\bar{l}_2+1), If(i(16\bar{r}_1)-13, (\sigma(16\bar{r}_1), (\bar{l}_2+0)/2), (\sigma(16\bar{r}_1), (\bar{l}_2+1)/2)))$ with $\sigma$ and $i$ constructed as suitable approximation of the fractional and integer part as in previous section.

We then just need to apply $\ell(d)$ times $F$ on $(\bar{d}, 0)$, and then project on the second component to get a function Encode that does the job. That is Encode$(x, y) = \pi_3^3(G(x, y))$ with

$$G(0, y) = (\bar{d}, 0) \quad \text{and} \quad \frac{\partial G}{\partial \ell}(t, \bar{d}, \bar{l}) = F(G(t, \bar{d}, \bar{l})).$$

**Lemma 8 (From $\mathbb{N}$ to $\mathcal{I}$).** We can construct some function Decode: $\mathbb{N}^d \to \mathbb{R}$ in $\mathbb{L}\mathbb{D}\mathbb{L}^\bullet$ that maps $n \in \mathbb{N}$ to some (easily computable) encoding of $n$ in $\mathcal{I}$.

*Proof.* We discuss only the case $d = 1$ by lack of space. Let $div_2$ (respectively: $mod_2$) denote integer (respectively remainder of) division by 2: As these functions are from $\mathbb{N} \to \mathbb{N}$, from Theorem 1 from [5, 6], they belongs to $\mathbb{L}\mathbb{D}\mathbb{L}$. Their expression in $\mathbb{L}\mathbb{D}\mathbb{L}$, replacing $\text{sg}()$ by $\text{cond}()$, provides some extensions $div_2$ and $mod_2$ in $\mathbb{L}\mathbb{D}\mathbb{L}^\bullet$. We then do something similar as in the previous lemma but now with function

$$F(\bar{r}_1, \bar{l}_2) = \begin{cases} (\overline{div_2(\bar{r}_1)}, (\bar{l}_2 + 0)/2) & \text{whenever } \overline{mod_2(\bar{r}_1)} = 0 \\ (\overline{div_2(\bar{r}_1)}, (\bar{l}_2 + 1)/2) & \text{whenever } \overline{mod_2(\bar{r}_1)} = 1. \end{cases}$$

We can now prove the direct direction of Theorem 3: Assume that $\mathbf{f}: \mathbb{N}^d \to \mathbb{R}^{d'}$ is computable in polynomial time. That means that each of its components are, thus, we can consider without loss of generality that $d' = 1$. We assume also that $d = 1$ (otherwise consider either multi-tape Turing machines, or some suitable alternative encoding in Encode). That means that we know that there is a TM polynomial time computable functions $d: \mathbb{N}^{d+1} \to \{1, 3\}^*$ so that on $\mathbf{m}, n$ it provides the encoding of some dyadic $\phi(\mathbf{m}, n)$ with $\|\phi(\mathbf{m}, n) - \mathbf{f}(\mathbf{m})\| \le 2^{-n}$ for all $\mathbf{m}$.

From Proposition 2, we can construct $\tilde{d}$ with $\tilde{d}(2^{p(max(\mathbf{m}, n))}, \text{Decode}(n, \mathbf{m})) = d(\mathbf{m}, n)$ for some polynomial $p$ corresponding to the time required to compute $d$.

Both functions $\ell(\mathbf{x}) = \ell(x_1) + \dots + \ell(x_p)$ and $B(\mathbf{x}) = 2^{\ell(\mathbf{x})} \cdot \ell(\mathbf{x})$ are in $\mathbb{L}\mathbb{D}\mathbb{L}$ (see [5, 6]). It is easily seen that: $\ell(\mathbf{x})^c \le B^{(c)}(\ell(\mathbf{x}))$ where $B^{(c)}$ is the $c$-fold composition of function $B$.

Then $\tilde{\mathbf{f}}(\mathbf{m}, n) = \text{Encode}(\tilde{d}(B^{(c)}(\max(\mathbf{m}, n)), \text{Decode}(n, \mathbf{m})))$ provides a solution such that $\|\tilde{\mathbf{f}}(\mathbf{m}, 2^n) - \mathbf{f}(\mathbf{m})\| \le 2^{-n}$.

# 7 Proving Theorems 4 and 5

Clearly Theorem 5 follows from the case where $d = 1$ and $d' = 1$ from Theorem 4. Hence, there only remain to prove Theorem 4. The direct direction is immediate from Theorem 3. For the reverse direction, by induction, the only thing to prove is that the class of functions from the integers to the reals computable in polynomial
time is preserved by the operation *ELim*. Take such a function $\tilde{f}$. By definition, given $\mathbf{m}$, we can compute $\tilde{f}(\mathbf{m}, 2^n)$ with precision $2^{-n}$ in time polynomial in $n$. This must be by definition of *ELim* schema some approximation of $f(\mathbf{m})$, and hence $f$ is computable in polynomial time.

# 8 Generalizations

Recall that a function $M: \mathbb{N} \to \mathbb{N}$ is a modulus of convergence of $g: \mathbb{N} \to \mathbb{R}$, with $g(n)$ converging toward 0 when $n$ goes to $\infty$, if and only if for all $i > M(n)$, we have $\|g(i)\| \le 2^{-n}$. A function $M: \mathbb{N} \to \mathbb{N}$ is a uniform modulus of convergence of a sequence $g: \mathbb{N}^{d+1} \to \mathbb{R}$, with $g(\mathbf{m}, n)$ converging toward 0 when $n$ goes to $\infty$ if and only if for all $i > M(n)$, we have $\|g(\mathbf{m}, i)\| \le 2^{-n}$. Intuitively, the modulus of convergence gives the speed of convergence of a sequence.

**Definition 10 (Operation $E_2Lim$).** Given $\tilde{f}: \mathbb{N}^{d+1} \to \mathbb{R} \in \mathbb{L}\mathbb{D}\mathbb{L}^\bullet$, $g: \mathbb{N}^{d+1} \to \mathbb{R}$ such that for all $\mathbf{m} \in \mathbb{N}^d$, $n \in \mathbb{N}$, $\|\tilde{f}(\mathbf{m}, 2^n) - f(\mathbf{m})\| \le g(\mathbf{m}, n)$ under the condition that $0 \le g(\mathbf{m}, n)$ is decreasing to 0, with $\|g(\mathbf{m}, p(n))\| \le 2^{-n}$ for some polynomial $p(n)$ then $E_2Lim(\tilde{f}, g)$ is the (clearly uniquely defined) corresponding function $f: \mathbb{N}^d \to \mathbb{R}^e$.

**Theorem 7.** We could replace *ELim* by $E_2Lim$ in the statements of Theorems 4 and 5.

This is equivalent to prove the following, and observe from the proof that we can replace in above statement “$g(\mathbf{m}, n)$ going to 0” by “decreasing to 0”, and last condition by $\|g(\mathbf{m}, p(n))\| \le 2^{-n}$.

**Theorem 8.** $\mathbf{F}: \mathbb{N}^d \to \mathbb{R}^{d'}$ is computable in polynomial time iff there exists $\mathbf{f}: \mathbb{N}^{d+1} \to \mathbb{Q}^{d'}$, with $\mathbf{f}(\mathbf{m}, n)$ computable in polynomial time with respect to the value of $n$, and $g: \mathbb{N}^{d+1} \to \mathbb{Q}$ such that

$$ - \|\mathbf{f}(\mathbf{m}, n) - \mathbf{F}(\mathbf{m})\| \le g(\mathbf{m}, n) $$

$$ - 0 \le g(\mathbf{m}, n) \text{ and } g(\mathbf{m}, n) \text{ converging to } 0 \text{ when } n \text{ goes to } +\infty, $$

$$ - \text{with a uniform polynomial modulus of convergence } p(n). $$

From the proofs we also get a normal form theorem. In particular,

**Theorem 9 (Normal form theorem).** Any function $f: \mathbb{N}^d \to \mathbb{R}^{d'}$ can be obtained from the class $\overline{\mathbb{L}\mathbb{D}\mathbb{L}}^\bullet$ using only one schema *ELim* (or $E_2Lim$).

# 9 Conclusion and future work

In this article, we characterized the set of functions from the integer to the reals. As we already said, our aim in a future work is to characterize $\mathbf{FPTIME} \cap \mathbb{R}^\mathbb{R}$ and not only $\mathbf{FPTIME} \cap \mathbb{R}^\mathbb{N}$. This is clearly a harder task. In particular, a natural approach would be to consider some function *Encode* from $\mathbb{R}$ to $\mathcal{I}$. Unfortunately, such a function *decode* is necessarily discontinuous, and is hence not-computable,
and cannot be in the class. The approach of *mixing* of [23] might provide a solution, even if the constructions there, based on (classical) continuous ODEs use deeply some closure properties of these functions that are not true for discrete ODEs.

# 10 Thanks

We would like to thank warmly Arnaud Durand, for several very helpful discussions, and comments about this work as well as very relevant questions and suggestions who influenced strongly the way some of our results are formulated.

# References

1. Arnold, V.I.: Ordinary Differential Equations. MIT Press (1978)

2. Birkhoff, G., Rota, G.C.: Ordinary Differential Equations. 4th edn. John Wiley & Sons (1989)

3. Coddington, E.A., Levinson, N.: Theory of Ordinary Differential Equations. McGraw-Hill (1955)

4. Bournez, O., Pouly, A.: A survey on analog models of computation. In Brattka, V., Hertling, P., eds.: Handbook of Computability and Complexity in Analysis. Springer (2020)

5. Bournez, O., Durand, A.: Recursion schemes, discrete differential equations and characterization of polynomial time computation. In Rossmanith, P., Heggernes, P., Katoen, J., eds.: 44th Int Symposium on Mathematical Foundations of Computer Science, MFCS. Volume 138 of LIPIcs., Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019) 23:1–23:14

6. Bournez, O., Durand, A.: Recursion schemes, discrete differential equations and characterization of polynomial time computation. Technical report (October 2018) Submitted. A preliminary version coauthored with Sabrina Ouazzani is available on https://arxiv.org/abs/1810.02241.

7. Gelfond, A.: Calculus of finite differences. (1971)

8. Graham, R.L., Knuth, D.E., Patashnik, O., Liu, S.: Concrete mathematics: a foundation for computer science. Computers in Physics 3(5) (1989) 106–107

9. Gleich, D.: Finite calculus: A tutorial for solving nasty sums. Stanford University (2005)

10. Izadi, F., Aliev, N., Bagirov, G.: Discrete Calculus by Analogy. Bentham Science Publishers (2009)

11. Lau, G. Course notes for the course "Discrete calculus", available on http://gustavolau.com

12. Cobham, A.: The intrinsic computational difficulty of functions. In Bar-Hillel, Y., ed.: Proceedings of the International Conference on Logic, Methodology, and Philosophy of Science. North-Holland, Amsterdam (1962) 24–30

13. Bellantoni, S., Cook, S.: A new recursion-theoretic characterization of the poly-time functions. Computational Complexity 2 (1992) 97–110

14. Leivant, D.: Intrinsic theories and computational complexity. In: LCC'94. Number 960 in Lecture Notes in Computer Science (1995) 177–194

15. Weihrauch, K.: Computable Analysis: an Introduction. Springer (2000)
16. Leivant, D., Marion, J.Y.: Lambda calculus characterizations of Poly-Time. Fundamenta Informatica **19**(1,2) (1993) 167,184

17. Leivant, D.: Predicative recurrence and computational complexity I: Word recurrence and poly-time. In Clote, P., Remmel, J., eds.: Feasible Mathematics II. Birkhäuser (1994) 320–343

18. Leivant, D., Marion, J.Y.: Ramified recurrence and computational complexity II: substitution and poly-space. In Pacholski, L., Tiuryn, J., eds.: Computer Science Logic, 8th Workshop, CSL’94. Volume 933 of Lecture Notes in Computer Science., Kazimierz, Poland, Springer (1995) 369–380

19. Clote, P.: Computational models and function algebras. In Griffor, E.R., ed.: Handbook of Computability Theory. North-Holland, Amsterdam (1998) 589–681

20. Clote, P., Kranakis, E.: Boolean functions and computation models. Springer Science & Business Media (2013)

21. Siegelmann, H.T., Sontag, E.D.: On the computational power of neural nets. Journal of Computer and System Sciences **50**(1) (February 1995) 132–150

22. Siegelmann, H.T.: Neural Networks and Analog Computation - Beyond the Turing Limit. Birkauser (1999)

23. Bournez, O., Campagnolo, M.L., Graça, D., S. Hainry, E.: Polynomial differential equations compute all real computable functions on computable compact intervals. Journal of Complexity **23**(3) (2007) 317–335

24. Brattka, V.: Recursive characterization of computable real-valued functions and relations. Theoretical Computer Science **162**(1) (1996) 45–77

25. Ng, K.M., R Tavana, N., Yang, Y.: A recursion theoretic foundation of computation over real numbers. Journal of Logic and Computation **31**(7) (2021) 1660–1689

26. Ko, K.I.: Complexity Theory of Real Functions. Progress in Theoretical Computer Science. Birkhäuser, Boston (1991)

27. Brattka, V., Hertling, P., Weihrauch, K.: A tutorial on computable analysis. In: New computational paradigms. Springer (2008) 425–491