¿Existe una Turing completa cálculo lambda escrita a máquina?

Question

¿Existen cualquier Turing completa con tipo lambda cálculos? Si es así, ¿cuáles son algunos ejemplos?

Answer 1

Sí, seguro. Muchos lambda mecanografiada cálculos aceptar solamente términos fuertemente de la normalización, por diseño, por lo que no pueden expresar cálculos arbitrarios. Sin embargo, un sistema de tipos puede ser lo que desee; que sea lo suficientemente amplia, y se puede expresar todos los cálculos deterministas.

Un sistema de tipo trivial que abarca un fragmento de Turing-completa del cálculo lambda es la que acepta cada plazo, así tecleó-(con un top tipo ). $$ \ dfrac {} {\ Gamma \ vdash M: \ superior} $$

En términos más prácticos, estático de tipos de lenguajes de programación funcionales tienen en su núcleo un mecanografiada cálculo lambda que permite una punto fijo combinador así mecanografiado. Por ejemplo, comenzar con el simplemente mecanografiado cálculo lambda (o el sistema de tipo ML o sistema de F o cualquier otro tipo de sistema de su elección) y añadir una regla que hace que algunos combinador punto fijo como $ \ mathbf {Y} = \ lambda f. (\ Lambda x. F (x \, x)) (\ lambda x. F (x \, x)) $ bien escrito. $$ \ Dfrac {\ Gamma \ vdash f: T \ rightarrow T} {\ Gamma \ vdash \ mathbf {Y} \, f: T} \ qquad \ Dfrac {\ Gamma \ vdash f: T \ rightarrow T} {\ Gamma \ vdash (\ lambda x f (x \, x).) (\ Lambda x f (x \, x).): T} $$ Las reglas que los presentados anteriormente son bastante torpe, ya que hacen términos como $ \ vec {y} \, f $ así mecanografiados a pesar de que sus componentes no están bien mecanografiados a - que no son totalmente compositiva. Una solución sencilla es añadir un combinador punto fijo como una constante lenguaje y proporcionar una regla delta para ello; entonces es una simple cuestión de tener un sistema de tipos y la semántica de reducción con tipo preservación . Lo que se obtiene lejos del cálculo lambda puro en el reino de cálculo lambda con constantes. $$ \ begin {*} recopilar \ Dfrac {} {\ Gamma \ vdash \ textbf {fijo}: (T \ rightarrow T) \ rightarrow T} \\ \ Textbf {fix} \, f \ a f (\ textbf {fix} \, f) \\ \ End {*} $$ reunir

Cumplir con el cálculo lambda puro, un sistema de tipo de interés es el cálculo lambda con tipos de intersección.

$$ \ Dfrac {\ Gamma \ vdash M: T_1 \ quad \ Gamma \ vdash M: T_2} {\ Gamma \ vdash M: T_1 \ wedge} T_2 (\ Wedge I) \ Qquad \ qquad \ {} Dfrac {\ Gamma \ vdash M: \ superior} (\ I arriba) $$

tipos de intersecciones tienen propiedades interesantes con respecto a la normalización:

• Una lambda plazo se puede escribir sin utilizar el $ \ $ regla superior I si y sólo si es fuertemente normalizando.
• Una lambda plazo admite un tipo que no contiene $ \ $ si y sólo si la parte superior tiene una forma normal.

Caracterización de lambda-términos que tienen tipos de unión para una penetración en cuanto a por qué tipos de intersección tienen un alcance tan notable.

Por lo que tiene un sistema de tipo que define un lenguaje Turing completo (ya que cada término es bien escrito-), y una caracterización simple de poner fin a los cálculos. Por supuesto, ya que este tipo de sistema caracteriza a la normalización, no es decidible.

_{Una observación sobre los nombres de las reglas $ (\ top I) $ y $ (\ wedge I) $: no tienen sentido formal, sino que se eligen deliberadamente. el $ $ que es sinónimo de “introducción”, porque se trata de reglas de introducción - que introducen el símbolo ($ \ wedge $ o $ \ $ arriba) en el tipo debajo de la línea. Dualmente, encontrará reglas de eliminación, cuando un símbolo aparece por encima de la línea, pero no por debajo. Por ejemplo, la regla de typecheck una expresión lambda en el cálculo lambda escrito con sencillez es la regla de introducciónpor $ \ rightarrow $, y el estado de typecheck una aplicación es la regla de eliminación de $ \ rightarrow $.}