La 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]
Utilizando los combinadores K y S de la lógica combinatoria , las funciones lógicas se pueden representar como funciones de combinadores:
< término > ::= 00 | 01 | 1 < término > < término >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 los subtérminos de un término dado, analizando desde la izquierda:
1100xy → x 11101xyz → 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 .