Гипотеза Черни // Алексей Савватеев, Михаил Волков

Каждому известно, что при попадании компьютера в непонятное состояние надо нажать кнопку “Reset”, после чего через некоторое время он перейдет в начальное. При этом на компьютере выполняется фиксированная последовательность команд: в каком бы состоянии он ни пребывал, после её выполнения он переходит в одно и то же. Если же вместо компьютера у нас есть произвольный конечный автомат, всё становится сложнее. Черни давным-давно выдвинул гипотезу, что если общее число состояний автомата равно n, то количество команд в такой последовательности будет не больше чем n-1 в квадрате, и привел серию автоматов, для которых эта оценка достигается. Чуть больше десяти лет назад Михаил Волков прочел серию лекций , где предположил, что квадратичная оценка сверху для количества команд в такой последовательности будет скоро доказана. Увы, до сих пор это не так. Надеемся, что после обращения внимания в этом видео на сей досадный факт, он перестанет иметь место.