Насколько хорошим может быть детектор остановки?

12

Есть ли машина Тьюринга, которая может решить, остановятся ли почти все другие машины Тьюринга?

Предположим, у нас есть некоторое перечисление машин Тьюринга и некоторое представление о «размере» набора натуральных чисел , и мы определяем:N{Mi}

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

Какие характеристики минимального значения существуют для разных ? Например, предположим , что | | S | | является limsup пропорции чисел до к , которые находятся в S . Есть ли i, для которого f ( i ) = 0 ?fSkSif(i)=0

Acccumulation
источник
4
projecteuclid.org/euclid.ndjfl/1168352664
Эмиль Йержабек

Ответы:

10

Это не «хорошее» свойство, потому что от кодировки зависит, является ли оно истинным или ложным.

См. Асимптотическиλ Дэвид и др. Почти все λ- термины сильно нормализуют , что доказывает то, что говорится в заголовке. Тем не менее, эта статья также показывает, что для SKI-комбинаторов справедливо обратное (в которые лямбда-члены могут быть композиционно встроены)

λ

Тем не менее, лямбда-термины могут быть переведены сохраняющим смысл способом в комбинаторное исчисление, такое как комбинаторы SKI (и наоборот), и в исчислениях комбинатора асимптотически все циклы цикла.

Нил Кришнасвами
источник
2
Я заметил, что будущий посетитель, не обязательно зная связь между строгой нормализацией и обнаружением остановки, может не определить, какую позицию (если таковая имеется) занимает ваш ответ.
Эрик Тауэрс
@EricTowers Готово!
Нил Кришнасвами