Abstract
Every finite and every co-finite set of non-negative integers is decidable. This is true and it is not, depending on whether the set is given constructively. A similar constraint is applicable in language theory and many other fields. The constraint is usually understood and, hence, omitted.
The phenomenon of a set being finite, but possibly undecidable, is, of course, a consequence of allowing non-constructive arguments in proofs. In this note we discuss a few ramifications of this fact. We start out with showing that every number theoretic statement that can be expressed in first-order logic can be reduced to a finite set, to be called a test set. Thus, if one knew the test set, one could determine the truth of the statement. The crucial point is, of course, that we may not be able to know what the finite test set is. Using problems in the class Π1 of the arithmetic hierarchy as an example, we establish that the bound on the size of the test set is Turing-complete and that it is upper-bounded by the busy-beaver function.
This re-enforces the fact that there is a vast difference between finiteness and constructive finiteness. In the context of the present re-opened discussion about the notion of computability — possibly extending its realm through new computational models derived from physics — the constraint of constructivity of the model itself may add another twist.
The Research reported in this paper was partially supported by Auckland University, Research Grant A18/XXXXX/602090/3414050, and by the Natural Sciences and Engineeringn Council and Canada, Grant OGP0000243.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. H. Albert, J. Lawrence, A proof of Ehrenfeucht’s conjecture, Theoret. Comput. Sci., 41 (1985), 121–123.
C. H. Bennett, Chaitin’s Omega, in Fractal Music, HyperCards, and More… (M. Gardner, ed.), W. H. Freeman, New York, 1992, 307–319.
R. P. Brent, J. v. d. Lune, H. J. J. t. Riele, D. T. Winter, On the zeros of the Riemann zeta function in the critical strip I, Math. Comp., 33 (1979), 1361–1372.
R. P. Brent, J. v. d. Lune, H. J. J. t. Riele, D. T. Winter, On the zeros of the Riemann zeta function in the critical strip II, Math. Comp., 39 (1979), 1361–1372.
R. P. Brent, J. v. d. Lune, H. J. J. t. Riele, D. T. Winter, On the zeros of the Riemann zeta function in the critical strip III, Math. Comp., 41 (1979), 1361–1372.
R. P. Brent, J. v. d. Lune, H. J. J. t. Riele, D. T. Winter, On the zeros of the Riemann zeta function in the critical strip IV, Math. Comp., 46 (1979), 1361–1372.
C. Calude, Note on Ehrenfeucht’s conjecture and Hilbert’s basis theorem, Bull. EATCS, 29 (1986), 18–22.
C. Calude, Theories of Computational Complexities, North-Holland, Amsterdam, 1988.
C. S. Calude, G. J. Chaitin, Randomness everywhere. Nature, 400, 22 July (1999), 319–320.
C. Calude, H. Jürgensen, M. Zimand, Is independence an exception? Applied Mathematics and Computation, 66 (1994), 63–76.
C. Calude, D. Vaida, Ehrenfeucht test set theorem and Hilbert basis theorem: A constructive glimpse, in Mathematical Foundations of Computer Science, 1989 (A. Kreczmar, G. Mirkowska, eds.), Lecture Notes in Computer Science 379, Springer-Verlag, Berlin, 1989, 177–184.
G. J. Chaitin, The Unknowable, Springer-Verlag, Singapore, 1999.
C. Choffrut, J. Karhumäki, Combinatorics on words, in Handbook of Formal Language Theory (G. Rozenberg, A. Salomaa, eds.), Vol. 1, Springer-Verlag, Berlin, 1987, 329–438.
M. Davis, Y. V. Matijasevič, J. Robinson, Hilbert’s tenth problem. Diophantine equations: Positive aspects of a negative solution, in Mathematical Developments Arising from Hilbert Problems (F. E. Browder, ed.), American Mathematical Society, Providence, RI, 1976, 323–378.
A. K. Dewdney, A computer trap for the busy beaver, the hardest-working Turing machine, Scientific American, 251(8) (1984), 19–23.
A. K. Dewdney, The New Turing Omnibus, Computer Science Press, New York, 1993.
L. E. Dickson, History of the Theory of Numbers, Carnegie Institute, Washington, 1919, 1920, 1923, 3 volumes.
V. S. Guba, The equivalence of infinite systems of equations in free groups and semigroups, Mat. Zametki, 40 (1986), 321–324 (in Russian).
G. H. Hardy, Goldbach’s theorem, Mat. Tid. B, 1 (1922), 1–16. Reprinted in Collected Papers of G. H. Hardy vol. 1, Oxford University Press, Oxford, 1966, 545–560.
J. Karhumäki, W. Rytter, S. Jarominek, Efficient constructions of test sets for regular and context-free languages, Theoret. Comput. Sci., 116 (1993), 305–316.
J. Karhumäki, W. Plandowski, W. Rytter, Polynomial size test sets for context-free languages, J. Comput. System Sci., 50 (1995), 11–19.
W. A. Light, T. J. Forres, N. Hammond, S. Roe, A note on the Goldbach conjecture, BIT, 20 (1980), 525.
Y. V. Matijasevič, Hilbert’s Tenth Problem, MIT Press, Cambridge, MA, 1993, 117–122.
S. Marcus, Bridging linguistics and computer science, via mathematics, in People and Ideas in Theoretical Computer Science (C. S. Calude, ed.), Springer-Verlag, Singapore, 1998, 163–176.
A. M. Odlyzko, Tables of zeros of the Riemann zeta function, http://www.research.att.com/amo/zeta_tables/index.html.
C.-T. Pan, Goldbach Conjecture, Science Press, Beijing, 1992.
D. Perrin, On the solution of Ehrenfeucht’s conjecture, Bull. EATCS, 27 (1985), 68–70.
E. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. (New Series) Amer. Math. Soc., 50 (1944), 284–316.
T. Rado, On non-computable numbers, Bell System Tech. J., 3 (1962), 977–884.
B. Riemann, Über die Anzahl der Primzahlen unter einer gegebenen Größe, in Gesammelte mathematische Werke und, wissenchaftlicher Nachlaß, Springer-Verlag, Berlin, 1990, 177–185.
H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkhäuser, Boston, second ed., 1994.
H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967.
A. Salomaa, The Ehrenfeucht conjecture: A proof for language theorists, Bull. EATCS, 27 (1985), 71–82.
W. Yuan, ed., Goldbach Conjecture, World Scientific, Singapore, 1984.
Names of large numbers and unsolved problems, http://www.smartpages.com/faqs/sci-math-faq/unsolvedproblems/faq.html, December 1994.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag London Limited
About this chapter
Cite this chapter
Calude, C.S., Jürgensen, H., Legg, S. (2000). Solving Problems with Finite Test Sets. In: Finite Versus Infinite. Discrete Mathematics and Theoretical Computer Science. Springer, London. https://doi.org/10.1007/978-1-4471-0751-4_4
Download citation
DOI: https://doi.org/10.1007/978-1-4471-0751-4_4
Publisher Name: Springer, London
Print ISBN: 978-1-85233-251-8
Online ISBN: 978-1-4471-0751-4
eBook Packages: Springer Book Archive