Computability of the Fourier Transform and ZFC

Holger Boche; Ullrich J. Monich

doi:10.1109/SampTA45681.2019.9030870

Computability of the Fourier Transform and ZFC

Holger Boche, Ullrich J. Monich

Chair of Theoretical Information Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Scopus citations

Abstract

In this paper we study the Fourier transform and the possibility to determine the binary expansion of the values of the Fourier transform in the Zermelo-Fraenkel set theory with the axiom of choice included (ZFC). We construct a computable absolutely integrable bandlimited function with continuous Fourier transform such that ZFC (if arithmetically sound) cannot determine a single binary digit of the binary expansion of the Fourier transform at zero. This result implies that ZFC cannot determine for every precision goal a rational number that approximates the Fourier transform at zero. Further, we discuss connections to Turing computability.

Original language	English
Title of host publication	2019 13th International Conference on Sampling Theory and Applications, SampTA 2019
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9781728137414
DOIs	https://doi.org/10.1109/SampTA45681.2019.9030870
State	Published - Jul 2019
Event	13th International Conference on Sampling Theory and Applications, SampTA 2019 - Bordeaux, France Duration: 8 Jul 2019 → 12 Jul 2019

Publication series

Name	2019 13th International Conference on Sampling Theory and Applications, SampTA 2019

Conference

Conference	13th International Conference on Sampling Theory and Applications, SampTA 2019
Country/Territory	France
City	Bordeaux
Period	8/07/19 → 12/07/19

Access to Document

10.1109/SampTA45681.2019.9030870

Cite this

Boche, H., & Monich, U. J. (2019). Computability of the Fourier Transform and ZFC. In 2019 13th International Conference on Sampling Theory and Applications, SampTA 2019 Article 9030870 (2019 13th International Conference on Sampling Theory and Applications, SampTA 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SampTA45681.2019.9030870

@inproceedings{19f12e52ef80495789cc09614ec1a486,

title = "Computability of the Fourier Transform and ZFC",

abstract = "In this paper we study the Fourier transform and the possibility to determine the binary expansion of the values of the Fourier transform in the Zermelo-Fraenkel set theory with the axiom of choice included (ZFC). We construct a computable absolutely integrable bandlimited function with continuous Fourier transform such that ZFC (if arithmetically sound) cannot determine a single binary digit of the binary expansion of the Fourier transform at zero. This result implies that ZFC cannot determine for every precision goal a rational number that approximates the Fourier transform at zero. Further, we discuss connections to Turing computability.",

author = "Holger Boche and Monich, {Ullrich J.}",

note = "Publisher Copyright: {\textcopyright} 2019 IEEE.; 13th International Conference on Sampling Theory and Applications, SampTA 2019 ; Conference date: 08-07-2019 Through 12-07-2019",

year = "2019",

month = jul,

doi = "10.1109/SampTA45681.2019.9030870",

language = "English",

series = "2019 13th International Conference on Sampling Theory and Applications, SampTA 2019",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "2019 13th International Conference on Sampling Theory and Applications, SampTA 2019",

}

Boche, H & Monich, UJ 2019, Computability of the Fourier Transform and ZFC. in 2019 13th International Conference on Sampling Theory and Applications, SampTA 2019., 9030870, 2019 13th International Conference on Sampling Theory and Applications, SampTA 2019, Institute of Electrical and Electronics Engineers Inc., 13th International Conference on Sampling Theory and Applications, SampTA 2019, Bordeaux, France, 8/07/19. https://doi.org/10.1109/SampTA45681.2019.9030870

Computability of the Fourier Transform and ZFC. / Boche, Holger; Monich, Ullrich J.
2019 13th International Conference on Sampling Theory and Applications, SampTA 2019. Institute of Electrical and Electronics Engineers Inc., 2019. 9030870 (2019 13th International Conference on Sampling Theory and Applications, SampTA 2019).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Computability of the Fourier Transform and ZFC

AU - Boche, Holger

AU - Monich, Ullrich J.

PY - 2019/7

Y1 - 2019/7

N2 - In this paper we study the Fourier transform and the possibility to determine the binary expansion of the values of the Fourier transform in the Zermelo-Fraenkel set theory with the axiom of choice included (ZFC). We construct a computable absolutely integrable bandlimited function with continuous Fourier transform such that ZFC (if arithmetically sound) cannot determine a single binary digit of the binary expansion of the Fourier transform at zero. This result implies that ZFC cannot determine for every precision goal a rational number that approximates the Fourier transform at zero. Further, we discuss connections to Turing computability.

AB - In this paper we study the Fourier transform and the possibility to determine the binary expansion of the values of the Fourier transform in the Zermelo-Fraenkel set theory with the axiom of choice included (ZFC). We construct a computable absolutely integrable bandlimited function with continuous Fourier transform such that ZFC (if arithmetically sound) cannot determine a single binary digit of the binary expansion of the Fourier transform at zero. This result implies that ZFC cannot determine for every precision goal a rational number that approximates the Fourier transform at zero. Further, we discuss connections to Turing computability.

UR - http://www.scopus.com/inward/record.url?scp=85073159340&partnerID=8YFLogxK

U2 - 10.1109/SampTA45681.2019.9030870

DO - 10.1109/SampTA45681.2019.9030870

M3 - Conference contribution

AN - SCOPUS:85073159340

T3 - 2019 13th International Conference on Sampling Theory and Applications, SampTA 2019

BT - 2019 13th International Conference on Sampling Theory and Applications, SampTA 2019

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 13th International Conference on Sampling Theory and Applications, SampTA 2019

Y2 - 8 July 2019 through 12 July 2019

ER -

Computability of the Fourier Transform and ZFC

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this