Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-24T17:36:39.624Z Has data issue: false hasContentIssue false
  • English
  • Français

Some strongly undecidable natural arithmetical problems, with an application to intuitionistic theories

Published online by Cambridge University Press:  12 March 2014

Panu Raatikainen
Panu Raatikainen*
Affiliation:
Helsinki Collegium for Advanced Studies, P.O. Box 4, Fin-00014, Univeristy of Helsinki, Finland, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

Although Church and Turing presented their path-breaking undecidability results immediately after their explication of effective decidability in 1936, it has been generally felt that these results do not have any direct bearing on ordinary mathematics but only contribute to logic, metamathematics and the theory of computability. Therefore it was such a celebrated achievement when Yuri Matiyasevich in 1970 demonstrated that the problem of the solvability of Diophantine equations is undecidable. His work was building essentially on the earlier work by Julia Robinson, Martin Davis and Hilary Putnam (1961), who had showed that the problem of solvability of exponential Diophantine equations is undecidable. One should note, however, that although it was only Matiyasevich's result which finally solved Hilbert's tenth problem, already the earlier result had provided a perfectly natural problem of ordinary number theory which is undecidable.

Nevertheless, both the set of Diophantine equations with solutions and the set of exponential Diophantine equations with solutions are still semi-decidable, that is, recursively enumerable (i.e., Σ10); if an equation in fact has a solution, this can be eventually verified. More generally, they are — as are their complements, the sets of equations with no solutions, which are Π10, — also Trial and Error decidable (Putnam [1965]), or decidable in the limit (Shoenfield [1959]), for every Δ20 set is (and conversely). This last-mentioned natural “liberalized” notion of decidability has begun more recently to play an essential role e.g., in so-called Formal Learning Theory (see e.g., Osherson, Stob, and Weinstein [1986], Kelly [1996]).

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 68 , Issue 1 , March 2003 , pp. 262 - 266
Copyright
Copyright © Association for Symbolic Logic 2003

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Davis, M. [1972], On the number of solutions of Diophantine equations, Proceedings of the American Mathematical Society, vol. 35, pp. 552–554.CrossRefGoogle Scholar
Davis, M. [1973], Hilbert's tenth problem is unsohable, The American Mathematical Monthly, vol. 80, pp. 233–269.CrossRefGoogle Scholar
Davis, M. [1977], Unsolvable problems, Handbook of mathematical logic (Barwise, J., editor), North-Holland, Amsterdam, pp. 567–594.CrossRefGoogle Scholar
Davis, M., Putnam, H., and Robinson, J. [1961], The decision problem for exponential diophantine equations, Annals of Mathematics, Second Series, vol. 74, pp. 425–436.CrossRefGoogle Scholar
Davis, M., Putnam, H., and Robinson, J. [1976], Hubert's tenth problem. Diophantine equations: positive aspects of a negative solution, Proceedings of Symposia in Pure Mathematics, vol. 28, pp. 323–378.CrossRefGoogle Scholar
Friedman, Harvey [1978], Classically and intuitionistically provably recursive functions, Higher set theory (Müller, and Scott, , editors), Springer-Verlag, Berlin, Lecture Notes in Mathematics 669, pp. 21–27.CrossRefGoogle Scholar
Kelly, K. [1996], The logic of reliable inquiry, Oxford University Press, New York.CrossRefGoogle Scholar
Lempp, S. [1997], The computational complexity of torsion-freeness of finitely presented groups, Bulletin of the Australian Mathematical Society, vol. 56, pp. 273–277.CrossRefGoogle Scholar
Matiyasevich, Y. [1970], Diofantovost' perechislimykh mnozhestv, Doklady Akademii Nauk SSSR, vol. 191, no. 2, pp. 297–282, (Russian). (English translation, Enumerable sets are Diophantine, Soviet Mathematics Doklady, vol. 11, no. 2, pp. 354–358).Google Scholar
Matiyasevich, Y. [1974], Sushchestvovanie neeffektiviziruemikh otsenok v teorii ekzponentsial'no dio-fantovikh, Zapiski Naucnyh Seminarov Leningradskogo Otdelenija Matematiceskogo Instituta im. V. A. Steklova, Academii Nauk SSSR, vol. 40, pp. 77–93.Google Scholar
Matiyasevich, Y. [1993], Hubert's tenth problem, M.I.T. Press, Cambridge, MA.Google Scholar
Osherson, D., Stob, M., and Weinstein, S. [1986], Systems that learn, M.I.T. Press, Cambridge.Google Scholar
Putnam, H. [1965], Trial and error predicates and the solution to a problem of Mostowski, this Journal, vol. 30, pp. 49–57.Google Scholar
Rogers, H. Jr. [1958], Gödel numberings of partial recursive functions, this Journal, vol. 23, pp. 331–341.Google Scholar
Rogers, H. Jr., [1967], Theory of recursive functions and effective computability, McGraw-Hill, New York.Google Scholar
Shoenfield, J. R. [1959], On degrees of unsolvability, Annals of Mathematics, vol. 69, pp. 644–653.CrossRefGoogle Scholar
Smoryński, C. [1977], A note on the number of zeros of polynomials and exponential polynomials, this Journal, vol. 42, pp. 99–106.Google Scholar
Smoryński, C. [1991], Logical number theory. I, Springer-Verlag, Berlin.CrossRefGoogle Scholar