Algorithmic procedures
HTML articles powered by AMS MathViewer
- by Harvey Friedman and Richard Mansfield PDF
- Trans. Amer. Math. Soc. 332 (1992), 297-312 Request permission
Abstract:
We consider the state of elementary recursion theory when the familiar $0, 1, +, \times , =, <$ of ordinary arithmetic are replaced by constants, functions, and relations from an arbitrary model.References
- Lenore Blum, Mike Shub, and Steve Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.) 21 (1989), no. 1, 1–46. MR 974426, DOI 10.1090/S0273-0979-1989-15750-9
- C. C. Chang and H. J. Keisler, Model theory, 3rd ed., Studies in Logic and the Foundations of Mathematics, vol. 73, North-Holland Publishing Co., Amsterdam, 1990. MR 1059055
- Harvey Friedman, Algorithmic procedures, generalized Turing algorithms, and elementary recursion theory, Logic Colloquium ’69 (Proc. Summer School and Colloq., Manchester, 1969) North-Holland, Amsterdam, 1971, pp. 361–389. MR 0304140
- A. J. Kfoury, The pebble game and logics of programs, Harvey Friedman’s research on the foundations of mathematics, Stud. Logic Found. Math., vol. 117, North-Holland, Amsterdam, 1985, pp. 317–329. MR 835264, DOI 10.1016/S0049-237X(09)70165-X
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- Richard Mansfield, A complete axiomatization of computer arithmetic, Math. Comp. 42 (1984), no. 166, 623–635. MR 736458, DOI 10.1090/S0025-5718-1984-0736458-7
- Richard Mansfield, The irrationals are not recursively enumerable, Proc. Amer. Math. Soc. 110 (1990), no. 2, 495–497. MR 1019752, DOI 10.1090/S0002-9939-1990-1019752-9
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
- J. C. Shepherdson, Algorithmic procedures, generalized Turing algorithms, and elementary recursion theory, Harvey Friedman’s research on the foundations of mathematics, Stud. Logic Found. Math., vol. 117, North-Holland, Amsterdam, 1985, pp. 285–308. MR 835262, DOI 10.1016/S0049-237X(09)70163-6
- Alfred Tarski, A decision method for elementary algebra and geometry, University of California Press, Berkeley-Los Angeles, Calif., 1951. 2nd ed. MR 0044472
Additional Information
- © Copyright 1992 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 332 (1992), 297-312
- MSC: Primary 03D75
- DOI: https://doi.org/10.1090/S0002-9947-1992-1055807-7
- MathSciNet review: 1055807