Двадцатилетний британский студент Алекс Смит решил математическую задачу, за решение которой известный американский математик Стивен Вольфрам учредил приз в 25 тысяч долларов, сообщает журнал Nature.
Стивен Вольфрам известен, в частности, как создатель распространенной компьютерной программы Mathematica. В мае этого года Вольфрам предложил всем желающим доказать, что конкретная машина Тьюринга с двумя состояниями каретки и алфавитом из трех символов является универсальной или же доказать обратное.
Машиной Тьюринга в честь британского математика Алана Тьюринга называют абстрактный исполнитель алгоритмов, который упрощает модель вычислительной машины. В состав машины Тьюринга входит бесконечная в обе стороны лента, разделенная на ячейки, а в каждой ячейке может быть записан один из символов заданного алфавита. Над лентой передвигается каретка, которая может находиться в одном из заданных состояний.
Мысленный эксперимент с машиной Тьюринга редко непосредственно используется в современной математике, но в принципе на ней можно промоделировать многие, в том числе и довольно сложные, алгоритмы.
А универсальной машиной Тьюринга называют машину, которая способна заменить собой любую другую машину Тьюринга. Поэтому задача, предложенная Вольфрамом, состояла в том, чтобы выяснить, является ли машина Тьюринга с двумя состояниями каретки, алфавитом из трех символов и конкретным набором правил универсальной и доказать это.
Победителем стал Алекс Смит, студент третьего курса Бирмингемского университета, занимающийся изучением электротехники. Он сумел доказать универсальность вольфрамовской машины, за что и получит 25 тысяч долларов.