¿Qué tan bueno puede ser un detector de detención?

¿Existe una máquina de Turing que pueda decidir si casi todas las demás máquinas de Turing se detienen?

$\mathbb{N} \rightarrow \{M_i\}$$\| \cdot \|$

¿Qué caracterizaciones del valor mínimo de existen para diferentes? Por ejemplo, supongamos quees la limsup de la proporción de los números hasta que están en . ¿Hay una para la cual ?$f$$\| \cdot \|$$\| S \|$$k$$S$$i$$f(i) = 0$

Esta no es una propiedad "agradable", porque si es verdadera o falsa depende de la codificación.

Vea Asintóticamente, de$\lambda$ David et al., Casi todos los términos se normalizan fuertemente , lo que demuestra lo que dice en el título. Sin embargo, este documento también muestra que lo opuesto es válido para los combinadores de SKI (en los que los términos lambda pueden incorporarse de forma compositiva).

En el cálculo lambda, una reducción es el equivalente a un paso de una máquina de Turing, y una fuerte normalización es la propiedad de que cada secuencia de reducción finalmente alcanza una forma normal, es decir, no es posible realizar más reducciones. (Dado que un término lambda dado puede tener muchas reducciones válidas, la normalización fuerte es un poco como decir que una máquina de Turing no determinista siempre se detiene). Por lo tanto, el hecho de que asintóticamente casi todos los términos se normalicen fuertemente significa que con una probabilidad cercana a 1, reducir los términos lambda grandes siempre alcanzará una forma normal.$\lambda$

Sin embargo, los términos lambda se pueden traducir de una manera que conserva el significado en un cálculo combinatorio como los combinadores SKI (y viceversa), y en el cálculo combinador asintóticamente todos los términos se repiten.