Is McCarthy Formalism first ever formalism for defining functions recursively in computer science?

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

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


Source : Link , Question Author : Siegmeyer , Answer Author : Community

Leave a Comment