Hispanopedia WikiLa lógica combinatoria binaria ( BCL ) es un lenguaje de programación informática que utiliza los términos binarios 0 y 1 para crear una formulación completa de lógica combinatoria utilizando únicamente los símbolos 0 y 1. [1] Utilizando los combinadores S y K, se pueden crear funciones complejas de álgebra booleana. BCL 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 se pueden representar como funciones de combinadores:
Sintaxis
< término > ::= 00 | 01 | 1 < término > < término >
Semántica
La semántica denotacional de BCL puede especificarse de la siguiente manera:
[ 00 ] == K[ 01 ] == S[ 1 <term1> <term2> ] == ( [<term1>] [<term2>] )
donde " [...]" abrevia "el significado de ...". Aquí Ky Sson los combinadores de base KS , y ( )es la operación de aplicación de la lógica combinatoria . (El prefijo 1corresponde a un paréntesis izquierdo, siendo innecesario el paréntesis derecho para la desambiguación).
Por lo tanto, existen cuatro formulaciones equivalentes de BCL, dependiendo de la manera de codificar el triplete (K, S, paréntesis izquierdo). Estas son (00, 01, 1)(como en la versión actual), (01, 00, 1), (10, 11, 0)y (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 manera muy compacta mediante las siguientes reglas de reescritura para subtérminos de un término dado, analizando desde la izquierda:
1100xy → x11101xyz → 11xz1yz
donde x, y, y zson subtérminos arbitrarios. (Tenga en cuenta, por ejemplo, que debido a que el análisis se realiza desde la izquierda, 10000no es un subtérmino de 11010000).
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
- ^ ab Tromp, John (2007), "Cálculo lambda binario y lógica combinatoria", Aleatoriedad y complejidad (PDF) , World Sci. Publ., Hackensack, NJ, págs. 237–260, CiteSeerX 10.1.1.695.3142 , doi :10.1142/9789812770837_0014, ISBN 978-981-277-082-0, Sr. 2427553.
- ^ Devine, Sean (2009), "Las ideas de la entropía algorítmica", Entropy , 11 (1): 85–110, Bibcode :2009Entrp..11...85D, doi : 10.3390/e11010085 , MR 2534819
- ^ abc Wolfram, Stephen (6 de diciembre de 2021). "Combinadores: una visión centenaria". writings.stephenwolfram.com . Archivado desde el original el 6 de diciembre de 2020 . Consultado el 17 de febrero de 2021 .
Lectura adicional
- 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.
Enlaces externos
- Patio de juegos de cálculo lambda y lógica combinatoria de John
- Una implementación mínima en C
- Cálculo Lambda en 383 Bytes
- Brauner, Paul. "Lista de reproducción de diagramas Lambda para YouTube". YouTube . Archivado desde el original el 21 de diciembre de 2021.
