Period Finding for Continuous Functions Cannot Be Automated on Turing Machines

Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung

Beitragende

  • Holger Boche - , Technische Universität München, Technische Universität Dresden, Munich Center for Quantum Science and Technology (MCQST) (Autor:in)
  • Volker Pohl - , Technische Universität München (Autor:in)
  • H. Vincent Poor - , Princeton University (Autor:in)

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

OriginalspracheEnglisch
Seiten (von - bis)3284-3297
Seitenumfang14
FachzeitschriftIEEE transactions on computers
Jahrgang75
Ausgabenummer9
Frühes Online-Datum22 Juni 2026
PublikationsstatusVeröffentlicht - Sept. 2026
Peer-Review-StatusJa

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