Quão bom pode ser um detector de parada?

12

Existe uma máquina de Turing que pode decidir se quase todas as outras máquinas de Turing são interrompidas?

Suponha que tenhamos alguma enumeração de máquinas de Turing e alguma noção de "tamanho" de um conjunto de números naturaise definimos:N{Mi}

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

Que caracterizações do valor mínimo de f existem para diferentes ? Por exemplo, suponha Sé o limsup da proporção dos números até k que estão em S . Existe um i para o qual f(i)=0 ?

Acumulação
fonte

Respostas:

10

Esta não é uma propriedade "agradável", porque se é verdadeira ou falsa depende da codificação.

Veja os termos assintoticamente deλ David et al. Quase todos os termos \ lambda estão fortemente normalizando , o que prova o que diz o título. No entanto, este artigo também mostra que o oposto se aplica aos combinadores SKI (nos quais os termos lambda podem ser incorporados em termos de composição).

No cálculo lambda, uma redução é equivalente a um passo de uma máquina de Turing, e uma forte normalização é a propriedade de que toda sequência de redução finalmente atinge uma forma normal - ou seja, nenhuma redução adicional é possível. (Como um determinado termo lambda pode ter muitas reduções válidas, uma normalização forte é um pouco como dizer que uma máquina de Turing não determinística sempre para.) Portanto, o fato de que quase todos os termos assintoticamente estejam normalizando fortemente significa que, com probabilidade se aproximando de 1, reduzir um grande número de termos lambda sempre alcançará uma forma normal.λ

No entanto, os termos lambda podem ser traduzidos de maneira preservadora de significado em um cálculo combinatório, como os combinadores SKI (e vice-versa), e no cálculo combinador, assintoticamente, todos os termos são repetidos.

Neel Krishnaswami
fonte
2
Observo que um futuro visitante, sem necessariamente conhecer a relação entre forte normalização e detecção de interrupção, pode não ser capaz de determinar qual posição (se houver) sua resposta.
Eric Towers
@EricTowers Done!
Neel Krishnaswami