A BASIS FOR A MATHEMATICAL THEORY OF COMPUTATION

JOHN McCARTHY

1961-1963

[This 1963 paper was included in Computer Programming and Formal Systems, edited by P. Braffort and D. Hirshberg and published by North-Holland. An earlier version was published in 1961 in the Proceedings of the Western Joint Computer Conference.]

• Introduction
• Formalisms For Describing Computable Functions and Related Entities
  • Functions Computable in Terms of Given Base Functions
  • Recursive Functions of the Integers
  • Computable Functionals
  • Non-Computable Functions and Functionals
  • Ambiguous Functions
  • Recursive Definitions of Sets
• Properties of Computable Functions
  • Formal Properties of Conditional Forms
  • Recursion Induction
• Relation to Other Formalisms
  • Recursive function theory
  • On the Relations between Computation and Mathematical Logic
• Conclusion: Mathematical Theory of Computation
• REFERENCES
• About this document ...