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

Jingnan Xie (), Harry B. Hunt and Richard E. Stearns
Additional contact information
Jingnan Xie: Computer Science, Millersville University of Pennsylvania, 40 Dilworth Rd, Millersville, PA 17551, USA
Harry B. Hunt: Computer Science, University at Albany, State University of New York, Albany, NY 12222, USA
Richard E. Stearns: Computer Science, University at Albany, State University of New York, Albany, NY 12222, USA

Mathematics, 2024, vol. 12, issue 20, 1-12

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 (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/20/3248/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/20/3248/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:20:p:3248-:d:1500513

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().