000219538 001__ 219538
000219538 005__ 20180913063751.0
000219538 0247_ $$2doi$$a10.1016/j.apal.2016.03.001
000219538 022__ $$a0168-0072
000219538 02470 $$2ISI$$a000375821500001
000219538 037__ $$aARTICLE
000219538 245__ $$aUndecidability through Fourier series
000219538 260__ $$aAmsterdam$$bElsevier Science Bv$$c2016
000219538 269__ $$a2016
000219538 300__ $$a18
000219538 336__ $$aJournal Articles
000219538 520__ $$aIn computability theory a variety of combinatorial systems are encountered (word problems, production systems) that exhibit undecidability properties. Here we seek such structures in the realm of Analysis, more specifically in the area of Fourier Analysis. The starting point is that sufficiently strongly convergent Fourier series give rise to predicates in the sense of first order predicate calculus by associating to any s-ary Fourier series the predicate "the Fourier coefficient with index (n(1), ... , n(s)) is non-zero". We introduce production systems, viewed as counterparts of the combinatorial ones, that generate all recursively enumerable predicates in this way using as tools only elementary operations and functions from classical Analysis. The problem arises how simple such a system may be. It turns out that there is a connection between this question and an as yet unproved conjecture by R. Bilchi. This is discussed in the second half of the paper. (C) 2016 Elsevier B.V. All rights reserved.
000219538 6531_ $$aRecursively enumerable sets
000219538 6531_ $$aFourier series
000219538 6531_ $$aBuchi's problem
000219538 6531_ $$aJacobi theta functions
000219538 700__ $$aBuser, Peter$$uEcole Polytech Fed Lausanne, MATHGEOM, SB, Stn 8, CH-1015 Lausanne, Switzerland
000219538 700__ $$aScarpellini, Bruno
000219538 773__ $$j167$$k7$$q507-524$$tAnnals Of Pure And Applied Logic
000219538 909C0 $$0252438$$pMATHGEOM$$xU10159
000219538 909CO $$ooai:infoscience.tind.io:219538$$particle
000219538 937__ $$aEPFL-ARTICLE-219538
000219538 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000219538 980__ $$aARTICLE