Является ли функция занятого бобра уникальной для игры занятого бобра в n-состоянии?

Question

Для данного n-состояния игра занятого бобра , уникальна ли функция занятого бобра или может быть несколько функций с одинаковым максимальным счетом?Возможно, это не было доказано в любом случае?

Answer 1

Да, это так.

Функция занятого бобра определена так, что

\Sigma(n) = max { \sigma(M) | M is a halting n-state 2-symbol Turing machine} 

Максимум уникален, если он существует, что он и делает (Радо доказал это). Это всего лишь число.

Следовательно, \ Sigma (n) также уникальна, и поэтому дискретная функция \ Sigma: N -> N также уникальна. Может быть несколько способов расширить \ Sigma до непрерывной функции, но почему кто-то захочет это сделать, мне не под силу.

Возможно вычислить небольшие значения \ Sigma; проверьте запись OEIS для самых больших известных значений.

Answer 2

Как отметил @PengOne, функция действительно уникальна.Это полностью определенная N -> N дискретная функция.

Однако из вашей формулировки («или может быть несколько функций с одинаковым максимальным счетом») также можно понять, что вы хотите знать, существуетнесколько занятых бобров, которые дают одинаковый максимум.Если это так, то да, есть по крайней мере 2 занятых бобра, которым дано N, один создается из другого путем простого изменения смены.

Answer 3

Это было задано давно, но я нашел это интересным: http://www.win.tue.nl/~wijers/shallit.pdf

Кроме того, я кодировал алгоритм, который грубо форсирует проблему занятого бобра в 3 состояниях, и он дал мне около 22 несимметричных конфигураций, которые производили 6 символов (последовательных или нет). Это означает, что существует около 60 конфигураций, если вы считаете, что вы можете поменять местами состояние 1 и состояние 2, а также инвертировать первый переход.

Но это только для количества произведенных символов, а не для "самого длинного исполнения".