El teorema de la Iglesia-Rosser del indica que si hay dos reducciones distintas a partir de el mismo término en el cálculo de la lambda, después existe un término que sea accesible vía la secuencia de a (posiblemente vacía) de reducciones de ambos reducts. Por consiguiente, un término en el cálculo de la lambda tiene a lo más una forma normal . Es así el teorema de la Iglesia-Rosser que justifica referencias al " el form" del normal de ; de cierto término. El teorema fue probado en 1936 por la iglesia de Alonzo y el J.

El teorema de la Iglesia-Rosser también se sostiene para muchas variantes del cálculo de la lambda, tales como cálculo del beta-valor de s de Plotkin cálculo simple-mecanografiado de la lambda, muchos cálculos con el tipo avanzado sistemas, y el Gordon '. Plotkin también utilizó un teorema de la Iglesia-Rosser para probar que la evaluación de programas funcionales (para la evaluación perezosa y la evaluación impaciente ) es una función de programas a los valores (un subconjunto de los términos de la lambda). En los años 80, el teorema de la Iglesia-Rosser fue establecido para las extensiones del cálculo de la lambda con las características de los lenguajes de programación imprescindible .

Ver también

.