Hispanopedia Wiki
Articulo de referencia

Lógica combinatoria binaria

La lógica combinatoria binaria ( LCB ) es un lenguaje de programación que utiliza los términos binarios 0 y 1 para crear una formulación completa de la lógica combinatoria emple...

Hispanopedia WikiContenido en espanolLectura gratuita

La lógica combinatoria binaria ( LCB ) es un lenguaje de programación que utiliza los términos binarios 0 y 1 para crear una formulación completa de la lógica combinatoria empleando únicamente los símbolos 0 y 1. [ 1 ] Mediante los combinadores S y K, se pueden construir funciones complejas del álgebra booleana. La LCB tiene aplicaciones en la teoría de la complejidad del tamaño del programa ( complejidad de Kolmogorov ). [ 1 ] [ 2 ]

Definición

Base SK

Utilizando los combinadores K y S de la lógica combinatoria , las funciones lógicas pueden representarse como funciones de combinadores:

Sintaxis

Forma Backus-Naur :

< término > ::= 00 | 01 | 1 < término > < término >

Semántica

La semántica denotacional de BCL se puede especificar de la siguiente manera:

  • [ 00 ] == K
  • [ 01 ] == S
  • [ 1 <term1> <term2> ] == ( [<term1>] [<term2>] )

donde " [...]" abrevia "el significado de ...". Aquí Ky Sson los combinadores base KS , y ( )es la operación de aplicación de la lógica combinatoria . (El prefijo 1corresponde a un paréntesis izquierdo; los paréntesis derechos son innecesarios para la desambiguación).

Así pues, existen cuatro formulaciones equivalentes de BCL, dependiendo de la forma de codificar el triplete (K,  S,  paréntesis izquierdo). Estas son (como en la presente versión), , , y .(00, 01, 1)(01, 00, 1)(10, 11, 0)(11, 10, 0)

La semántica operacional de BCL, aparte de la eta-reducción (que no es necesaria para la completitud de Turing ), puede especificarse de forma muy compacta mediante las siguientes reglas de reescritura para los subtérminos de un término dado, analizando desde la izquierda:

  •  1100xy  → x
  • 11101xyz → 11xz1yz

donde x, y, y zson subtérminos arbitrarios. (Nótese, por ejemplo, que como el análisis sintáctico se realiza desde la izquierda, 10000no es un subtérmino de 11010000).

Un paso de la Regla 110 Autómatas celulares en SK-Basis (escrito en el lenguaje Wolfram ). [ 3 ]

BCL se puede utilizar para replicar algoritmos como máquinas de Turing y autómatas celulares , [ 3 ] BCL es Turing completo .

Véase también

Referencias

  1. 1 2 Tromp, John (2007), "Cálculo lambda binario y lógica combinatoria", Aleatoriedad y complejidad (PDF) , World Sci. Publ., Hackensack, NJ, pp. 237–260 , CiteSeerX 10.1.1.695.3142 , doi : 10.1142/9789812770837_0014 , ISBN   978-981-277-082-0, MR 2427553 .
  2. ↑ Devine, Sean (2009), "The insights of algorithmic entropy", Entropy , 11 (1): 85– 110, Bibcode : 2009Entrp..11...85D , doi : 10.3390/e11010085 , MR 2534819 
  3. 1 2 3 Wolfram, Stephen (2021-12-06). "Combinadores: Una visión centenaria" . writings.stephenwolfram.com . arXiv : 2103.12811 . Archivado del original el 2020-12-06 . Recuperado el 2021-02-17 .

Lecturas adicionales

  • Tromp, John (octubre de 2007). «Cálculo lambda binario y lógica combinatoria» . Aleatoriedad y complejidad, de Leibniz a Chaitin : 237-260 . doi : 10.1142/9789812770837_0014 . ISBN 978-981-277-082-0.
  • Tromp, John (abril de 2023). "Functional Bits: Lambda Calculus based Algorithmic Information Theory" (PDF) . tromp.github.io.
  • El espacio de experimentación de John sobre cálculo lambda y lógica combinatoria
  • Una implementación mínima en C
  • Cálculo Lambda en 383 Bytes
  • Brauner, Paul (10 de enero de 2018). "Lista de reproducción de diagramas Lambda en YouTube" . YouTube . Archivado del original el 21 de diciembre de 2021.