Вариант функции занятого бобра

Читая этот вопрос « Естественные неразрешимые проблемы RE, но не полные по Тьюрингу », мне пришло в голову следующее:

Если - это функция занятого бобра (максимально достижимая оценка среди всех останавливающих 2-символьных машин Тьюринга с n-состояниями описанного выше типа при запуске на чистой ленте), определите функцию:$\Sigma(\cdot)$

Теперь определите язык:

$L = \{ \langle M \rangle \; | \; \langle M \rangle \mbox{ halts and } BB(\langle M \rangle) = 0 \}$

Является перечислимым? (следует повторить: просто моделируйте параллельно M со всеми TM одинаковой длины, и если останавливается, а другой останавливается с более высоким счетом, добавьте M к перечислению).M M $L$$M$$M'$

Можем ли мы уменьшить проблему остановки до ? (кажется, что он не может «захватить» остановку занятых бобров)$L$

Я не могу поверить, что я не видел этого раньше - но да, с оракулом для вы можете решить проблему остановки. Очевидно, что оракул для L дает нам «рекурсивно» все машины, не останавливающие Busy Beaver, поэтому возникает вопрос: «Можем ли мы рекурсивно выяснить в L, что такое занятые бобры?». Определить Σ 2 ( n ) как функцию счета «второго загруженного бобра»; то есть второй наивысший достижимый балл среди всех остановленных двухсимвольных ТМ с n- состояниями. Хитрость в том, что существует рекурсивная функция такая, что (почти наверняка,$L$$L$$L$$\Sigma_2(n)$$n$Σ ( n ) ≤ Σ 2 ( f ( n ) ) f ( n ) = n + $f()$$\Sigma(n)\leq\Sigma_2(f(n))$$f(n)=n+1$на самом деле сделает свое дело, но для этого нужно знать, что функция BB строго возрастает): дана машина размера n, которая печатает Σ ( M ) 1s на своей ленте, а затем останавливается, есть несколько c > 1 и две машины каждый размеромкоторый печатает точно1s и точно1s соответственно на своих лентах - и это верно для машины "занятого бобра"даже если мы этого не делаем знатьявно. Это означает, что наличие функции «второй занятый бобер» для$M$$n$$\Sigma(M)$$c\gt 1$Σ ( M ) Σ ( M ) + 1 M M f ( n ) $\leq cn$$\Sigma(M)$$\Sigma(M)+1$$M$ $M$$f(n)$дает оценку функции занятого бобра на ; но затем с этим, это легко решить Проблему Остановки для ТМ М размера п - если ⟨ M ⟩ ∈ L , то говорят , что M привалов; в противном случае найдите самую длинную машину размера f ( n ) в L (что можно сделать рекурсивно, поскольку существует только конечное число машин размера ≤ f ( n ) ) и смоделируйте M столько же шагов, сколько эта машина делает для остановки , Если М не останавливается в течение этого времени, то М$n$$M$$n$$\langle M\rangle\in L$$M$$f(n)$$L$$\leq f(n)$$M$$M$$M$ не может остановиться

Это переработанная версия хорошего ответа Стивена с явным сокращением проблемы Остановки.

Учитывая сборки М ' , которая проходит М на ж и , если он останавливается идет справа от ленты, пишет 0 и привал.$\langle M \rangle, w$$M'$$M$$w$

Если останавливается, B B ( M ' ) = 0, потому что есть эквивалентный TM того же размера, который записывает 1 и останавливается; таким образом, мы можем использовать решающий знак для L, чтобы проверить, останавливается ли M на w ( M останавливается на w тогда и только тогда, когда M ′ ∈ L )$M'$$BB(M')=0$$L$$M$$w$$M$$w$$M' \in L$

... оказалось, что вопрос действительно тривиальный :-)