Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-25T17:44:33.345Z Has data issue: false hasContentIssue false
  • English
  • Français

Can there be no nonrecursive functions?

Published online by Cambridge University Press:  12 March 2014

Joan Rand Moschovakis
Joan Rand Moschovakis*
Affiliation:
Occidental College, Los Angeles, California 90041
Get access Rights & Permissions [Opens in a new window]

Extract

In 1936 Alonzo Church proposed the following thesis: Every effectively computable number-theoretic function is general recursive. The classical mathematician can easily give examples of nonrecursive functions, e.g. by diagonalizing a list of all general recursive functions. But since no such function has been found which is effectively computable, there is as yet no classical evidence against Church's Thesis.

The intuitionistic mathematician, following Brouwer, recognizes at least two notions of function: the free-choice sequence (or ordinary number-theoretic function, thought of as the ever-finite but ever-extendable sequence of its values) and the sharp arrow (or effectively definable function, all of whose values can be specified in advance).

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 36 , Issue 2 , June 1971 , pp. 309 - 315
Copyright
Copyright © Association for Symbolic Logic 1971

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

[1]Heyting, A., Intuitionism, North-Holland Publishing Company, Amsterdam, 1956 (2nd ed. 1966).Google Scholar
[2]Kleene, S. C. and Vesley, R. E., The foundations of intuitionistic mathematics, North-Holland Publishing Company, Amsterdam, 1965.Google Scholar
[3]Kleene, S. C., Formalized recursive functionals and formalized realizability, Memoirs of the American Mathematical Society, No. 89 (1969), Providence, R.I.CrossRefGoogle Scholar
[4]Kreisel, G. and Troelstra, A. S., Formal systems for some branches of intuitionistic analysis, Annals of mathematical logic, vol. 1 (1970), pp. 229–387.CrossRefGoogle Scholar
[5]Myhill, John, Formal systems of intuitionistic analysis I, Logic, methodology and philosophy of science III, edited by Rootselaar, B. van and Staal, J. F., North-Holland Publishing Company, Amsterdam, 1968.Google Scholar
[6]Vesley, R. E., A palatable alternative to Kripke's schema, Intuitionism and proof theory, edited by Myhill, J., Kino, A., and Vesley, R., North-Holland Publishing Company, Amsterdam, 1970.Google Scholar