Period Finding for Continuous Functions Cannot Be Automated on Turing Machines
Research output: Contribution to journal › Research article › Contributed › peer-review
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
| Original language | English |
|---|---|
| Pages (from-to) | 3284-3297 |
| Number of pages | 14 |
| Journal | IEEE transactions on computers |
| Volume | 75 |
| Issue number | 9 |
| Early online date | 22 Jun 2026 |
| Publication status | Published - Sept 2026 |
| Peer-reviewed | Yes |
External IDs
| Mendeley | 0596314d-e976-356f-a0ed-ed05c35f2cb1 |
|---|
Keywords
ASJC Scopus subject areas
Keywords
- Bandwidth, Nyquist Sampling, Period finding, Quantum Computing, RSA algorithm, Shor algorithm, Turing computability, Nyquist sampling, bandwidth, quantum computing