tgoop.com/EchelonEyes/2915
Last Update:
Исследователи приближаются к пределам вычислимого
После десятилетий неопределенности команда программистов продемонстрировала, насколько сложными могут быть простые компьютерные программы.
Согласно гипотезе Гипотеза Чёрча-Тьюринга, любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга. Однако не существует общего алгоритма, который бы мог определить, остановится ли программа, по ее описанию и входным данным. То есть функция определения остановки невычислима. На практике это выглядит так — сам компьютер никогда не сможет определить точно, зависнет ли его очередная программа в бесконечном потоке инструкций или нет.
Для испытания пределов вычислимого в 1962 году венгерский математик Тибор Радо создал игру Busy Beaver (усердный бобер), которая предлагает найти программу для машины Тьюринга с n состояниями, которая работает максимально долго и потом завершается. Программы, которые интересуют охотников за бобрами, написаны не на обычном языке программирования, а с помощью инструкций для теоретических компьютеров, называемых машинами Тьюринга. Ученый-первопроходец Алан Тьюринг задумал эти гипотетические устройства в 1936 году как способ математического моделирования процесса вычислений.
При этом машин Тьюринга может быть бесконечное множество, поэтому Радо предложил разделить их на группы в зависимости от того, сколько у них правил: одна группа для всех машин Тьюринга с одним правилом, другая для всех машин с двумя правилами и так далее.
Найти предел вычислений для машины с одни правилом элементарно, поскольку фактически существует только две возможности. Если правило предписывает машине Тьюринга остановиться, когда она увидит 0, она остановится на первом шаге. Любое другое правило заставит машину двигаться по ленте вечно, поскольку в каждой ячейке она встретит 0. Это означает, что количество шагов в усердном бобре с одним правилом, или BB(1), равно 1.
Достаточно простой программы, чтобы доказать, что BB(2) = 6. Но найти BB(3) уже гораздо труднее, впрочем в 1965 году ученые выяснили, что BB(3) = 21, а в 1975 году было доказано, что BB(4) = 107, при этом ученым пришлось изучить тысячи состояний машин Тьюринга.
С тех пор, на протяжении более чем 40 лет, программисты пытаются обнаружить пятого бобра. Исследователи подсчитали, что с пятью правилами существует почти 17 триллионов возможных машин Тьюринга — даже простое перечисление их всех со скоростью одна в миллисекунду заняло бы более 500 лет. Один из программистов установил рекорд, в котором машина остановилась после 100 000 шагов, однако ее перебили другие охотники, добившись длительности вычислений в 2 миллиона шагов в 1984 году.
Новые охотники за бобрами, Хайнер Марксен и Юрген Бунтрок из Берлина, использовали новые математические методы для ускорения моделирования машин Тьюринга, однако сдались, так и не перебив предыдущий рекорд. Лишь спустя годы Марксен, получив доступ к мощному компьютеру, предпринял новые попытки. Он оставил его включенным на выходные, надеясь воспроизвести открытие машины с 2 миллионами шагов. Вместо этого его программа выполнила колоссальные 47 176 870 шагов.
Фактически тогда Марксен поймал усердного бобра, но потребовалось более 30 лет усилий ученых из разных стран, чтобы доказать, что все оставшиеся машины никогда не останавливались. Так, 10 мая 2024 года было объявлено, что машина Марксена-Бунтрок действительно является пятым усердным бобром. Подробные детали вычислений приводятся в журнале Quanta Magazine.
Это очень важный эксперимент, потому что в нем исследуются пределы вычислимого.
Научное сообщество уже приступило к поиску шестого бобра, причем многие уверены, что он станет последним, то есть фактически пределом вычислимого, дальше которого человечество никогда не прыгнет.
Источник: https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/
#машинаТьюринга
BY Echelon Eyes
Share with your friend now:
tgoop.com/EchelonEyes/2915