stringtranslate.com

Formalismo macartista

En informática y teoría de la recursión, el Formalismo 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 a la recursión primitiva como al operador mu .

Introducción

La noción de McCarthy deexpresión condicional

McCarthy (1960) describió su formalismo de esta manera: [1]

"En este artículo, describimos primero un formalismo para definir funciones de forma recursiva. Creemos que este formalismo tiene ventajas tanto como lenguaje de programación como vehículo 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 las ideas son bien conocidas, pero se cree que la noción de expresión condicional es nueva, y el uso de expresiones condicionales permite definir funciones recursivamente de una manera nueva y conveniente.

La explicación de Minsky sobre el “formalismo”

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

"Los lenguajes informáticos 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 realza 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 1 entonces e 1 de lo contrario e 2 )
donde e i son expresiones y p 1 es un enunciado (o ecuación) que puede ser verdadero o falso. ¶ Esta expresión significa
Vea si p 1 es verdadero; si es así, el valor de f viene dado por e 1 .
SI p1 es falso, el valor de f viene dado por e 2 .
Esta expresión condicional . . . también tiene el poder del operador de minimización. . ..
El formalismo McCarthy es como el sistema recursivo general (Kleene), al estar basado en algunas funciones básicas, composición e igualdad, pero con la expresión condicional por sí sola reemplazando tanto al esquema primitivo-recursivo como al operador de minimización. (Minsky 1967:192-193)

Minsky utiliza los siguientes operadores en sus demostraciones: [2]

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

Expansión de IF-THEN-ELSE al operador CASE

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:

"Una función φ es recursiva primitiva en ψ 1 , ..., ψ k (brevemente Ψ ), si hay una secuencia finita φ 1 , ..., φ k de (ocurrencias de) funciones ... tales que cada función de la secuencia es una de las funciones Ψ (las funciones supuestas), o una función inicial, o una función dependiente inmediata de funciones precedentes, y la última función φ k es φ ." (Kleene 1952:224)

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

Minsky (arriba) describe un operador de dos casos. Una demostración de que el IF-THEN-ELSE anidado (la " declaración de caso " o "declaración switch") es recursivo primitivo se puede encontrar en Kleene 1952:229 [4] 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 CASE 1 entonces HAGA "p" de lo contrario si X es CASE 2 entonces haga "q" de lo contrario si X es CASE "3" entonces haga "r" de lo contrario haga "default".

Boolos-Burgess-Jeffrey 2002 observan que en un caso particular el operador CASE, o una secuencia de instrucciones IF-THEN-ELSE anidadas, deben ser mutuamente excluyentes , lo que significa que solo se cumple un "caso" (es verdadero), y colectivamente exhaustivos , lo que significa que cada situación o "caso" posible está "cubierto". Estos requisitos son una consecuencia de la determinación 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; vea más en Fórmula proposicional . Los autores señalan el poder de la "definición por casos":

"...en ejemplos más complicados, la definición por casos hace mucho más fácil establecer la recursividad (primitiva) de funciones importantes. Esto se debe principalmente a que existe una variedad de procesos para definir nuevas relaciones a partir de las antiguas que pueden demostrar que producen nuevas relaciones recursivas (primitivas) cuando se aplican a 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 de identidad que extrae (el valor de) una variable particular de una lista de variables), negación (NO lógico), conjunción (Y lógico), disyunción (O lógico), cuantificación universal acotada o cuantificación existencial acotada pueden usarse 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

  1. ^ McCarthy 1960.
  2. ^ Minsky (1967) no incluye el operador identidad en su descripción de funciones recursivas primitivas . No se sabe por qué ocurre esto.
  3. ^ Varios autores utilizan distintos nombres para esta operación. Kleene la llama: "el esquema de definición por sustitución . La expresión para el valor ambiguo de φ se obtiene por sustitución de expresiones para los valores ambiguos de χ 1 , . . ., χ m por las variables de ψ . . .. la función φ definida por una aplicación de este esquema a veces la escribimos como t S m n (ψ, 1 , . . ., χ m ." (Kleene 1952:220). Knuth la llama la " operación de reemplazo importantísima (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 debe reemplazarse por el valor actual de la variable n " (cf Knuth 1973:3).
  4. ^ El "esquema" de recursión primitiva de cinco de Kleene incluye 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