Period Finding for Continuous Functions Cannot Be Automated on Turing Machines

Research output: Contribution to journal › Research article › Contributed › peer-review

Contributors

  • Holger Boche - , Technical University of Munich, TUD Dresden University of Technology, Munich Center for Quantum Science and Technology (MCQST) (Author)
  • Volker Pohl - , Technical University of Munich (Author)
  • H. Vincent Poor - , Princeton University (Author)

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 languageEnglish
Pages (from-to)3284-3297
Number of pages14
JournalIEEE transactions on computers
Volume75
Issue number9
Early online date22 Jun 2026
Publication statusPublished - Sept 2026
Peer-reviewedYes

External IDs

Mendeley 0596314d-e976-356f-a0ed-ed05c35f2cb1

Keywords

Keywords

  • Bandwidth, Nyquist Sampling, Period finding, Quantum Computing, RSA algorithm, Shor algorithm, Turing computability, Nyquist sampling, bandwidth, quantum computing