В решение задачи Вольфрама, возможно, вкралась ошибка

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

В состав машины Тьюринга входит лента, бесконечная в обе стороны и разделенная на ячейки (внешняя память); читающая и записывающая каретка (управляющий блок), способная находиться в одном из нескольких конечных состояний, например, соответствующих верхнему или нижнему положению головки "печатаемой" капли; и программа (логический блок). В начале работы машины задаются входные условия - состояние ленты и положение каретки.

Универсальной называется машина Тьюринга, способная заменить собой любую другую МТ, то есть, по сути, вычислить любую функцию, для которой есть разрешающий алгоритм. Ценность машин Тьюринга заключается в логической простоте (они совершают элементарные и последовательные действия), что позволяет проводить исследования в области алгоритмов.

Еще в 2002 году известный математик Стефен Вольфрам (Stephen Wolfram) предположил, что универсальной может быть крайне простая машина Тьюринга. В работе "A New Kind of Science" ему удалось доказать, что универсальной является машина Тьюринга с двумя состояниями каретки и алфавитом из пяти символов (цветов). В мае 2007 года он учредил приз в размере $25 тыс. за доказательство или опровержение универсальности машины Тьюринга с двумя состояниями каретки и алфавитом из трех символов (МТ 2,3).

Недавно стало известно, что приз Вольфрама выиграл британский студент Алекс Смит (Alex Smith). Ему удалось привести доказательство того, что указанное простейшее абстрактное устройство способно выполнять функции любой другой машины Тьюринга.

Смит показал, что МТ 2,3 является эквивалентом варианта двухсимвольной циклической tag-системы Эмиля Поста (Emil Post), универсальность которого уже доказана. Tag-система Эмиля Поста - модель вычислений с конечным числом состояний, в которой доступ к элементам осуществляется по принципу FIFO ("первый пришел, первый вышел").

Однако, по мнению Вогана Пратта, в работу Смита вкралась элементарная логическая ошибка. Для машин эта ошибка означает, что линейно ограниченные автоматы являются универсальными машинами Тьюринга, а согласно современным представлениям, это не так.

С Воганом Праттом не согласен сотрудник Wolfram Research Тодд Роуланд (Todd Rowland), который предложил развернуть по данному вопросу широкую дискуссию.