En informática y teoría de la recursión, el Formalismo McCarthy (1963) del científico informático John McCarthy aclara la noción de funciones recursivas mediante el uso de la construcción IF-THEN-ELSE común a la informática, junto con cuatro de los operadores de funciones recursivas primitivas : cero , sucesor, igualdad de número y composición. El operador condicional reemplaza tanto la recursividad primitiva como el operador mu .
En su Computación de 1967 : Máquinas finitas e infinitas , Marvin Minsky en su § 10.6 Expresiones condicionales: El formalismo de McCarthy describe el "formalismo" de la siguiente manera:
A partir de estos, muestra cómo derivar la función predecesora (es decir, DECRECIMIENTO); con esta herramienta deriva el operador de minimización necesario para la recursividad "general" , así como definiciones recursivas primitivas.
En su Introducción a las metamatemáticas de 1952 , Stephen Kleene proporciona una definición de lo que significa ser una función recursiva primitiva:
En otras palabras, dada una función "base" (puede ser una constante como 0), la recursión primitiva usa la base o el valor anterior de la función para producir el valor de la función; La recursividad primitiva a veces se llama inducción matemática.
Minsky (arriba) está describiendo un operador de dos CASO. En Kleene 1952:229 [3] en " #F ( 'predicados mutuamente excluyentes ' )". El operador CASE se comporta como un multiplexor lógico y es simplemente una extensión del operador lógico de dos casos más simple, a veces llamado AND-OR-SELECT (ver más en Fórmula proposicional ). El operador CASO para tres casos se describiría verbalmente como: "Si X es CASO 1, entonces HAGA "p"; de lo contrario, si X es CASO 2, entonces haga "q"; de lo contrario, si X es CASO "3", entonces haga "r"; de lo contrario, haga " defecto".