Гипотеза Черни

Каждому известно, что при попадании компьютера в непонятное состояние надо нажать кнопку “Reset”, после чего через некоторое время он перейдет в начальное. При этом на компьютере выполняется фиксированная последовательность команд: в каком бы состоянии он ни пребывал, после её выполнения он переходит в одно и то же.

Если же вместо компьютера у нас есть произвольный конечный автомат, всё становится сложнее. Черни давным давно выдвинул гипотезу, что если общее число состояний автомата равно n, то количество команд в такой последовательности будет не больше чем n-1 в квадрате, и привел серию автоматов, для которых эта оценка достигается. Чуть больше десяти лет назад Михаил Волков прочел серию лекций https://www.lektorium.tv/course/22808, где предположил, что квадратичная оценка сверху для количества команд в такой последовательности будет скоро доказана. Увы, до сих пор это не так. Надеемся, что после обращения внимания в этом видео на сей досадный факт, он перестанет иметь место, тем более у видео есть конкретные адресаты из слушателей канала.

Ролик записан в Центре современной культуры "Смена": https://youtube.com/c/smenakazan

🎯 Поддержать популяризацию математики на Патреоне: https://patreon.com/savvateev

Наши ресурсы: https://vk.com/alexei_savvateev https://www.instagram.com/aleksey_savvateev https://www.facebook.com/savvatan https://savvateev.livejournal.com https://savvateev.xyz https://t.me/savvateev_xyz

Видео Гипотеза Черни канала Маткульт-привет! :: Алексей Савватеев и Ко