Period Finding for Continuous Functions Cannot Be Automated on Turing Machines
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Abstract
This paper investigates whether it is possible to have a Turing machine that is able to compute the minimum (or fundamental) period of a given periodic computable continuous function. It is shown that for every periodic computable continuous function f, its fundamental period is always a computable number. Therefore, there always exists a specific Turing machine, which depends on f, for computing the period of f. Nevertheless, it is also shown that there exists no universal algorithm on a Turing machine that is able to compute the period for all functions having periods that are smaller than a given upper bound. This result is established even for a class of nonlinear operators that compute a bounded deviation from the minimal period. It is shown that these operators are not even Banach–Mazur computable and therefore fail to satisfy even the weakest computability requirements known from the theory of digital computation.
Details
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 3284-3297 |
| Seitenumfang | 14 |
| Fachzeitschrift | IEEE transactions on computers |
| Jahrgang | 75 |
| Ausgabenummer | 9 |
| Frühes Online-Datum | 22 Juni 2026 |
| Publikationsstatus | Veröffentlicht - Sept. 2026 |
| Peer-Review-Status | Ja |
Externe IDs
| Mendeley | 0596314d-e976-356f-a0ed-ed05c35f2cb1 |
|---|
Schlagworte
ASJC Scopus Sachgebiete
- Software - Bandwidth, Nyquist Sampling, Period finding, Quantum Computing, RSA algorithm, Shor algorithm, Turing computability, Nyquist sampling, bandwidth, quantum computing
- Theoretische Informatik - Bandwidth, Nyquist Sampling, Period finding, Quantum Computing, RSA algorithm, Shor algorithm, Turing computability, Nyquist sampling, bandwidth, quantum computing
- Hardware und Architektur - Bandwidth, Nyquist Sampling, Period finding, Quantum Computing, RSA algorithm, Shor algorithm, Turing computability, Nyquist sampling, bandwidth, quantum computing
- Theoretische Informatik und Mathematik - Bandwidth, Nyquist Sampling, Period finding, Quantum Computing, RSA algorithm, Shor algorithm, Turing computability, Nyquist sampling, bandwidth, quantum computing
Schlagwörter
- Bandwidth, Nyquist Sampling, Period finding, Quantum Computing, RSA algorithm, Shor algorithm, Turing computability, Nyquist sampling, bandwidth, quantum computing