Перейти к основному содержанию

Математическая задача стоимостью 25 тысяч долларов.

25 тысяч долларов получит 20-летний британский студент Алекс Смит за решение математической задачи. Эта задача была предложена в мае 2007 года американским математиком Стивеном Вольфрамом, создателем популярной компьютерной программы Mathematica, основавшим в Америке компанию Wolfram Research.

Суть задачи заключалась в необходимости доказать, что конкретная машина Тьюринга с двумя состояниями каретки и алфавитом из трёх символов может считаться универсальной. Как вариант решения, нужно было доказать обратное. Третьекурснику Бирмингемского университета, изучающего электротехнику, удалось доказать универсальность машины посредством сведения задачи к более простой, но эквивалентной.

Вообще же в мире учреждено огромное количество всевозможных премий как в области науки (Нобелевская премия в области литературы, химии, физики, медицины, достижения мира во всём мире, экономики; Филдсовская премия в области математики; премия Тьюринга в области информатики и др.), так и скандальных премий (премия Дарвина).

Последняя премия вручается, как правило, посмертно за наиболее глупое и нелепое «извлечение своего вклада из генофонда человечества». «Победители», проще говоря, умирали или теряли способность иметь детей в результате нелепого несчастного случая, произошедшего по их же глупости.

Премия Тьюринга является самой престижной в области информатики. Спонсорами награды являются корпорации Google и Intel, а вручает эту ежегодную премию в размере 250.000 долларов Ассоциация вычислительной техники за выдающийся научно-технический вклад в области информатики. Премия названа в честь английского математика Алана Тьюринга, получившего первые серьёзные результаты в вопросах вычисления задолго до создания первых вычислительных машин. Первым лауреатом Премии Тьюринга стал в 1966 году Алан Перилас за развитие технологии создания компиляторов (http://ru.wikipedia.org/wiki/Компилятор).

Возвращаясь к премии Вольфрама, поясним, что машиной Тьюринга называется абстрактный исполнитель алгоритмов, являющийся упрощенной моделью вычислительной машины. Конкретная машина Тьюринга состоит из:

  • Бесконечной в обе стороны ленты, разделённой на три ячейки.
  • Алфавита символов, которые могут быть записаны в каждой ячейке.
  • Каретки, находящейся в одном из заданных состояний.
  • Программы перемещения каретки вида «прочти символ», «перейди в такую-то ячейку», «запиши символ», «сотри символ».

Перемещаясь влево и вправо, каретка может считывать и записывать символы алфавита. На этой машине можно промоделировать любой алгоритм, который может выполнить обычный компьютер.

Таким образом, перед Алексом Смитом и другими математиками, ломавшими голову над «вольфрамовской» задачей, стояла цель доказать универсальность конкретной машины Тьюринга с двумя состояниями каретки и алфавитом из 3 символов (включая и пустую ячейку). То есть, способность заменить собой любую другую машину Тьюринга. Об успешном достижении Смитом этой цели говорит тот факт, что парень стал богаче на 25 тысяч американских долларов.