Open AccessArticle

On Productiveness and Complexity in Computable Analysis Through Rice-Style Theorems for Real Functions

Jingnan Xie

^1,*

Harry B. Hunt III

² and

Richard E. Stearns

Computer Science, Millersville University of Pennsylvania, 40 Dilworth Rd, Millersville, PA 17551, USA

Computer Science, University at Albany, State University of New York, Albany, NY 12222, USA

Author to whom correspondence should be addressed.

Mathematics 2024, 12(20), 3248; https://doi.org/10.3390/math12203248

Submission received: 7 September 2024 / Revised: 6 October 2024 / Accepted: 15 October 2024 / Published: 17 October 2024

(This article belongs to the Section Mathematics and Computer Science)

Download Versions Notes

Abstract

This paper investigates the complexity of real functions through proof techniques inspired by formal language theory. Productiveness, which is a stronger form of non-recursive enumerability, is employed to analyze the complexity of various problems related to real functions. Our work provides a deep reexamination of Hilbert’s tenth problem and the equivalence to the identically 0 function problem, extending the undecidability results of these problems into the realm of productiveness. Additionally, we study the complexity of the equivalence to the identically 0 function problem over different domains. We then construct highly efficient many-one reductions to establish Rice-style theorems for the study of real functions. Specifically, we show that many predicates, including those related to continuity, differentiability, uniform continuity, right and left differentiability, semi-differentiability, and continuous differentiability, are as hard as the equivalence to the identically 0 function problem. Due to their high efficiency, these reductions preserve nearly any level of complexity, allowing us to address both complexity and productiveness results simultaneously. By demonstrating these results, which highlight a more nuanced and potentially more intriguing aspect of real function theory, we provide new insights into how various properties of real functions can be analyzed.

Keywords:

computable analysis; undecidability; productiveness; computational complexity; functions of real variables; Hilbert’s tenth problem; analog of Rice’s theorem

MSC:

03D05; 03D10; 03D15; 03D20; 03D25; 03D35; 03D75; 03D78; 03D80; 26A03; 26A09; 26A15; 26A24

1. Introduction

Computable analysis is a modern theory of computability and complexity in analysis that arose out of the seminal work of Turing in the 1930s. This was motivated by questions such as “which real numbers and real number functions are computable, and which mathematical tasks in analysis can be solved by algorithmic means?” Some recent research on computable analysis can be found in [1,2]. In this paper, we extend some of the concepts and proof techniques in the theory of formal languages to study the undecidability and complexity of problems in the theory of functions of real variables.

In the theory of formal languages, Rice’s theorem establishes that any non-trivial property of the languages recognized by Turing machines is undecidable. Several authors have investigated the existence and applicability of analogs of Rice’s theorem for different classes of languages. For example, in [3,4,5,6,7,8], sufficient conditions are given for a language predicate to be as hard as the language predicate “

= {0, 1}^{*}

” or “

= \emptyset

”. It is well known that for a given alphabet

Σ

, the set of formal languages over

Σ

forms a semiring, with ∅ being the additive identity. In rings, the corresponding element of ∅ is 0. Thus, an analog of the predicate “

= \emptyset

” is the equivalence to the identically 0 function problem. This inspired us to establish similar proof techniques in the theory of real functions, leading to the development of Rice-style theorems for the study of real functions, utilizing the equivalence to the identically 0 function problem.

In this paper, we employ a stronger form of non-recursive enumerability called productiveness. A productive set S is not recursively enumerable. Furthermore, for any effective axiomatic system F, there is an effective procedure to construct an element that is in S, but not provable in F (see Section 2 for the importance and precise definition of productiveness). We then study the productiveness of the equivalence to the identically 0 function problem by investigating and extending the previous work in [9,10], as well as the undecidability result of Hilbert’s tenth problem (HTP). To the best of our knowledge, HTP is the primary method used to show undecidable results for real fields (for example, see [11]). We show that HTP and the equivalence to the identically 0 function problem studied in [9,10] are not only undecidable but also productive; hence, they are not provable. Furthermore, for any sound proof procedure P, one can effectively construct an element that is true, but not provable in P. The productiveness of the equivalence to the identically 0 function problem over different domains is also established.

Moreover, we use highly efficient many-one reductions to show that many problems in the theory of functions of real variables are as hard as the equivalence to the identically 0 function problem. For example, we show that problems such as “is an arbitrary function identically equal to a fixed function?”, “is an arbitrary function differentiable?”, and “is an arbitrary function continuous?” are as hard as the equivalence to the identically 0 function problem. Intuitively, these reductions preserve many levels of complexity. Although, to date, our results for real fields are either productiveness results or relative complexity results, the efficiency of our reductions shows that these relative complexity results have many potential applications.

This paper is organized as follows.

In Section 2, we review the definitions and theorems related to HTP. We also provide a deeper analysis of the undecidability proof of HTP and show that the set of false instances of HTP is productive. To make the paper more self-contained, the definition and importance of productiveness are discussed. Several preliminary definitions and notations are also explained.

In Section 3, the productiveness of the equivalence to the identically 0 function problem across different sets of functions and domains is investigated.

In Section 4, we show two relative complexity/productiveness results via highly efficient reductions from the equivalence to the identically 0 function problem. Due to the efficiency of these reductions, these Rice-style theorems can prove undecidability/productiveness results and hardness results simultaneously.

2. Definitions and Preliminary Results

In this section, we first explain several preliminary definitions and notations. The concept and significance of productiveness are also discussed. The reader is referred to [12] for all unexplained notations and terminologies in language theory. Next, we review the definitions and theorems related to HTP. Through a detailed analysis of the undecidability proof of HTP, we demonstrate that the set of false instances of HTP is productive.

Definition 1.

Let A and B be two formal languages over the alphabets Σ and Γ, respectively. A many-one reduction from A to B is a total recursive function

f : Σ^{*} \to Γ^{*}

such that

\forall w \in Σ^{*}

w \in A

, if and only if

f (w) \in B

. If such a function f exists, we say that A is many-one reducible to B, and write

A ⩽_{m} B

; if this reduction is polynomial-time bounded, we write

A ⩽_{p t i m e} B

We use

N

to denote the set of natural numbers and ∅ to denote the empty set. We utilize various standard notations related to real functions, such as

s i n ()

for the sine function and

(\partial / \partial x_{i})

for partial derivatives. For a comprehensive overview of these conventions, please refer to [13].

Productive sets and their properties are a standard topic in mathematical logic/recursion theory textbooks such as [14,15]. Productiveness is a recursion-theoretic abstraction of what causes Gödel’s first incompleteness theorem to hold. The next definition recalls the definition of a productive set on

N

, as developed in [14].

Definition 2.

Let W be an effective Gödel numbering of the recursively enumerable sets. A set A of natural numbers is called productive if there exists a total recursive function f so that for all

i \in N

, if

W_{i} \subseteq A

, then

f (i) \in A - W_{i}

. The function f is called the productive function for A.

From this definition, we can see that no productive set is recursively enumerable. It is well known that the set of all provable sentences in an effective axiomatic system is always a recursively enumerable set. So, for any effective axiomatic system F, if a set A of Gödel numbers of true sentences in F is productive, then there is at least one element in A that is true but cannot be proven in F. Moreover, there is an effective procedure to produce such an element.

Let W be an effective Gödel numbering of the recursively enumerable sets. K denotes the set

{i \in N ∣ i \in W_{i}}

\bar{K}

denotes the set

{i \in N ∣ i \notin W_{i}}

. Two well-known facts of productive sets (see [14]) that are necessary for the research developed here are as follows:

Proposition 1.

1.: $\bar{K}$ is productive.
2.: For all $A \subseteq N$ , A is productive if and only if $\bar{K} ⩽_{m} A$ .

The following proposition is proven in [5] and is used to prove productiveness results. It also shows in which way the productiveness is stronger than non-recursive enumerability: i.e., every productive set A has an infinite recursively enumerable subset, and for any sound proof procedure P, one can effectively construct an element that is in A, but not provable in P.

Proposition 2.

Let

A \subseteq Σ^{*}

B \subseteq Δ^{*}

, and

A ⩽_{m} B

. Then, the following hold:

1.: If A is productive, then so is B.
2.: If A is productive, then there exists a total recursive function $Ψ : Σ^{*} \to Σ^{*}$ , called a productive function for A, such that for all $x \in Σ^{*}$ ,

$\begin{array}{l} L (M_{x}) \subseteq A \Rightarrow Ψ (x) \in A - L (M_{x}), where {M_{x} ∣ x \in Σ^{*}} is some G \ddot{o} del \\ numbering of Turing machines over alphabet Σ . \end{array}$
3.: If A is productive, then A is not recursively enumerable (RE). However, A does have an infinite RE subset.

To make the definitions of this paper clear, we need some discussion about expressions of functions.

Let R be a set of expressions representing functions. In this chapter, all the expressions are assumed to represent real, single-valued elementary functions of one or more real variables over some domain D. If

F \in R

, then

F (x_{1}, \dots, x_{k})

for

k \geq 1

is the function represented by F. It is supposed that, given

A, B \in R

, there is an efficient procedure for finding expressions in R to represent the functions

\begin{matrix} A (x_{1}, \dots, x_{m}) + B (x_{1}, \dots, x_{n}) \\ A (x_{1}, \dots, x_{m}) - B (x_{1}, \dots, x_{n}) \\ A (x_{1}, \dots, x_{m}) * B (x_{1}, \dots, x_{n}) \\ A (\dots, B (x_{1}, \dots, x_{n}), \dots) . \end{matrix}

A (x_{1}, \dots, x_{k}) \equiv B (x_{1}, \dots, x_{k})

means that

A (x_{1}, \dots, x_{k})

and

B (x_{1}, \dots, x_{k})

are defined over the same domain and equal wherever they are defined.

Definition 3.

Let R be a set of expressions representing real functions of one (or multiple) real variable(s). The equivalence to the identically 0 function problem (denoted by

{\equiv 0 |}_{R, D})

is the problem of deciding, given

F \in R

, over some domain D, whether

F (x_{1}, x_{2}, \dots, x_{k}) \equiv 0

for all

x_{1}, x_{2}, \dots, x_{k} \in D

(k \geq 1)

We then briefly introduce HTP and review the standard proof of its undecidability as presented in [11,16]. The definitions and notations used here are mainly from the book [11]. A deeper analysis of this undecidability proof reveals that the set of false instances of HTP is productive. This finding is stronger than the undecidability result since it demonstrates that HTP is not provable. Moreover, for any sound proof procedure P, one can effectively construct a counterexample that is not provable by P. This is potentially more interesting in the theory of functions of real variables.

Definition 4.

A Diophantine equation is an equation of the form

D (x_{1}, \dots, x_{m}) = 0,

where D is a polynomial with integer coefficients. A family of Diophantine equations is defined by an equation of the form

D (a_{1}, \dots, a_{n}, x_{1}, \dots, x_{m}) = 0,

where D is a polynomial with integer coefficients, the variables of which are split into two groups:

1.: The parameters $a_{1}, \dots, a_{n}$ ;
2.: The unknowns $x_{1}, \dots, x_{m}$ .

We can consider the set

M

of all n-tuples

(a_{1}, \dots, a_{n})

for which the above parametric equation has a solution in integers, that is,

(a_{1}, \dots, a_{n}) \in M ⟺ \exists x_{1}, \dots, x_{m} \in N^{m} [D (a_{1}, \dots, a_{n}, x_{1}, \dots, x_{m}) = 0] .

An equivalence of this form is called a Diophantine representation of the set

M

Hilbert’s tenth problem is to determine whether a given Diophantine equation has a solution in integers. The following theorem proved by Yuri Matiyasevich [16] shows that HTP is undecidable.

Theorem 1.

(Matiyasevich’s Theorem) Every recursively enumerable set W of n-tuples of nonnegative integers has a Diophantine representation; that is, for any recursively enumerable set W,

(a_{1}, \dots, a_{n}) \in W ⟺ \exists x_{1}, \dots, x_{m} \in N^{m} [D (a_{1}, \dots, a_{n}, x_{1}, \dots, x_{m}) = 0] .

for some polynomial D with integer coefficients.

We investigate the proof of Theorem 1 and show a stronger form of this theorem that implies the set of false instances in HTP is productive.

Corollary 1.

\bar{K} ⩽_{m} {D | D (x_{1}, \dots, x_{n})

is a Diophantine equation, and

D (x_{1}, \dots, x_{n})

has no solution in integers}.

Proof.

Recall the definition of the set

K

. Let W be an effective Gödel numbering of the recursively enumerable sets.

K = {i \in N | i \in W_{i}}

. According to Theorem 1, we know that

i \in W_{i}

if and only if there exists a polynomial D with integer coefficients such that

D (i, x_{1}, \dots, x_{m})

has a solution in integers. □

One related result is about the problem of determining whether a given Diophantine equation has a solution in natural numbers.

Corollary 2.

\bar{K} ⩽_{m} {D | D (x_{1}, \dots, x_{n})

is a Diophantine equation, and

D (x_{1}, \dots, x_{n})

has no solution in natural numbers}.

Proof.

The problem of determining whether a given Diophantine equation has a solution in integers is many-one equivalent to the problem of determining whether it has a solution in natural numbers. The proof that these two problems are many-one equivalent can be seen in [17]. The rest of the proof is by Corollary 1 and the transitivity of many-one reduction. □

The following corollary is presented in [17] and is directly from Corollary 1 and the properties of productiveness. It demonstrates the importance of productiveness.

Corollary 3.

There is a particular one-parameter Diophantine equation

U_{0} (a, x_{1}, \dots, x_{m}) = 0

and an algorithm that, for a given algorithm

A

, produces a number

a_{A}

(counterexample) such that the algorithm

A

fails to give the correct answer to the question of whether equation

U_{0} (a_{A}, x_{1}, \dots, x_{m}) = 0

has a solution in integers.

3. The Equivalence to the Identically 0 Function Problem

In this section, we present a deep analysis of the proofs in [9,10] and establish a stronger theorem to show that the problem “

{\equiv 0 |}_{R, (- \infty, + \infty)}

” is productive for a particular set of expressions representing real functions over the domain

(- \infty, + \infty)

. This productiveness result is then extended to different domains, such as

[0, + \infty)

(- \infty, 0]

(a, b)

for any real numbers

a < b

, etc.

Theorem 2.

Let R be the set of expressions generated by

1.: The rational numbers and the real number π;
2.: The variable x;
3.: The operations of addition, multiplication, and composition;
4.: The sine and absolute value functions.

Then,

\bar{K} ⩽_{m} {F \in R | F (x) \equiv 0

over

(- \infty, + \infty)}

. Hence, the problem “

{\equiv 0 |}_{R, (- \infty, + \infty)}

” is productive.

Proof.

The constructions in this proof are mainly from [9]. For any polynomial

P (x_{1}, \dots, x_{n})

with integer coefficients, let

K_{i} (x_{1}, \dots, x_{n})

be the dominating function for

(\partial / \partial x_{i}) P (x_{1}, \dots, x_{n})

. This means

K_{i} (x_{1}, \dots, x_{n}) > 1

for all real

x_{1}, \dots, x_{n}

and

K_{i} (x_{1}, \dots, x_{n}) > (\partial / \partial x_{i}) P (x_{1} + Δ_{1}, \dots, x_{n} + Δ_{n})

for all real

x_{i}

and all real

Δ_{i}

satisfying

| Δ_{i} | < 1

for

1 \leq i \leq n

. Observe that the expressions P and

K_{i}

are in R. Then, we can effectively construct an expression

F \in R

representing

F (x_{1}, \dots, x_{n}) = {(n + 1)}^{2} [P^{2} (x_{1}, \dots, x_{n}) + \sum_{i = 1}^{n} s i n^{2} (π x_{i}) K_{i}^{2} (x_{1}, \dots, x_{n})] - 1 .

If there exist n natural numbers

a_{1}, \dots, a_{n}

such that

P (a_{1}, \dots, a_{n}) = 0

, then

F (a_{1}, \dots, a_{n}) = - 1 < 0

. If there exist n nonnegative real numbers

b_{1}, \dots, b_{n}

such that

F (b_{1}, \dots, b_{n}) < 0

, let

a_{i}

be the smallest integer such that

| a_{i} - b_{i} | \leq 1 / 2

. Observe that

a_{1}, \dots, a_{n}

are natural numbers. Then,

P^{2} (b_{1}, \dots, b_{n}) + \sum_{i = 1}^{n} s i n^{2} (π b_{i}) K_{i}^{2} (b_{1}, \dots, b_{n}) < 1 / {(n + 1)}^{2} .

Hence,

P^{2} (b_{1}, \dots, b_{n}) < 1 / {(n + 1)}^{2} < 1 / (n + 1)

and

| s i n (π b_{i}) | K_{i} (b_{1}, \dots, b_{n}) < 1 / (n + 1)

for all

1 \leq i \leq n

. By the n-dimensional mean value theorem,

P^{2} (a_{1}, \dots, a_{n}) \leq P^{2} (b_{1}, \dots, b_{n}) + \sum_{i = 1}^{n} | a_{i} - b_{i} | (\partial / \partial x_{i}) P^{2} (c_{1}, \dots, c_{m})

where

c_{i}

is between

a_{i}

and

b_{i}

. From the definition of

K_{i}

, we have

P^{2} (a_{1}, \dots, a_{n}) < P^{2} (b_{1}, \dots, b_{n}) + \sum_{i = 1}^{n} | a_{i} - b_{i} | K_{i} (b_{1}, \dots, b_{n}) .

Since

| a_{i} - b_{i} | \leq 1 / 2

, we have

| a_{i} - b_{i} | \leq | s i n (π b_{i}) |

. Hence,

P^{2} (a_{1}, \dots, a_{n}) < P^{2} (b_{1}, \dots, b_{n}) + \sum_{i = 1}^{n} | s i n (π b_{i}) | K_{i} (b_{1}, \dots, b_{n}) .

We know

P^{2} (b_{1}, \dots, b_{n}) < 1 / (n + 1)

and

| s i n (π b_{i}) | K_{i} (b_{1}, \dots, b_{n}) < 1 / (n + 1)

. So,

P^{2} (a_{1}, \dots, a_{n}) < 1 \Rightarrow P (a_{1}, \dots, a_{n}) = 0 .

So, there exist n natural numbers

a_{1}, \dots, a_{n}

such that

P (a_{1}, \dots, a_{n}) = 0

. By Corollary 2, we have

\bar{K} ⩽_{m} {F \in R | F (x_{1}, \dots, x_{n}) \geq 0 over [0, + \infty)} .

(1)

For any function

F (x_{1}, \dots, x_{n})

represented by an expression in R, we can effectively construct an expression

G_{1} \in R

, such that

G_{1} (x_{1}, \dots, x_{n}) = F (x_{1}^{2}, \dots, x_{n}^{2}) .

If there exist n nonnegative real numbers

b_{1}, \dots, b_{n}

such that

F (b_{1}, \dots, b_{n}) < 0

, then there exist n real numbers

\sqrt{b_{1}}, \dots, \sqrt{b_{n}}

such that

G_{1} (\sqrt{b_{1}}, \dots, \sqrt{b_{n}}) < 0

. On the other hand, if there are n real numbers

b_{1}, \dots, b_{n}

such that

G_{1} (b_{1}, \dots, b_{n}) < 0

, clearly, there exist n nonnegative real numbers

b_{1}^{2}, \dots, b_{n}^{2}

such that

F (b_{1}^{2}, \dots, b_{n}^{2}) < 0

. So, we have

{F \in R | F (x_{1}, \dots, x_{n}) \geq 0 over [0, + \infty)} ⩽_{m} {F \in R | F (x_{1}, \dots, x_{n}) \geq 0 over (- \infty, + \infty)} .

(2)

For any function

F (x_{1}, \dots, x_{n})

represented by an expression in R, we can effectively construct an expression

G_{2} \in R

such that

G_{2} (x) = F (h (x), h (g (x)), \dots, h (g (\dots (g (x)) \dots)))

where

h (x) = x s i n (x)

and

g (x) = x s i n (x^{3})

. Because of the fact proved in [10] that, for any real numbers

a_{1}, \dots, a_{n}

and any

0 < ϵ < 1

, there exists

b > 0

such that

| h (b) - a_{1} | < ϵ, | h (g (b)) - a_{2} | < ϵ, \dots, | h (g (\dots (g (b)) \dots)) - a_{n} | < ϵ

we know there exists a real number b such that

G_{2} (b) < 0

if and only if there exist n real numbers

a_{1}, \dots, a_{n}

such that

F (a_{1}, \dots, a_{n}) < 0

. So, we have

{F \in R | F (x_{1}, \dots, x_{n}) \geq 0 over (- \infty, + \infty)} ⩽_{m} {F \in R | F (x) \geq 0 over (- \infty, + \infty)} .

(3)

For any function

F (x)

represented by an expression in R, we can effectively construct an expression

G_{3} \in R

such that

G_{3} (x) = | F (x) | - F (x) .

F (x) \geq 0

for all

x \in (- \infty, + \infty)

, then

G_{3} (x) \equiv 0

over

(- \infty, + \infty)

. Otherwise, there exists a real number a such that

F (a) < 0

. So,

G_{3} (a) = - 2 F (a) \neq 0

. Then, we have

{F \in R | F (x) \geq 0 over (- \infty, + \infty)} ⩽_{m} {F \in R | F (x) \equiv 0 over (- \infty, + \infty)} .

(4)

By the transitivity of many-one reductions, we have

\bar{K} ⩽_{m} {F \in R | F (x) \equiv 0 over (- \infty, + \infty)} .

□

Since investigating the complexity/productiveness of the problem “

{\equiv 0 |}_{R, D}

” is central to our research, it is desirable to have as much information as possible about this problem. One natural direction is to investigate this problem over different domains. From the proof of Theorem 2, we have the following corollary directly.

Corollary 4.

Let R be the same set defined in Theorem 2. Then,

$\bar{K} ⩽_{m} {F \in R | F (x) \equiv 0$ over $[0, + \infty)}$ .
$\bar{K} ⩽_{m} {F \in R | F (x) \equiv 0$ over $(- \infty, 0]}$ .

Proof.

The proof follows from the first reduction (reduction (1)) in the proof of Theorem 2. Notice that the set

{D | D (x_{1}, \dots, x_{n})

is a Diophantine equation and

D (x_{1}, \dots, x_{n})

has no nonpositive solution} is also productive. The proof is simple: For any Diophantine equation

D_{1} (x_{1}, \dots, x_{n})

, we can effectively construct another Diophantine equation

D_{2} (x_{1}, \dots, x_{n}) = D_{1} (- x_{1}, \dots, - x_{n})

. Clearly,

D_{1}

has a solution in natural numbers if and only if

D_{2}

has a solution in nonpositive numbers. Applying this result to the first reduction in the proof of Theorem 2, we can obtain

\bar{K} ⩽_{m} {F \in R | F (x_{1}, \dots, x_{n}) \geq 0 over (- \infty, 0]} .

The remainder of the proof is just to skip the second reduction (reduction (2)) in the proof of Theorem 2 and go through reductions (3) and (4). □

In the theory of functions of real variables, the domains of many problems are defined to be an open (or closed) interval

(a, b)

(or

[a, b]

), where a and b represent real numbers that define the boundaries of the interval. In order to make our general methods applicable to problems with these domains, we investigate the productiveness of the problems “

{\equiv 0 |}_{R, (a, b)}

”, “

{\equiv 0 |}_{R, (a, b]}

”, “

{\equiv 0 |}_{R, [a, b)}

”, and “

{\equiv 0 |}_{R, [a, b]}

”.

Theorem 3.

Let

R_{2}

be the set of expressions generated by

1.: The rational numbers and the real number π;
2.: The variable x;
3.: The operations of addition, multiplication, division, and composition;
4.: The sine and absolute value functions.

Then, the following hold:

$\bar{K} ⩽_{m} {F \in R_{2} | F (x) \equiv 0$ over $(a, b)$ , where $a, b$ are real numbers and $a < b}$ ;
$\bar{K} ⩽_{m} {F \in R_{2} | F (x) \equiv 0$ over $(a, b]$ , where $a, b$ are real numbers and $a < b}$ ;
$\bar{K} ⩽_{m} {F \in R_{2} | F (x) \equiv 0$ over $[a, b)$ , where $a, b$ are real numbers and $a < b}$ .

Proof.

Observe that the set R defined in Theorem 2 is a proper subset of

R_{2}

and that

R_{2}

allows the operation of division. For any function

F (x)

represented by an expression in R, for any two real numbers

a, b

with

a < b

, we can effectively construct an expression

G \in R_{2}

such that

G (x) = F (\frac{1}{a - x} + \frac{1}{b - x}) .

It is easy to see

lim_{x \to a^{+}} (\frac{1}{a - x} + \frac{1}{b - x}) = - \infty

and

lim_{x \to b^{-}} (\frac{1}{a - x} + \frac{1}{b - x}) = + \infty

. So, for any real number t, there exists a real number

h \in (a, b)

such that

F (t) = G (h)

. Hence,

F (x) \equiv 0

for all

x \in (- \infty, + \infty)

if and only if

G (x) \equiv 0

over

(a, b)

The proofs for the other two results are similar. Consider the following construction:

G (x) = F (\frac{1}{b - x} * (x - a)) .

For any real number

t \in [0, + \infty)

, there exists a real number

h \in [a, b)

such that

F (t) = G (h)

. Hence,

F (x) \equiv 0

for all

x \in [0, + \infty)

if and only if

G (x) \equiv 0

over

[a, b)

Consider the following construction:

G (x) = F (\frac{1}{a - x} * (b - x)) .

For any real number

t \in (- \infty, 0]

, there exists a real number

h \in (a, b]

such that

F (t) = G (h)

. Hence,

F (x) \equiv 0

for all

x \in (- \infty, 0]

if and only if

G (x) \equiv 0

over

(a, b]

. □

If we study the problem “

{\equiv 0 |}_{R, D}

” in the extended real number system (see [18,19] for more information), we can obtain a stronger result. The extended real number system (denoted by

\bar{R}

) is the real number system with two extra elements. The two extra elements are denoted by

+ \infty

and

- \infty

(read as positive infinity and negative infinity, respectively). The extended real number system is very useful in describing various limiting behaviors in calculus and mathematical analysis, especially in the theory of measure and integration. The algebraic operations for

+ \infty

and

- \infty

are defined as follows:

$a + (+ \infty) = (+ \infty + a) = + \infty$ if $a \neq - \infty$ ;
$a + (- \infty) = (- \infty + a) = - \infty$ if $a \neq + \infty$ ;
$a \cdot (\pm \infty) = \pm \infty \cdot a = \pm \infty$ if $a \in (0, + \infty]$ ;
$a \cdot (\pm \infty) = \pm \infty \cdot a = \mp \infty$ if $a \in [- \infty, 0)$ ;
$\frac{a}{\pm \infty} = 0$ if $a \in (- \infty, + \infty)$ ;
$- \infty < x < + \infty$ for all $x \in (- \infty, + \infty)$ .

The expressions

+ \infty + (- \infty)

- \infty + (+ \infty)

, and

\frac{\pm \infty}{\pm \infty}

are left undefined. In this paper, in order to make it applicable to Lebesgue measure theory, we shall agree that

$0 \cdot (\pm \infty) = 0$ ;
For any continuous function $f (x)$ , if $x \to a \Rightarrow f (x) \to 0^{+}$ , then $\frac{1}{f (a)} = + \infty$ ; if $x \to a \Rightarrow f (x) \to 0^{-}$ , then $\frac{1}{f (a)} = - \infty$ .

Let us consider functions over extended real numbers. The following proposition follows directly from Theorem 2.

Proposition 3.

Let R be the set of expressions generated by

1.: The rational numbers and the real number π;
2.: The variable x;
3.: The operations of addition, multiplication, and composition;
4.: The sine and absolute value functions.

Then,

\bar{K} ⩽_{m} {F \in R | F (x) \equiv 0

over

[- \infty, + \infty]}

Proof.

The proof is the same as that of Theorem 2. □

Proposition 3 enables us to study the complexity/productiveness of the problem “

{\equiv 0 |}_{R, [a, b]}

” in the extended real number system. The following theorem shows that, in the extended real system, the problem “

{\equiv 0 |}_{R, [a, b]}

” for a particular set of elementary functions over any closed and bounded interval

[a, b]

with

a < b

is productive.

Theorem 4.

Let

R_{2}

be the set of expressions generated by

1.: The rational numbers and the real number π;
2.: The variable x;
3.: The operations of addition, multiplication, division, and composition;
4.: The sine and absolute value functions.

Then,

\bar{K} ⩽_{m} {F \in R_{2} | F (x) \equiv 0

over

[a, b]

, where

a, b

are real numbers and

a < b}

Proof.

Observe that the set R defined in Proposition 3 is a proper subset of

R_{2}

and that

R_{2}

allows the operation of division. For any continuous function

A (x)

represented by an expression in R, we can effectively construct an expression

F \in R_{2}

such that

F (x) = \{\begin{matrix} \frac{A^{2} (x)}{1 + A^{2} (x)} \cdot \frac{1}{x^{2}}, & if | x | > 1 \\ \frac{A^{2} (x)}{1 + A^{2} (x)}, & if - 1 \leq x \leq 1 \end{matrix}

It is obvious that

0 \leq \frac{A^{2} (x)}{1 + A^{2} (x)} < 1

. So, we have the following:

$lim_{x \to - \infty} F (x) = 0$ and $lim_{x \to + \infty} F (x) = 0$ , since $lim_{x \to - \infty} \frac{1}{x^{2}} = 0$ and $lim_{x \to + \infty} \frac{1}{x^{2}} = 0$ ;
$lim_{x \to - 1^{-}} F (x) = \frac{A^{2} (x)}{1 + A^{2} (x)}$ and $lim_{x \to - 1^{+}} F (x) = \frac{A^{2} (x)}{1 + A^{2} (x)}$ , since $lim_{x \to - 1^{-}} \frac{1}{x^{2}} = 1$ ;
$lim_{x \to 1^{-}} F (x) = \frac{A^{2} (x)}{1 + A^{2} (x)}$ and $lim_{x \to 1^{+}} F (x) = \frac{A^{2} (x)}{1 + A^{2} (x)}$ , since $lim_{x \to 1^{+}} \frac{1}{x^{2}} = 1$ .

Consider the extended real number system

[- \infty, + \infty]

F (x)

is everywhere defined and continuous over

[- \infty, + \infty]

and

F (- \infty) = F (+ \infty) = 0

. For any real numbers

a, b

with

a < b

, let

g (x) = \frac{1}{a - x} + \frac{1}{b - x}

. Observe that there exists an expression in

R_{2}

to represent

F (g (x))

lim_{x \to a^{+}} g (x) = - \infty

and

lim_{x \to b^{-}} g (x) = + \infty

. Hence, over the interval

[a, b]

g (a) = - \infty

and

g (b) = + \infty

. Hence, for any extended real number

t \in [- \infty, + \infty]

, there exists a real number

h \in [a, b]

such that

g (h) = t

. Hence,

F (g (x)) \equiv 0

over

[a, b]

if and only if

F (x) \equiv 0

over

[- \infty, + \infty]

. By the definition of

F (x)

, we know

F (x) \equiv 0

over

[- \infty, + \infty]

if and only if

A (x) \equiv 0

over

[- \infty, + \infty]

. □

4. Rice-Style Theorems for Real Fields

In this section, we present several general complexity/productiveness results in the theory of functions of real variables. Through these results, we illustrate one useful proof technique and show the complexity-theoretic parallels between the theories of formal languages (Rice’s theorem) and of functions of real variables. In the theory of formal languages, researchers have provided a lot of discussion and applications on testing equivalence to any fixed language. Here, we consider a similar problem: testing equivalence to any fixed real function. Since the set of all real functions forms a ring, the problem of testing equivalence to any fixed real function is many-one equivalent to the equivalence to the identically 0 function problem.

Theorem 5.

Let R be the set of expressions generated by

1.: The variable x;
2.: The operations of addition and subtraction.

For any fixed real function

F_{0} (x)

represented by an expression in R,

{F \in R | F (x) \equiv 0 over D} \equiv_{p t i m e} {F \in R | F (x) \equiv F_{0} (x) over D} .

Proof.

For any function

F (x)

, where

F \in R

, we can efficiently construct an expression

G \in R

such that

G (x) = F (x) + F_{0} (x)

. Clearly,

G (x) = F_{0} (x)

over domain D if and only if

F (x) \equiv 0

over D. On the other hand, we can construct a function

G (x) = F_{0} (x) - F (x)

, and then

G (x) \equiv 0

over D if and only if

F (x) = F_{0} (x)

over D. □

The use of dichotomized reductions to show that a collection of predicates is hard simultaneously has been explored in the theory of formal languages. For example, in [6], we construct a language that is either

{0, 1}^{*}

or a language that is not a multi-pattern language. Then, the single reduction implies the following simultaneously: for any subset

Γ

of multi-pattern languages, if

{0, 1}^{*} \in Γ

, then the predicate “

\in Γ

” is hard. The same proof technique also works in real fields. For example, using a dichotomized reduction, we have the following Rice-style theorem.

Theorem 6.

Let D be a domain, R be a set of expressions representing continuous functions, and

R^{'}

be any superset of R such that there exists an expression in

R^{'}

that represents the Dirichlet function

K_{0} (x)

defined by

K_{0} (x) = \{\begin{matrix} 1, & if x is rational \\ 0, & if x is irrational \end{matrix}

Then, for any fixed set of functions Γ, where

1.: 0 functions over D are in Γ and
2.: $Γ \subseteq$ the set of all semi-continuous functions over D represented by expressions in $R^{'}$ , ${F \in R | F (x) \equiv 0$ over $D} ⩽_{p t i m e} {F \in R^{'} | F (x)$ over D is in $Γ}$ .

Proof.

For any function F(x), where

F \in R

, we can efficiently construct an expression

G \in R^{'}

such that

G (x) = F (x) * K_{0} (x)

. Clearly, if

F (x) \equiv 0

over D, then

G (x) \equiv 0

over D. So,

G (x) \in Γ

. Otherwise, because

F (x)

is continuous, there exists an interval

(a, b) \subseteq D

with

a < b

such that

F (x) \neq 0

at any point on

(a, b)

. So,

G (x)

is everywhere discontinuous over

(a, b)

. Hence,

G (x)

is not semi-continuous over D. Hence,

G (x) \notin Γ

. □

The following corollary shows several direct implications of this theorem. We need several definitions to understand the terminologies mentioned in the following corollary.

Definition 5.

1.: A real-valued function $f : D \mapsto S$ is called uniformly continuous over D if, for every real number $ϵ > 0$ , there exists $δ > 0$ such that for every $x, y \in D$ , $| x - y | < δ$ implies $| f (x) - f (y) | < ϵ$ .
2.: A real-valued function $f : D \mapsto S$ is called right differentiable at $a \in D$ if the limit $lim_{\binom{x \to a +}{x \in D}} \frac{f (x) - f (a)}{x - a}$ exists as a real number. f is called left differentiable at $a \in D$ if the limit $lim_{\binom{x \to a -}{x \in D}} \frac{f (x) - f (a)}{x - a}$ exists as a real number. f is semi-differentiable at $a \in D$ if f is left and right differentiable at $a \in D$ .
3.: A real-valued function $f : D \mapsto S$ is said to be continuously differentiable over D if its derivative $f^{'} (x)$ exists over D and $f^{'} (x)$ is a continuous function over D.

Corollary 5.

${F \in R | F (x) \equiv 0$ over $D} ⩽_{p t i m e} {F \in R^{'} | F (x)$ is continuous over $D}$ ;
${F \in R | F (x) \equiv 0$ over $D} ⩽_{p t i m e} {F \in R^{'} | F (x)$ is semi-continuous over $D}$ ;
${F \in R | F (x) \equiv 0$ over $D} ⩽_{p t i m e} {F \in R^{'} | F (x)$ is uniformly continuous over $D}$ ;
${F \in R | F (x) \equiv 0$ over $D} ⩽_{p t i m e} {F \in R^{'} | F (x)$ is differentiable over $D}$ ;
${F \in R | F (x) \equiv 0$ over $D} ⩽_{p t i m e} {F \in R^{'} | F (x)$ is semi-differentiable over $D}$ ;
${F \in R | F (x) \equiv 0$ over $D} ⩽_{p t i m e} {F \in R^{'} | F (x)$ is continuously differentiable over $D}$ ;
${F \in R | F (x) \equiv 0$ over $D} ⩽_{p t i m e} {F \in R^{'} | F (x)$ is n times differentiable over D where $n \geq 1}$ .

Proof.

From Definition 5, it is clear that every case satisfies the conditions of

Γ

defined in Theorem 6. □

Based on the results presented in Section 3, it is evident that for certain sets of elementary functions, the predicates outlined in Corollary 5 are all productive. Given the numerous theoretical properties of the identically 0 function in the context of real variables, and utilizing dichotomized reductions, we believe that the proof technique employed in Theorem 6 has broad applicability, and this technique can be used to establish much more results beyond those demonstrated in Corollary 5. Although our results to date primarily focus on productiveness, which is a stronger concept than undecidability and has significant implications in the theory of functions of real variables, we believe that the relative complexity results established in this section also offer considerable potential applications. This is mainly due to the highly efficient many-one reductions developed here, which effectively preserve nearly every level of complexity.

5. Conclusions

In this paper, we have explored the complexity and productiveness of real functions, drawing valuable insights from the theory of formal languages. We have demonstrated that determining whether a function is identically 0 over various domains is productive, which is a stronger form of non-recursive enumerability. We then established Rice-style theorems for real functions by using highly efficient many-one reductions from the equivalence to the identically 0 function problem.

Our investigation into dichotomized reductions introduced a novel technique for transforming the equivalence to the identically 0 function problem into instances that involve specific properties, such as continuity or differentiability. By employing functions like the Dirichlet function in these transformations, we have developed a robust method for analyzing and comparing real function properties. The dichotomized reductions leverage numerous theoretical properties of the identically 0 function, resulting in constructions that either exhibit many properties (because they are identically 0) or possess no properties, as exemplified by the Dirichlet function. This approach not only enhances our understanding of function equivalence but also provides practical tools for addressing complex questions in real analysis.

The implications of our work are significant, affecting both theoretical and practical aspects of real function analysis. The methods and results discussed lay a foundation for the further exploration and application of complexity theory to real functions. Our approach offers new perspectives on classical problems and promises to advance the field of real function theory. We anticipate that the techniques and insights presented here will inspire further research and contribute to a deeper understanding of the computational aspects of real functions, potentially impacting various areas of mathematical and applied research.

Author Contributions

Conceptualization, J.X., H.B.H.III and R.E.S.; methodology, J.X. and H.B.H.III; software, J.X.; validation, J.X., H.B.H.III and R.E.S.; formal analysis, J.X.; investigation, J.X.; resources, J.X. and H.B.H.III; writing—original draft preparation, J.X.; writing—review and editing, J.X., H.B.H.III and R.E.S.; supervision, H.B.H.III and R.E.S. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Data Availability Statement

This research did not involve the use or generation of any data.

Conflicts of Interest

The authors declare no conflicts of interest.

References

Vasco Brattka, P.H. (Ed.) Handbook of Computability and Complexity in Analysis; Theory and Applications of Computability; Springer: Cham, Switzerland, 2021. [Google Scholar] [CrossRef]
Berger, U.; Franklin, J.N.Y.; Manea, F.; Pauly, A. (Eds.) Revolutions and Revelations in Computability. In 18th Conference on Computability in Europe, CiE 2022; Lecture Notes in Computer Science; Springer: Cham, Switzerland, 2022. [Google Scholar] [CrossRef]
Hunt, H.B., III; Rosenkrantz, D.J. Computational Parallels Between the Regular and Context-free Languages. SIAM J. Comput. 1978, 7, 99–114. [Google Scholar] [CrossRef]
Hunt, H.B., III; Rosenkrantz, D.J. On Equivalence and Containment Problems for Formal Languages. J. ACM 1977, 24, 387–396. [Google Scholar] [CrossRef]
Xie, J.; Hunt, H.B., III. On the Undecidability and Descriptional Complexity of Synchronized Regular Expressions. Acta Inf. 2023, 60, 257–278. [Google Scholar] [CrossRef]
Xie, J.; Hunt, H.B., III; Stearns, R.E. On the Computational and Descriptional Complexity of Multi-Pattern Languages. Available online: https://ssrn.com/abstract=4493700 (accessed on 9 May 2024).
Xie, J.; Hunt, H.B., III; Stearns, R.E. Pumping Lemmas can be “Harmful”. Theory Comput. Syst. 2024. [Google Scholar] [CrossRef]
Xie, J.; Hunt, H.B., III; Stearns, R.E. Decision Problems Concerning L Systems. Available online: https://ssrn.com/abstract=4823208 (accessed on 9 May 2024).
Caviness, B.F. On Canonical Forms and Simplification. J. ACM 1970, 17, 385–396. [Google Scholar] [CrossRef]
Richardson, D. Some Undecidable Problems Involving Elementary Functions of a Real Variable. J. Symb. Log. 1968, 33, 514–520. [Google Scholar] [CrossRef]
Matiyasevich, Y.V. Hilbert’s Tenth Problem; MIT Press: Cambridge, MA, USA, 1993. [Google Scholar]
Hopcroft, J.E.; Ullman, J.D. Introduction to Automata Theory, Languages, and Computation; Addison-Wesley: Reading, MA, USA, 1979. [Google Scholar]
Rudin, W. Principles of Mathematical Analysis; McGraw-Hill: New York, NY, USA, 1976. [Google Scholar]
Rogers, H., Jr. Theory of Recursive Functions and Effective Computability; MIT Press: Cambridge, MA, USA, 1987. [Google Scholar]
Soare, R.I. Recursively Enumerable Sets and Degrees; Springer: Berlin/Heidelberg, Geramny, 1987. [Google Scholar]
Matiyasevich, Y.V. Enumerable sets are diophantine. In Mathematical Logic in the 20th Century; World Scientific: Singapore, 2003; pp. 269–273. [Google Scholar] [CrossRef]
Matiyasevich, Y.V. Hilbert’s tenth problem: What was done and what is to be done. Contemp. Math. 2000, 270, 1–48. [Google Scholar]
Aliprantia, C.D.; Burkinshaw, O. Principles of Real Analysis; Academic Press: San Diego, CA, USA, 1998. [Google Scholar]
Endou, N.; Wasaki, K.; Shidama, Y. Basic properties of extended real numbers. Formaliz. Math. 2001, 9, 491–494. [Google Scholar]

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Xie, J.; Hunt, H.B., III; Stearns, R.E. On Productiveness and Complexity in Computable Analysis Through Rice-Style Theorems for Real Functions. Mathematics 2024, 12, 3248. https://doi.org/10.3390/math12203248

AMA Style

Xie J, Hunt HB III, Stearns RE. On Productiveness and Complexity in Computable Analysis Through Rice-Style Theorems for Real Functions. Mathematics. 2024; 12(20):3248. https://doi.org/10.3390/math12203248

Chicago/Turabian Style

Xie, Jingnan, Harry B. Hunt, III, and Richard E. Stearns. 2024. "On Productiveness and Complexity in Computable Analysis Through Rice-Style Theorems for Real Functions" Mathematics 12, no. 20: 3248. https://doi.org/10.3390/math12203248

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Article metric data becomes available approximately 24 hours after publication online.

Article Menu

On Productiveness and Complexity in Computable Analysis Through Rice-Style Theorems for Real Functions

Abstract

1. Introduction

2. Definitions and Preliminary Results

3. The Equivalence to the Identically 0 Function Problem

4. Rice-Style Theorems for Real Fields

5. Conclusions

Author Contributions

Funding

Data Availability Statement

Conflicts of Interest

References

Share and Cite

Article Metrics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI