Undecidability through Fourier series. (English) Zbl 1403.03064
Summary: In 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, \ldots, 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. Büchi. This is discussed in the second half of the paper.
MSC:
| 03D25 | Recursively (computably) enumerable sets and degrees |
| 03D35 | Undecidability and degrees of sets of sentences |
| 03D78 | Computation over the reals, computable analysis |
| 03D80 | Applications of computability and recursion theory |
| 42B05 | Fourier series and coefficients in several variables |
| 11Y55 | Calculation of integer sequences |
| 33E05 | Elliptic functions and integrals |
References:
| [1] | Adler, A., Some recursively unsolvable problems in analysis, Proc. Amer. Math. Soc., 22, 523-526 (1969) · Zbl 0206.28401 |
| [2] | (Mac Lane, Saunders; Siefkes, Dirk, The Collected Works of J. Richard Büchi (1990), Springer-Verlag: Springer-Verlag New York), With a Preface by Saunders Mac Lane and Dirk Siefkes · Zbl 0725.68006 |
| [3] | Buser, P., Darstellung von Prädikaten durch analytische Funktionen (1972), Universität Basel, 41 pp. |
| [4] | Buser, P.; Scarpellini, B., Undecidable propositions by ODE’s, Ann. Acad. Sci. Fenn. Math., 32, 317-340 (2007) · Zbl 1117.03068 |
| [5] | Copeland, J., Hypercomputation, Minds Mach., 12, 461-502 (2002) · Zbl 1036.68058 |
| [6] | Copeland, J., Super-recursive algorithms and hypercomputation, Theoret. Comput. Sci., 1-3, 251-267 (2004) · Zbl 1055.03007 |
| [7] | Davis, M., Computability and Unsolvability (1958), McGraw-Hill: McGraw-Hill New York · Zbl 0080.00902 |
| [8] | Denef, J.; Lipshitz, L., Decision problems for differential equations, J. Symbolic Logic, 54, 941-950 (1989) · Zbl 0683.03039 |
| [9] | Lipshitz, L., Quadratic forms, the five squares problem, and Diophantine equations, (Mac Lane, Saunders; Siefkes, Dirk, The Collected Works of J. Richard Büchi (1990), Springer-Verlag: Springer-Verlag New York), With a preface by Saunders Mac Lane and Dirk Siefkes |
| [10] | Matiyasevich, Y. V., Hilbert’s Tenth Problem (1993), MIT Press: MIT Press Cambridge, MA · Zbl 0790.03009 |
| [11] | Pasten, H.; Pheidas, T.; Vidaux, X., A survey on Büchi’s problem: new presentations and open problems, J. Math. Sci. (N. Y.), 171, 765-781 (2010) · Zbl 1282.11015 |
| [12] | Pour-El, M. B.; Richards, I., Computability and noncomputability in classical analysis, Trans. Amer. Math. Soc., 275, 539-560 (1983) · Zbl 0513.03031 |
| [13] | Pour-El, M. B.; Richards, I., The wave equation with computable initial data such that its unique solution is not computable, Adv. in Math., 39, 215-239 (1981) · Zbl 0465.35054 |
| [14] | Priwalow, I. I., Einführung in die Funktionentheorie, Teil III (1970), B.G. Teubner Verlagsgesellschaft: B.G. Teubner Verlagsgesellschaft Leipzig · Zbl 0177.33401 |
| [15] | Richardson, D., Some undecidable problems involving elementary functions of a real variable, J. Symbolic Logic, 33, 514-520 (1968) · Zbl 0175.27404 |
| [16] | Rubel, L. A., The extended analog computer, Adv. in Appl. Math., 14, 39-50 (1993) · Zbl 0805.68010 |
| [17] | Scarpellini, B., Zwei unentscheidbare Probleme in der Analysis, Z. Math. Log. Grundl. Math., 9, 265-289 (1963) · Zbl 0207.31002 |
| [18] | Scarpellini, B., Two undecidable problems of analysis, Minds Mach., 13, 49-77 (2003) · Zbl 1030.68044 |
| [19] | Scarpellini, B., Comments on “Two undecidable problems of analysis”, Minds Mach., 13, 79-85 (2003) · Zbl 1030.68040 |
| [20] | Syropoulos, A., Hypercomputation: Computing Beyond the Church-Turing Barrier (2008), Springer: Springer New York · Zbl 1162.68014 |
| [21] | Whittaker, E. T.; Watson, G. N., A Course of Modern Analysis (1996), Cambridge University Press: Cambridge University Press Cambridge, reprint of the fourth (1927) edition · Zbl 0951.30002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
