Есть ли машина Тьюринга, которая может решить, остановятся ли почти все другие машины Тьюринга?
Предположим, у нас есть некоторое перечисление машин Тьюринга и некоторое представление о «размере» набора натуральных чисел ‖ ⋅ ‖ , и мы определяем:
Какие характеристики минимального значения существуют для разных ‖ ⋅ ‖ ? Например, предположим , что | | S | | является limsup пропорции чисел до к , которые находятся в S . Есть ли i, для которого f ( i ) = 0 ?
turing-machines
halting-problem
Acccumulation
источник
источник
Ответы:
Это не «хорошее» свойство, потому что от кодировки зависит, является ли оно истинным или ложным.
См. Асимптотическиλ Дэвид и др. Почти все λ- термины сильно нормализуют , что доказывает то, что говорится в заголовке. Тем не менее, эта статья также показывает, что для SKI-комбинаторов справедливо обратное (в которые лямбда-члены могут быть композиционно встроены)
Тем не менее, лямбда-термины могут быть переведены сохраняющим смысл способом в комбинаторное исчисление, такое как комбинаторы SKI (и наоборот), и в исчислениях комбинатора асимптотически все циклы цикла.
источник