Невычислимость функции на основе функции Busy Beaver
Позволять $\log _b^ac$обозначают повторяющееся основание-$b$функция логарифма. Например,$$\log _2^3({2^{65536}}) = {\log _2}({\log _2}({\log _2}({2^{65536}}))) = 4.$$
Выберите произвольную модель M машин Тьюринга, предполагая, что машина работает с двухсимвольным алфавитом:$0$ как пустой символ и $1$как непустой символ. Мы будем называть такие машины «М-машинами».
Позволять $f(n)$ обозначают максимальное количество непустых символов, которые могут появиться на ленте, когда конкретная M-машина останавливается, предполагая, что все машины начинаются с пустого ввода, а таблица инструкций содержит не более $n$ рабочие состояния.
Тогда функция $F(n)$ определяется следующим образом: $${F}(n) = \left\{ \begin{array}{l} 0\quad {\text{if}}\;{x_n}\;{\text{is even}}{\text{,}}\\ 1\quad {\text{if}}\;{x_n}\;{\text{is odd}}{\text{,}} \end{array} \right.$$ где $x_n$ наименьшее натуральное число такое, что $$\log _{{f}(n) + 2}^{x_n}({f}(n + 1) + 3) < 2.$$
Вопрос: это функция $F(n)$ невычислимой для любой модели M (то есть не существует M-машины, которая могла бы вычислить $F(n)$функция, независимо от того, какой M мы выберем)? Если да (или нет), можно ли это доказать?
РЕДАКТИРОВАТЬ
Предположим, что мы выбираем модель, описанную в разделе «Игра» в статье Википедии «Занятый бобер» . Является$F$невычислимо на таких машинах? Мне тоже интересно, как это доказать.
Ответы
Вложенный логарифм здесь мало что дает. Это вычислимая функция с вычислимой обратной, поэтому функции$n \mapsto x_n$ а также $f$ не только эквивалентны по Тьюрингу, но и связаны через вычислимое масштабирование.
Таким образом, ответ на этот вопрос применим и здесь.
Мы, безусловно, могли бы настроить наши машины Тьюринга таким образом, чтобы они никогда не записывали общее количество непустых символов, попадающих в диапазон, который $x_n$странный. Нам нужно будет провести некоторые побочные вычисления, чтобы определить допустимые диапазоны, но, учитывая размер диапазонов, я ожидаю, что символы, которые нам нужны для определения следующего интервала, который мы можем использовать, в конечном итоге не выведут нас из этого интервала.
С другой стороны, для естественной установки я не вижу причин, почему $F$когда-либо будет вычислимым. Но на самом деле для доказательства этого для конкретной установки потребовалось бы гораздо больше подумать о деталях конкретной модели машины Тьюринга, чем я бы хотел.