Функция максимального сдвига

Функция максимального сдвига или функция безумной лягушки^[1], обозначается как $S(n)$ или ${FF}(n)$ , является родственной функции занятого бобра. $S(n)$ определяется как максимальное количество переходов между состояниями, выполненными двухцветной машиной Тьюринга с "n" состояниями перед остановкой при пустом вводе. Хотя название впервые обсуждалось Тибором Радо,^[2] "безумная лягушка" появилась в рамках исследовательского проекта Джеймса Харланда "Сумасшедший зоопарк" на машине Тьюринга.^[3]^[4]

Некоторые авторы ссылаются на $S(n)$ как на функцию занятого бобра.^[5]

Соотношения между функциями $S$ и $\Sigma$ []

Очевидно, что $S(n) \geq \Sigma(n)$ , поскольку печать $\Sigma(n)$ с чистой ленты требует как минимум $\Sigma(n)$ шагов. Следовательно, функция безумной лягушки является невычислимой и в конечном итоге доминирует над всеми вычислимыми функциями.

Майкл Буро доказал в 1990 году, что $S(n)<\Sigma (9n)$ .^[6] На странице Паскаля Мишеля есть непроверенное утверждение, что Бен-Амрам и Петерсен доказали в 2002 году, что существует константа c такая, что $S(n)<\Sigma (n+{\frac {8n}{{\text{log}}_{2}(n)}}+c)$ .^[7]

Машина, которая производит $\Sigma(n)$ это не обязательно та же машина, которая производит $S(n)$ . Например, следующий занятый бобёр с 3 состояниями и 2 символами выдаёт максимум шесть единиц, но выполняет только 14 шагов:^[8]

	A	B	C
0	1RB	0RC	1LC
1	1RH	1RB	1LA

Для сравнения, следующий занятый бобёр выполняет максимум 21 ход, но выдаёт только пять единиц:^[9]

	A	B	C
0	1RB	1LB	1LC
1	1RH	0RC	1LA

Значения[]

Было доказано, что $S(1)=1$ , $S(2)=6$ , $S(3)=21$ и $S(4)=107$ . Некоторыми нижними границами для более высоких значений являются $S(5)\geq 47,176,870$ и $S(6)\geq 7,412\cdot 10^{36,534}$ .