Разрыв между

$HT(n)$ $n$ $BB(n) = \max HT(n)$

Что мы можем сказать о втором по величине числе в ? Назовите это . $HT(n)$ $BB_2(n)$

$BB_2(n)$ тривиально не вычислим, так как он позволяет вычислить : просто подождите, пока остановится еще одна машина. Наивно, я ожидал бы, что разрыв будет «похож на занятого бобра», увеличиваясь быстрее, чем любая вычислимая функция. Это доказуемо? $BB(n)$ $BB(n) - BB_2(n)$

computability Джеффри Ирвинг
источник

Предположим, что одно из n состояний недостижимо.

микрофон

@mic: я не думаю, что это актуально.

представляется крайне маловероятным.

B B (n - 1) = B B_{2} (n)

$BB(n-1) = BB_2(n)$

Джеффри Ирвинг

Это будет зависеть от кодировки. Если вы перевернете состояния принятия / отклонения, число состояний останется неизменным, и поэтому время остановится, что сделает

B B (n) = B B_{2} (n)

$BB(n)=BB_2(n)$

Ланс Фортноу

Вот почему я позволил

быть набором времен остановки, так что зазор по конструкции ненулевой.

H T (n)

$HT(n)$

Джеффри Ирвинг

Возможно ли даже доказать, что разрыв в конечном итоге не равен 1?

Джеффри Ирвинг

Количество состояний - это просто понятие сложности описания вычислимых функций в модели, вы можете выбрать любую модель вычислений и любую их кодировку в виде двоичных строк, а затем взять длину как n и определить BB (n) на основе это и все интересные результаты о BB (n) все еще были бы верны, есть особенное скучное представление о модели TM и количестве состояний.
Ничто не мешает им выбирать любую модифицированную модель ТМ. Как правило, вопросы, которые не являются инвариантными при таких изменениях представления ТМ, касаются не вычислимости или ТМ, а конкретного представления (например, BB (n) mod 2 и т. Д.), И если нет какой-то конкретной причины, по которой они интересны, они не не стоит преследовать имхо. Это хорошие головоломки, но они не имеют особой ценности. Заметим, что «BB (n) не вычислимо» инвариантно относительно изменения представлений ТМ.
Так не инвариантен ли этот вопрос при изменении представления вычислимых функций? Я думаю, что ответ - нет.

я. Рассмотрим представление, в котором у нас есть два специальных состояния 0 и 1, и либо 0 является начальным и просто может перейти в 1, либо 0 недоступно, а 1 является начальным. В этой кодировке разница составляет 1.

б. Рассмотрим другое представление, где у нас есть UTM плюс часть, которая записывает n бит на ленту перед переходом к UTM. Таким образом, вопрос становится max f (x) - 2ndmax f (x), где max превышают строки из n битов, а f - произвольная вычислимая функция. Нам нужно только найти вычислимую функцию, где она не вычислима. Я не думал об этом много, но моя интуиция говорит, что есть такая вычислимая функция.

Кава
источник

Ничто из этого не имеет значения, потому что я выбрал стандартные машины Тьюринга в качестве своего понятия вычисления. Я согласен с тем, что есть несколько различных общих определений (одно- или двухсторонняя лента, независимо от того, начинается ли лента с нуля или какого-то специального пустого символа), но ничего похожего на предварительно кодированные UTM, которые вы упоминаете.

Джеффри Ирвинг

n

$n$

Позвольте мне выразить это по-другому: почему вы заинтересованы в ответе? Как и многие другие, для BB характерны загадки, связанные с конкретным представлением ТМ, но они не раскрывают ничего о вычислимости и вычислениях. Выбор стандарта для представления ТМ был произвольным действием, можно было бы выбрать мое первое представление выше, и ответ на ваш вопрос был бы 1. Тот факт, что он называется стандартом, не делает его особенным среди представлений.

Каве

Это ничем не отличается от вопроса о том, имеет ли какое-либо произвольно выбранное уравнение Диофантиена E целочисленное решение. Таких уравнений бесконечно много, без причины, почему кто-то интересуется E, это не очень интересный вопрос. Когда люди задают такие вопросы, как «вычислимость BB (n) mod 2», они думают, что задают глубокие вопросы о вычислимости, тогда как в действительности это больше похоже на вопрос о разрешимости некоторого произвольно выбранного уравнения Диофантиана, но некоторые из них выглядят приятнее глаз.

Каве

Мне интересно, потому что я считаю, что ответ одинаков для всех недеградирующих кодировок: это недоказуемо, недоказуемо, что недоказуемо и т. Д. Но я не знаю, как это сформулировать, поэтому я выбрал один. Тот факт, что для специально выбранных кодировок это тривиально, похоже на проблему остановки, решаемую для машин с остановкой конструкции.

Джеффри Ирвинг

Разрыв между

Ответы: