Formalismo de McCarthy

En informática y teoría de la recursión, el formalismo de McCarthy (1963), del informático John McCarthy, clarifica la noción de funciones recursivas mediante el uso de la construcción IF-THEN-ELSE, común en informática, junto con cuatro de los operadores de funciones recursivas primitivas : cero, sucesor, igualdad de números y composición. El operador condicional reemplaza tanto la recursión primitiva como el operador mu .

Introducción

La noción de expresión condicional de McCarthy

McCarthy presentó una propuesta para expresiones condicionales en IAL , que se publicó como una "Carta al editor" en 1959. ^{[ 1 ]} Posteriormente, McCarthy describió su formalismo de esta manera: ^{[ 2 ]}

En este artículo, describimos en primer lugar un formalismo para definir funciones de forma recursiva. Creemos que este formalismo presenta ventajas tanto como lenguaje de programación como herramienta para desarrollar una teoría de la computación.

Necesitaremos una serie de ideas y notaciones matemáticas relativas a las funciones en general. La mayoría de estas ideas son bien conocidas, pero se cree que la noción de expresión condicional es novedosa, y su uso permite definir funciones de forma recursiva de una manera nueva y práctica.

La explicación de Minsky sobre el "formalismo"

En el libro de Marvin Minsky de 1967 , Computation: Finite and Infinite Machines , § 10.7 Conditional Expressions: The McCarthy Formalism , describe el "formalismo" de la siguiente manera:

"Los lenguajes de programación prácticos no se prestan a un tratamiento matemático formal; no están diseñados para facilitar la demostración de teoremas sobre los procedimientos que describen. En un artículo de McCarthy [1963] encontramos un formalismo que mejora el aspecto práctico del concepto de función recursiva, al tiempo que preserva y mejora su claridad matemática. ¶ McCarthy introduce "expresiones condicionales" de la forma

f = ( si p ₁entonces e ₁sino e ₂ )

donde e _i son expresiones y p ₁ es una afirmación (o ecuación) que puede ser verdadera o falsa. ¶ Esta expresión significa

Comprueba si p ₁ es verdadera; si lo es, el valor de f viene dado por e ₁ .

SI p1 es falso, el valor de f viene dado por e ₂ .

Esta expresión condicional... también tiene el poder del operador de minimización...

El formalismo de McCarthy es similar al sistema recursivo general (Kleene), ya que se basa en algunas funciones básicas, composición e igualdad, pero con la expresión condicional reemplazando tanto el esquema recursivo primitivo como el operador de minimización. (Minsky 1967:192-193)

Minsky utiliza los siguientes operadores en sus demostraciones: ^{[ 3 ]}

Cero
Sucesor
Igualdad de números
Composición (sustitución, reemplazo, asignación) ^{[ 4 ]}
Expresión condicional

A partir de estos, muestra cómo derivar la función predecesora (es decir, DECREMENTAR); con esta herramienta deriva el operador de minimización necesario para la recursión "general" , así como definiciones recursivas primitivas.

Ampliación de IF-THEN-ELSE al operador CASE.

En su obra de 1952, Introducción a las metamatemáticas, Stephen Kleene proporciona una definición de lo que significa ser una función recursiva primitiva:

"Una función

φ

es recursiva primitiva en

ψ 1, ..., ψ k

(brevemente Ψ ), si existe una secuencia finita

φ 1, ..., φ k

de (ocurrencias de) funciones ... tal que cada función de la secuencia es una de las funciones Ψ (las funciones supuestas), o una función inicial, o una dependiente inmediata de las funciones precedentes, y la última función

φ k

es

φ

." (Kleene 1952:224)

En otras palabras, dada una función "base" (que puede ser una constante como 0), la recursión primitiva utiliza la base o el valor anterior de la función para producir su valor; a la recursión primitiva a veces se la denomina inducción matemática.

Minsky (arriba) está describiendo un operador CASE de dos casos. Una demostración de que la instrucción IF-THEN-ELSE anidada —la " instrucción case " (o "instrucción switch")— es recursiva primitiva se puede encontrar en Kleene 1952:229 ^{[ 5 ]} 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 CASE para tres casos se describiría verbalmente como: "Si X es CASO 1 entonces HACER "p" sino si X es CASO 2 entonces hacer "q" sino si X es CASO "3" entonces hacer "r" sino hacer "predeterminado".

Boolos-Burgess-Jeffrey (2002) observan que, en un caso particular, el operador CASE, o una secuencia de sentencias IF-THEN-ELSE anidadas, debe ser mutuamente excluyente , lo que significa que solo un "caso" es verdadero, y colectivamente exhaustivo , lo que significa que cada situación o "caso" posible está "cubierto". Estos requisitos son consecuencia de la determinatividad de la lógica proposicional ; la implementación correcta requiere el uso de tablas de verdad y mapas de Karnaugh para especificar y simplificar los casos; véase más en Fórmula proposicional . Los autores destacan el poder de la "definición por casos":

«...en ejemplos más complejos, la definición por casos facilita enormemente el establecimiento de la recursividad (primitiva) de funciones importantes. Esto se debe principalmente a que existen diversos procesos para definir nuevas relaciones a partir de las antiguas que, al aplicarse a relaciones recursivas (primitivas), pueden demostrarse que producen nuevas relaciones recursivas (primitivas).» (Boolos-Burgess-Jeffrey 2002:74)

Demuestran, en particular, que los procesos de sustitución , relación gráfica (similar a la relación identidad que extrae (el valor de) una variable particular de una lista de variables), negación (NO lógico), conjunción (AND lógico), disyunción (OR lógico), cuantificación universal acotada o cuantificación existencial acotada pueden utilizarse junto con la definición por casos para crear nuevas funciones recursivas primitivas (cf Boolos-Burgess-Jeffrey 2002:74-77).

Véase también

Notas

↑ McCarthy 1959 .
↑ McCarthy 1960 .
↑ Minsky (1967) no incluye el operador identidad en su descripción de funciones recursivas primitivas . Se desconoce el motivo.
↑ Varios autores utilizan distintos nombres para esta operación. Kleene la denomina: "el esquema de definición por sustitución . La expresión para el valor ambiguo de φ se obtiene mediante la sustitución de expresiones para los valores ambiguos de χ₁ , . . ., χ_m por las variables de ψ . . .. la función φ definida por una aplicación de este esquema a veces escribimos como ast S _mⁿ (ψ,₁ , . . ., χ_{m ." (Kleene 1952:220). Knuth la denomina la "operación}de reemplazo fundamental(a veces llamada asignación o sustitución )", y la simboliza con la flecha " ← ", por ejemplo, "m ← n" significa que el valor de la variable m se reemplazará por el valor actual de la variable n " (cf Knuth 1973:3).
↑
Los 5 "esquemas" de recursión primitiva de Kleene incluyen lo siguiente:
1. constante cero: 0 o puede ser 0()
2. sucesor: $S (0) = "1", S (1) = "2",$ etc.
3. proyección: $U i n (x 1, ..., x n) = x i$ , los $x i$ son "parámetros" fijos durante todo el cálculo, y $U i n$ proyecta uno de ellos, también se utiliza la notación $π i n (x 1, ..., x n) = x i$ .
4. sustitución $φ(x 1, ..., x n) = ψ(χ 1 (x 1, ..., x n), ..., χ m (x 1, ..., x n))$
5. recursión primitiva; cf. Kleene 1952:219.

Referencias

McCarthy, John (1959). "Cartas al editor" . Communications of the ACM . 2 (8): 2– 5. doi : 10.1145/368405.1773349 .
McCarthy, John (1960). "Funciones recursivas de expresiones simbólicas y su cálculo por máquina, parte I" . Communications of the ACM . 3 (4): 184– 195. doi : 10.1145/367177.367199 .
George S. Boolos , John P. Burgess y Richard C. Jeffrey , 2002, Computabilidad y lógica: cuarta edición , Cambridge University Press, Cambridge, Reino Unido, ISBN 0-521-00758-5libro de bolsillo.
John McCarthy (1963), Una base para una teoría matemática de la computación , Programación de computadoras y sistemas formales, págs. 33-70.
Marvin Minsky (1967), Computación: Máquinas finitas e infinitas , Prentice-Hall Inc, Englewood Cliffs, NJ.

[FOOTNOTEMcCarthy1959-1] McCarthy 1959 .

[FOOTNOTEMcCarthy1960-2] McCarthy 1960 .

[3] Minsky (1967) no incluye el operador identidad en su descripción de funciones recursivas primitivas . Se desconoce el motivo.

[4] Varios autores utilizan distintos nombres para esta operación. Kleene la denomina: "el esquema de definición por sustitución . La expresión para el valor ambiguo de φ se obtiene mediante la sustitución de expresiones para los valores ambiguos de χ₁ , . . ., χ_m por las variables de ψ . . .. la función φ definida por una aplicación de este esquema a veces escribimos como ast S _mⁿ (ψ,₁ , . . ., χ_{m ." (Kleene 1952:220). Knuth la denomina la "operación}de reemplazo fundamental(a veces llamada asignación o sustitución )", y la simboliza con la flecha " ← ", por ejemplo, "m ← n" significa que el valor de la variable m se reemplazará por el valor actual de la variable n " (cf Knuth 1973:3).

[5] Los 5 "esquemas" de recursión primitiva de Kleene incluyen lo siguiente:
constante cero: 0 o puede ser 0()
sucesor: $S (0) = "1", S (1) = "2",$ etc.
proyección: $U i n (x 1, ..., x n) = x i$ , los $x i$ son "parámetros" fijos durante todo el cálculo, y $U i n$ proyecta uno de ellos, también se utiliza la notación $π i n (x 1, ..., x n) = x i$ .
sustitución $φ(x 1, ..., x n) = ψ(χ 1 (x 1, ..., x n), ..., χ m (x 1, ..., x n))$
recursión primitiva; cf. Kleene 1952:219.

[mwsQ] stante cero: 0 o puede ser 0()

[mwsg] sucesor: $S (0) = "1", S (1) = "2",$ etc.

[mwtg] royección: $U i n (x 1, ..., x n) = x i$ , los $x i$ son "parámetros" fijos durante todo el cálculo, y $U i n$ proyecta uno de ellos, también se utiliza la notación $π i n (x 1, ..., x n) = x i$ .

[mw3A] sustitución $φ(x 1, ..., x n) = ψ(χ 1 (x 1, ..., x n), ..., χ m (x 1, ..., x n))$

[mw8A] recursión primitiva; cf. Kleene 1952:219.

[mwsQ] stante cero: 0 o puede ser 0()

[mwsg] sucesor: $S (0) = "1", S (1) = "2",$ etc.

[mwtg] royección: $U i n (x 1, ..., x n) = x i$ , los $x i$ son "parámetros" fijos durante todo el cálculo, y $U i n$ proyecta uno de ellos, también se utiliza la notación $π i n (x 1, ..., x n) = x i$ .

[mw3A] sustitución $φ(x 1, ..., x n) = ψ(χ 1 (x 1, ..., x n), ..., χ m (x 1, ..., x n))$

[mw8A] recursión primitiva; cf. Kleene 1952:219.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]