Невычислимые функции на примере Busy Beaver Game

IT технологии проникли в большинство сфер жизни человека и продолжают развиваться. Автопилот, банковская сфера, машинный перевод, медицина, финансовые рынки, полеты в космос — все это возможно благодаря одной простой идее.

В этой статье я предлагаю заглянуть за границы возможностей компьютеров и рассмотреть чего же они не могут. И почему. Алан Тьюринг еще в 30-е годы обозначил невозможные для компьютера задачи.

Машина Тьюринга

Если быть предельно точным, то та самая публикация Тьюринга, которая положила начало компьютерным наукам[1], была именно о вычислимых функциях, что подчеркивает существование границы, которую не может перешагнуть машина Тьюринга.

Машина Тьюринга(МТ) — это абстрактная вычислительная машина, тесно связанная с понятием алгоритма[10]. Это самый простой компьютер.

Также стоит помнить, что любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга[2]. Это ведет к тому, что все выводы касающиеся абстрактной машины Тьюринга, полностью применимы к любым компьютерам на любой архитектуре.