McCarthy Formalism
Encyclopedia
In computer science
and recursion theory
the McCarthy Formalism (1963) of computer
scientist John McCarthy
clarifies the notion of recursive function
s by use of the IF-THEN-ELSE construction common to computer science, together with the four of the operators of primitive recursive function
s: zero, successor, equality of numbers and composition. The conditional operator replaces both primitive recursion and the mu-operator.
in his §10.6 Conditional Expressions: The McCarthy Formalism describes the "formalism" as follows:
Minsky uses the following operators in his demonstrations:
From these he shows how to derive the predecessor function (i.e. DECREMENT); with this tool he derives the minimization operator necessary for "general" recursion
, as well as primitive-recursive definitions.
In other words, given a "basis" function (it can be a constant such as 0), primitive recursion uses either the base or the previous value of the function to produce the value of the function; primitive recursion is sometimes called mathematical induction
Minsky (above) is describing a two-CASE operator. A demonstration that the nested IF-THEN-ELSE—the "case statement" (or "switch statement")--is primitive recursive can be found in Kleene 1952:229 at "#F ('mutually-exclusive predicates')". The CASE operator behaves like a logical multiplexer
and is simply an extension of the simpler two-case logical operator sometimes called AND-OR-SELECT (see more at Propositional formula
). The CASE operator for three cases would be verbally described as: "If X is CASE 1 then DO "p" else if X is CASE 2 then do "q" else if X is CASE "3" then do "r" else do "default".
Boolos-Burgess-Jeffrey 2002 observe that in a particular instance the CASE operator, or a sequence of nested IF-THEN-ELSE statements, must be both mutually exclusive
, meaning that only one "case" holds (is true), and collectively exhaustive
, meaning every possible situation or "case" is "covered". These requirements are a consequence of the determinacy of Propositional logic; the correct implementation requires the use of truth table
s and Karnaugh map
s to specify and simplify the cases; see more at Propositional formula
. The authors point out the power of "definition by cases":
They prove, in particular, that the processes of substitution
, graph relation (similar to the identity relation that plucks out (the value of) a particular variable from a list of variables), negation
(logical NOT), conjunction
(logical AND), disjunction (logical OR), bounded universal quantification
, or bounded existential quantification
can be used together with definition by cases to create new primitive recursive functions (cf Boolos-Burgess-Jeffrey 2002:74-77).
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and recursion theory
Recursion theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
the McCarthy Formalism (1963) of computer
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
scientist John McCarthy
John McCarthy (computer scientist)
John McCarthy was an American computer scientist and cognitive scientist. He coined the term "artificial intelligence" , invented the Lisp programming language and was highly influential in the early development of AI.McCarthy also influenced other areas of computing such as time sharing systems...
clarifies the notion of recursive function
Recursive function
Recursive function may refer to:*Recursion , a procedure or subroutine, implemented in a programming language, whose implementation references itself*A total computable function, a function which is defined for all possible inputs...
s by use of the IF-THEN-ELSE construction common to computer science, together with the four of the operators of primitive recursive function
Primitive recursive function
The primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict subset of the total µ-recursive functions...
s: zero, successor, equality of numbers and composition. The conditional operator replaces both primitive recursion and the mu-operator.
McCarthy's notion of conditional expression
McCarthy (1960) described his formalism this way:- "In this article, we first describe a formalism for defining recursively. We believe this formalism has advantages both as a programming language and as a vehicle for developing a theory of computation....
- " We shall need a number of mathematical ideas and notations concerning functions in general. Most of the ideas are well known, but the notion of conditional expression is believed to be new, and the use of conditional expressions permits functions to be defined recursively in a new and convenient way."
Minsky's explanation of the "formalism"
In his 1967 Computation: Finite and Infinite Machines, Marvin MinskyMarvin Minsky
Marvin Lee Minsky is an American cognitive scientist in the field of artificial intelligence , co-founder of Massachusetts Institute of Technology's AI laboratory, and author of several texts on AI and philosophy.-Biography:...
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.
- This conditional expression . . . has also the power of the minimization operator. . ..
- 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)
Minsky uses the following operators in his demonstrations:
- Zero
- Successor
- Equality of numbers
- Composition (substitution, replacement, assignment)
- Conditional expression
From these he shows how to derive the predecessor function (i.e. DECREMENT); with this tool he derives the minimization operator necessary for "general" recursion
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
, as well as primitive-recursive definitions.
Expansion of IF-THEN-ELSE to the CASE operator
In his 1952 Introduction of Meta-Mathematics Stephen Kleene provides a definition of what it means to be a primitive recursive function:- "A function φ is primitive recursive in ψ1, ...,ψl (briefly Ψ), if there is a finite sequence φ1, ...,φk of (occurrences of) functions ... such that each function of the sequence is either one of the functions Ψ (the assumed functions), or an initial function, or an immediate dependent of preceding functions, and the last function φk is φ." (Kleene 1952:224)
In other words, given a "basis" function (it can be a constant such as 0), primitive recursion uses either the base or the previous value of the function to produce the value of the function; primitive recursion is sometimes called mathematical induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
Minsky (above) is describing a two-CASE operator. A demonstration that the nested IF-THEN-ELSE—the "case statement" (or "switch statement")--is primitive recursive can be found in Kleene 1952:229 at "#F ('mutually-exclusive predicates')". The CASE operator behaves like a logical multiplexer
Multiplexer
In electronics, a multiplexer is a device that selects one of several analog or digital input signals and forwards the selected input into a single line. A multiplexer of 2n inputs has n select lines, which are used to select which input line to send to the output...
and is simply an extension of the simpler two-case logical operator sometimes called AND-OR-SELECT (see more at Propositional formula
Propositional formula
In propositional logic, a propositional formula is a type of syntactic formula which is well formed and has a truth value. If the values of all variables in a propositional formula are given, it determines a unique truth value...
). The CASE operator for three cases would be verbally described as: "If X is CASE 1 then DO "p" else if X is CASE 2 then do "q" else if X is CASE "3" then do "r" else do "default".
Boolos-Burgess-Jeffrey 2002 observe that in a particular instance the CASE operator, or a sequence of nested IF-THEN-ELSE statements, must be both mutually exclusive
Mutually exclusive
In layman's terms, two events are mutually exclusive if they cannot occur at the same time. An example is tossing a coin once, which can result in either heads or tails, but not both....
, meaning that only one "case" holds (is true), and collectively exhaustive
Collectively exhaustive
In probability theory, a set of events is jointly or collectively exhaustive if at least one of the events must occur. For example, when rolling a six-sided die, the outcomes 1, 2, 3, 4, 5, and 6 are collectively exhaustive, because they encompass the entire range of possible outcomes.Another way...
, meaning every possible situation or "case" is "covered". These requirements are a consequence of the determinacy of Propositional logic; the correct implementation requires the use of truth table
Truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...
s and Karnaugh map
Karnaugh map
The Karnaugh map , Maurice Karnaugh's 1953 refinement of Edward Veitch's 1952 Veitch diagram, is a method to simplify Boolean algebra expressions...
s to specify and simplify the cases; see more at Propositional formula
Propositional formula
In propositional logic, a propositional formula is a type of syntactic formula which is well formed and has a truth value. If the values of all variables in a propositional formula are given, it determines a unique truth value...
. The authors point out the power of "definition by cases":
- "...in more complicated examples, definition by cases makes it far easier to establish the (primitive) recursiveness of important functions. This is mainly because there are a variety of processes for defining new relations from old that can be shown to produce new (primitive) recursive relations when applied to (primitive) recursive relations." (Boolos-Burgess-Jeffrey 2002:74)
They prove, in particular, that the processes of substitution
Substitution
Substitution may refer to:- Sciences :* Substitution , a syntactic transformation on strings of symbols of a formal language* Substitution of variables* Substitution cipher, a method of encryption...
, graph relation (similar to the identity relation that plucks out (the value of) a particular variable from a list of variables), negation
Negation
In logic and mathematics, negation, also called logical complement, is an operation on propositions, truth values, or semantic values more generally. Intuitively, the negation of a proposition is true when that proposition is false, and vice versa. In classical logic negation is normally identified...
(logical NOT), conjunction
Logical conjunction
In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....
(logical AND), disjunction (logical OR), bounded universal quantification
Universal quantification
In predicate logic, universal quantification formalizes the notion that something is true for everything, or every relevant thing....
, or bounded existential quantification
Existential quantification
In predicate logic, an existential quantification is the predication of a property or relation to at least one member of the domain. It is denoted by the logical operator symbol ∃ , which is called the existential quantifier...
can be used together with definition by cases to create new primitive recursive functions (cf Boolos-Burgess-Jeffrey 2002:74-77).