En el cálculo lambda , el teorema de Church-Rosser establece que, al aplicar reglas de reducción a términos , el orden en que se eligen las reducciones no afecta el resultado final.
Más precisamente, si hay dos reducciones o secuencias de reducciones distintas que pueden aplicarse al mismo término, entonces existe un término al que se puede llegar a partir de ambos resultados, aplicando secuencias (posiblemente vacías) de reducciones adicionales. [1] El teorema fue demostrado en 1936 por Alonzo Church y J. Barkley Rosser , de quienes recibe su nombre.
El teorema está simbolizado por el diagrama adyacente: Si el término a puede reducirse tanto a b como a c , entonces debe haber un término adicional d (posiblemente igual a b o a c ) al que tanto b como c puedan reducirse. Considerando el cálculo lambda como un sistema de reescritura abstracto , el teorema de Church-Rosser establece que las reglas de reducción del cálculo lambda son confluentes . Como consecuencia del teorema, un término en el cálculo lambda tiene como máximo una forma normal , lo que justifica la referencia a " la forma normal" de un término normalizable dado.
En 1936, Alonzo Church y J. Barkley Rosser demostraron que el teorema es válido para la β-reducción en el cálculo λI (en el que cada variable abstraída debe aparecer en el cuerpo del término). El método de prueba se conoce como "finitud de desarrollos" y tiene consecuencias adicionales, como el teorema de estandarización, que se relaciona con un método en el que se pueden realizar reducciones de izquierda a derecha para alcanzar una forma normal (si existe una). El resultado para el cálculo lambda puro sin tipo fue demostrado por DE Schroer en 1965. [2]
Un tipo de reducción en el cálculo lambda puro no tipificado para el que se aplica el teorema de Church-Rosser es la β-reducción, en la que un subtérmino de la forma se contrae mediante la sustitución . Si la β-reducción se denota por y su clausura reflexiva y transitiva por entonces el teorema de Church-Rosser es que: [3]
Una consecuencia de esta propiedad es que dos términos iguales en deben reducirse a un término común: [4]
El teorema también se aplica a la η-reducción, en la que un subtérmino se reemplaza por . También se aplica a la βη-reducción, la unión de las dos reglas de reducción.
Para la β-reducción, un método de prueba se origina de William W. Tait y Per Martin-Löf . [5] Digamos que una relación binaria satisface la propiedad del diamante si:
Entonces la propiedad de Church-Rosser es el enunciado que satisface la propiedad del diamante. Introducimos una nueva reducción cuyo cierre transitivo reflexivo es y que satisface la propiedad del diamante. Por inducción sobre el número de pasos en la reducción, se sigue que satisface la propiedad del diamante.
La relación tiene las reglas de formación:
Se puede demostrar que la regla de reducción η es directamente de Church-Rosser. Luego, se puede demostrar que la reducción β y la reducción η conmutan en el sentido de que: [6]
Por lo tanto, podemos concluir que la βη-reducción es de Church-Rosser. [7]
Una regla de reducción que satisface la propiedad de Church-Rosser tiene la propiedad de que cada término M puede tener como máximo una forma normal distinta, de la siguiente manera: si X e Y son formas normales de M entonces, por la propiedad de Church-Rosser, ambos se reducen a un término igual Z . Ambos términos ya son formas normales, por lo que . [4]
Si una reducción es fuertemente normalizante (no hay caminos infinitos de reducción), entonces una forma débil de la propiedad de Church-Rosser implica la propiedad completa (véase el lema de Newman ). La propiedad débil, para una relación , es: [8]
El teorema de Church-Rosser también es válido para muchas variantes del cálculo lambda, como el cálculo lambda de tipos simples , muchos cálculos con sistemas de tipos avanzados y el cálculo de valores beta de Gordon Plotkin . Plotkin también utilizó un teorema de Church-Rosser para demostrar que la evaluación de programas funcionales (tanto para la evaluación perezosa como para la evaluación ansiosa ) es una función de programas a valores (un subconjunto de los términos lambda).
En artículos de investigación más antiguos, se dice que un sistema de reescritura es Church-Rosser, o que tiene la propiedad de Church-Rosser, cuando es confluente .