À quel point un détecteur d'arrêt peut-il être bon?

12

Existe-t-il une machine de Turing qui peut décider si presque toutes les autres machines de Turing s'arrêtent?

N{Mi}

f(i)={n:Mi can't decide whether Mn halts}.

Quelles caractérisations de la valeur minimale de existent pour différents? Par exemple, supposonsest le limsup de la proportion des nombres jusqu'à qui sont dans . Existe-t-il un pour lequel ?fSkSif(i)=0

Accumulation
la source

Réponses:

10

Ce n'est pas une propriété "sympa", car qu'elle soit vraie ou fausse dépend du codage.

Voir Asymptoticallyλ de David et al presque tous termes normalisent fortement , ce qui prouve ce qu'il dit dans le titre. Cependant, cet article montre également que l'opposé est valable pour les combinateurs SKI (dans lesquels les termes lambda peuvent être intégrés de manière compositionnelle).

Dans le calcul lambda, une réduction est l'équivalent d'une étape d'une machine de Turing, et une forte normalisation est la propriété que chaque séquence de réduction atteint finalement une forme normale - c'est-à-dire qu'aucune autre réduction n'est possible. (Puisqu'un terme lambda donné peut avoir de nombreuses réductions valides, une normalisation forte est un peu comme dire qu'une machine de Turing non déterministe s'arrête toujours.) Ainsi, le fait qu'asymptotiquement presque tous les termes sont fortement normalisants signifie qu'avec une probabilité approchant 1, réduire un gros lambda atteindra toujours une forme normale.λ

Cependant, les termes lambda peuvent être traduits d'une manière préservant le sens dans un calcul combinatoire tel que les combinateurs SKI (et vice-versa), et dans les calculs combinateurs asymptotiquement tous les termes bouclent.

Neel Krishnaswami
la source
2
J'observe qu'un futur visiteur, ne connaissant pas nécessairement la relation entre une normalisation forte et l'arrêt de la détection, peut ne pas être en mesure de déterminer la position (le cas échéant) de votre réponse.
Eric Towers
@EricTowers Done!
Neel Krishnaswami