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

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

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

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

Наши‏ ‎ресурсы: ‎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

Поддержать ‎Алексея ‎Савватеева:‏ ‎https://sponsr.ru/checkout?project=savvateev