McCarthy formalism is a formalism for defining functions recursively, first introduced in classic paper Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (1960).

From Wikipedia:

In his 1967 Computation: Finite and Infinite Machines, Marvin Minsky in his § 10.6 Conditional Expressions: The McCarthy Formalism describes the "formalism" as follows:

"Practical computer languages do not lend themselves to formal mathematical treatment--they are not designed to make it easy to prove theorems about the procedures they describe. In a paper by McCarthy [1963] we find a formalism that enhances the practical aspect of the recursive-function concept, while preserving and improving its mathematical clarity.

McCarthy introduces "conditional expressions" of the form f = (if p1 then e1 else e2) where the ei are expressions and p1 is a statement (or equation) that may be true or false. This expression means: See if p1 is true; if so the value of f is given by e1. IF p1 is false, the value of f is given by e2. [...]

The McCarthy formalism is like the general recursive (Kleene) system, in being based on some basic functions, composition, and equality, but with the conditional expression alone replacing both the primitive-recursive scheme and the minimization operator." (Minsky 1967:192-193)

I'm interested in chronology. Was there any other formalism regarding recursive function before McCarthy Formalism (in computer science)?

  • 1
    $\begingroup$ Such as Gödel's formalism for general recursive functins which predates McCarthy by at least 25 years? $\endgroup$ Commented Mar 8, 2019 at 18:23
  • $\begingroup$ Sure, but that's mathematics. I'm asking specifically about computer science. $\endgroup$
    – Siegmeyer
    Commented Mar 9, 2019 at 10:24
  • 2
    $\begingroup$ @Siegmeyer In TCS, there is no meaningful difference. $\mu$-recursion and $\lambda$-calculus are mathematical models we use in computer science. See also this question. $\endgroup$
    – Raphael
    Commented Mar 9, 2019 at 11:45
  • $\begingroup$ FWIW, formal semantics seem to have emerged later. Is that the field you are referring to, as opposed to computability/recursion theory? $\endgroup$
    – Raphael
    Commented Mar 9, 2019 at 11:47
  • 1
    $\begingroup$ @Siegmeyer: Wehre do you think people like McCarthy got their ideas from? They were very knowledgable, also about mathematics. $\endgroup$ Commented Mar 10, 2019 at 0:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.