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$ – Andrej Bauer Mar 8 '19 at 18:23
  • $\begingroup$ Sure, but that's mathematics. I'm asking specifically about computer science. $\endgroup$ – Siegmeyer Mar 9 '19 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 Mar 9 '19 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 Mar 9 '19 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$ – Andrej Bauer Mar 10 '19 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.