Close
23 марта 2019, Суббота

Двадцатилетний студент решил задачу о машине Тьюринга

15.10.2007 452



Двадцатилетний британский студент Алекс Смит из Бирмингемского университета решил сложную математическую задачу, доказав, что машина Тьюринга с двумя состояниями каретки и алфавитом из трех символов является универсальной.

Машина Тьюринга, представляющая собой абстрактный исполнитель, была предложена британским математиком Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. В состав машины Тьюринга входит бесконечная в обе стороны лента, разделенная на ячейки, и управляющее устройство (каретка), способное находиться в одном из состояний, число которых точно определено. Каретка может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. При этом управляющее устройство работает в соответствии с набором правил, которые предписывают каретке переместиться на одну клетку, записать символ и т.д. Универсальной называют такую машину Тьюринга, которая может заменить собой любую другую машину Тьюринга. (esoreiter.ru)

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

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

Владимир Парамонов

Новости партнеров
Рекомендуем
Самое популярное
На фотоснимке, присланным с Марса, обнаружено что-то наподобие древней статуи
23.03.2019 1056

Марсоход Opportunity в феврале этого года признан сотрудниками НАСА окончательно вышедшим из строя, хотя в действительности..

Загрузка...