stringtranslate.com

Cálculo combinador de esquí

El cálculo combinador SKI es un sistema lógico combinatorio y un sistema computacional . Puede considerarse un lenguaje de programación de computadoras, aunque no es conveniente para escribir software. En cambio, es importante en la teoría matemática de los algoritmos porque es un lenguaje completo de Turing extremadamente simple . Puede compararse con una versión reducida del cálculo lambda sin tipo . Fue introducido por Moses Schönfinkel [1] y Haskell Curry . [2]

Todas las operaciones en el cálculo lambda se pueden codificar mediante eliminación de abstracciones en el cálculo SKI como árboles binarios cuyas hojas son uno de los tres símbolos S , K e I (llamados combinadores ).

Notación

Aunque la representación más formal de los objetos en este sistema requiere árboles binarios, para una composición tipográfica más simple a menudo se representan como expresiones entre paréntesis, como una abreviatura del árbol que representan. Cualquier subárbol puede estar entre paréntesis, pero a menudo solo los subárboles del lado derecho están entre paréntesis, con asociatividad izquierda implícita para cualquier aplicación sin paréntesis. Por ejemplo, ISK significa (( IS ) K ). Usando esta notación, un árbol cuyo subárbol izquierdo es el árbol KS y cuyo subárbol derecho es el árbol SK se puede escribir como KS ( SK ). Si se desea ser más explícito, también se pueden incluir los paréntesis implícitos: (( KS )( SK )).

descripción informal

De manera informal, y usando la jerga del lenguaje de programación, se puede considerar un árbol ( xy ) como una función x aplicada a un argumento y . Cuando se evalúa ( es decir , cuando la función se "aplica" al argumento), el árbol "devuelve un valor", es decir , se transforma en otro árbol. La "función", el "argumento" y el "valor" son combinadores o árboles binarios. Si son árboles binarios, también se pueden considerar funciones, si es necesario.

La operación de evaluación se define de la siguiente manera:

( x , y y z representan expresiones hechas a partir de las funciones S , K e I y establecen valores):

Me devuelve su argumento:

yo x = x

K , cuando se aplica a cualquier argumento x , produce una función constante de un argumento K x , que, cuando se aplica a cualquier argumento y , devuelve x :

K x y = x

S es un operador de sustitución. Toma tres argumentos y luego devuelve el primer argumento aplicado al tercero, que luego se aplica al resultado del segundo argumento aplicado al tercero. Mas claro:

S xyz = xz ( yz )

Ejemplo de cálculo: SKSK se evalúa como KK ( SK ) según la regla S. Entonces, si evaluamos KK ( SK ), obtenemos K según la regla K. Como no se puede aplicar ninguna otra regla, el cálculo se detiene aquí.

Para todos los árboles x y todos los árboles y , SK xy siempre se evaluará como y en dos pasos, K y ( xy ) = y , por lo que el resultado final de evaluar SK xy siempre será igual al resultado de evaluar y . Decimos que SK x e I son "funcionalmente equivalentes" porque siempre producen el mismo resultado cuando se aplican a cualquier y .

A partir de estas definiciones se puede demostrar que el cálculo SKI no es el sistema mínimo que puede realizar completamente los cálculos del cálculo lambda, ya que todas las apariciones de I en cualquier expresión pueden reemplazarse por ( SKK ) o ( SKS ) o ( SK lo que sea ) y la expresión resultante arrojará el mismo resultado. Así que el " yo " es meramente azúcar sintáctico . Dado que I es opcional, el sistema también se denomina cálculo SK o cálculo combinador SK .

Es posible definir un sistema completo utilizando un solo combinador (impropio). Un ejemplo es el combinador iota de Chris Barker , que se puede expresar en términos de S y K de la siguiente manera:

ι x = x SK

Es posible reconstruir S , K e I a partir del combinador de iota. Al aplicar ι a sí mismo se obtiene ιι = ι SK = SSKK = SK ( KK ) que es funcionalmente equivalente a I. K se puede construir aplicando ι dos veces a I (lo que equivale a la aplicación de ι a sí mismo): ι(ι(ιι)) = ι(ιι SK ) = ι( ISK ) = ι( SK ) = SKSK = K . Aplicar ι una vez más da ι(ι(ι(ιι))) = ι K = KSK = S .

Definicion formal

Los términos y derivaciones de este sistema también se pueden definir más formalmente:

Términos : El conjunto T de términos se define recursivamente mediante las siguientes reglas.

  1. S , K y I son términos.
  2. Si τ 1 y τ 2 son términos, entonces (τ 1 τ 2 ) es un término.
  3. Nada es un término si no así lo exigen las dos primeras reglas.

Derivaciones : Una derivación es una secuencia finita de términos definidos recursivamente por las siguientes reglas (donde α y ι son palabras sobre el alfabeto { S , K , I , (, )} mientras que β, γ y δ son términos):

  1. Si Δ es una derivación que termina en una expresión de la forma α( I β)ι, entonces Δ seguido del término αβι es una derivación.
  2. Si Δ es una derivación que termina en una expresión de la forma α(( K β)γ)ι, entonces Δ seguido del término αβι es una derivación.
  3. Si Δ es una derivación que termina en una expresión de la forma α((( S β)γ)δ)ι, entonces Δ seguido del término α((βδ)(γδ))ι es una derivación.

Suponiendo que, para empezar, una secuencia es una derivación válida, se puede ampliar utilizando estas reglas. Todas las derivaciones de longitud 1 son derivaciones válidas.

Expresiones de ESQUÍ

Autoaplicación y recursividad

SII es una expresión que toma un argumento y lo aplica a sí mismo:

SII α = Yo α( Yo α) = αα

Esto también se conoce como combinador U , U x = xx . Una propiedad interesante es que su autoaplicación es irreductible:

SII ( SII ) = I ( SII )( I ( SII )) = SII ( I ( SII )) = SII ( SII )

O, usando la ecuación directamente como definición, obtenemos inmediatamente U U = U U .

Otra cosa es que permite escribir una función que aplica una cosa a la autoaplicación de otra:

( S ( K α)( SII ))β = K αβ( SII β) = α( I β( I β)) = α(ββ)

o puede considerarse que define otro combinador directamente, H xy = x ( yy ).

Esta función se puede utilizar para lograr la recursividad . Si β es la función que aplica α a la autoaplicación de otra cosa,

β = H α = S ( K α)( SII )

entonces la autoaplicación de este β es el punto fijo de ese α:

SII β = ββ = α(ββ) = α(α(ββ)) =

O, directamente de nuevo de la definición derivada, H α( H α) = α( H α( H α)).

Si α expresa un "paso computacional" calculado por αρν para algunos ρ y ν, eso supone que ρν' expresa "el resto del cálculo" (para algunos ν' que α "calculará" a partir de ν), entonces su punto fijo ββ expresa todo el cálculo recursivo, ya que usar la misma función ββ para la llamada del "resto del cálculo" (con ββν = α(ββ)ν) es la definición misma de recursividad: ρν' = ββν' = α(ββ)ν' = . ... . α tendrá que emplear algún tipo de condicional para detenerse en algún "caso base" y no realizar la llamada recursiva en ese momento, para evitar la divergencia.

Esto se puede formalizar, con

β = H α = S ( K α)( SII ) = S ( KS ) K α( SII ) = S ( S ( KS ) K )( K ( SII )) α

como

Y α = SII β = SII ( H α) = S ( K ( SII )) H α = S ( K ( SII ))( S ( S ( KS ) K )( K ( SII ))) α

lo que nos da una posible codificación del combinador Y.

Esto se vuelve mucho más corto con el uso de los combinadores B y C , ya que el equivalente

Y α = S ( KU )( SB ( KU ))α = U ( B α U ) = BU ( CBU )α

o directamente, como

H αβ = α(ββ) = B α U β = CBU αβ
Y α = U ( H α) = BU ( CBU )α

Y con una sintaxis pseudo- Haskell se convierte en el excepcionalmente corto Y = U. (. U ).

La expresión inversa

S ( K ( SI )) K invierte los dos términos siguientes:

S ( K ( SI )) K αβ →
K ( SI )α( K α)β →
SI ( K α)β →
Yo β( K αβ) →
Yo βα →
βα

lógica booleana

El cálculo combinador SKI también puede implementar la lógica booleana en forma de una estructura si-entonces-si no . Una estructura if-then-else consta de una expresión booleana que es verdadera ( T ) o falsa ( F ) y dos argumentos, tales que:

Txy = x​

y

F xy = y

La clave está en definir las dos expresiones booleanas. El primero funciona igual que uno de nuestros combinadores básicos:

T = K
K x y = x

El segundo también es bastante sencillo:

F = SK
SK xy = K y(xy) = y

Una vez que se definen verdadero y falso, toda la lógica booleana se puede implementar en términos de estructuras si-entonces-si no .

El NOT booleano (que devuelve el opuesto de un booleano dado) funciona igual que la estructura if-then-else , con F y T como segundo y tercer valor, por lo que se puede implementar como una operación de sufijo:

NO = ( F )( T ) = ( SK )( K )

Si esto se coloca en una estructura if-then-else , se puede demostrar que tiene el resultado esperado.

( T ) NO = T ( F )( T ) = F
( F ) NO = F ( F )( T ) = T

El OR booleano (que devuelve T si cualquiera de los dos valores booleanos que lo rodean es T ) funciona igual que una estructura if-then-else con T como segundo valor, por lo que se puede implementar como una operación infija:

O = T = K

Si esto se coloca en una estructura if-then-else , se puede demostrar que tiene el resultado esperado:

( T ) O ( T ) = T ( T )( T ) = T
( T ) O ( F ) = T ( T )( F ) = T
( F ) O ( T ) = F ( T )( T ) = T
( F ) O ( F ) = F ( T )( F ) = F

El AND booleano (que devuelve T si los dos valores booleanos que lo rodean son T ) funciona igual que una estructura if-then-else con F como tercer valor, por lo que se puede implementar como una operación de sufijo:

Y = F = SK

Si esto se coloca en una estructura if-then-else , se puede demostrar que tiene el resultado esperado:

( T )( T ) Y = T ( T )( F ) = T
( T )( F ) Y = T ( F )( F ) = F
( F )( T ) Y = F ( T )( F ) = F
( F )( F ) Y = F ( F )( F ) = F

Debido a que esto define T , F , NOT (como operador postfijo), OR (como operador infijo) y AND (como operador postfijo) en términos de notación SKI, esto demuestra que el sistema SKI puede expresar completamente la lógica booleana.

Una vez completado el cálculo SKI , también es posible expresar NOT , OR y AND como operadores de prefijo:

NO = S ( SI ( KF ))( KT ) (como S ( SI ( KF ))( KT ) x = SI ( KF ) x ( KT x ) = I x ( KF x ) T = x FT )
O = SI ( KT ) (como SI ( KT ) xy = I x ( KT x ) y = x T y )
Y = SS ( K ( KF )) (como SS ( K ( KF )) xy = S x ( K ( KF ) x ) y = xy ( KF y ) = xy F )

Conexión con la lógica intuicionista

Los combinadores K y S corresponden a dos axiomas bien conocidos de la lógica oracional :

AK : A → ( B → A ) ,
COMO : ( A → ( B → C )) → (( A → B ) → ( A → C )) .

La aplicación de la función corresponde a la regla modus ponens :

MP :de A y A → B , inferir B.

Los axiomas AK y AS y la regla MP están completos para el fragmento implicacional de la lógica intuicionista . Para que la lógica combinatoria tenga como modelo:

Esta conexión entre los tipos de combinadores y los axiomas lógicos correspondientes es un ejemplo del isomorfismo de Curry-Howard .

Ejemplos de reducción

Puede haber varias formas de realizar una reducción. Todos son equivalentes, siempre y cuando no se rompa el orden de las operaciones.

Ver también

Referencias

  1. ^ Schönfinkel, M. (1924). "Über die Bausteine ​​der mathematischen Logik". Annalen Matemáticas . 92 (3–4): 305–316. doi :10.1007/BF01448013. S2CID  118507515.Traducido por Stefan Bauer-Mengelberg como van Heijenoort, Jean , ed. (2002) [1967]. "Sobre los componentes básicos de la lógica matemática". Un libro de consulta sobre lógica matemática 1879-1931 . Prensa de la Universidad de Harvard. págs. 355–366. ISBN 9780674324497.
  2. ^ Curry, Haskell Brooks (1930). "Grundlagen der Kombinatorischen Logik" [Fundamentos de la lógica combinatoria]. Revista Estadounidense de Matemáticas (en alemán). Prensa de la Universidad Johns Hopkins. 52 (3): 509–536. doi :10.2307/2370619. JSTOR  2370619.

enlaces externos