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

25 октября 2007 года, 14:53
Текст: Владимир Парамонов

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

[IMG]http://science.compulenta.ru/upload/iblock/9cd/turing_machine.jpg[/IMG]
Машина Тьюринга (изображение с сайта ArsTechnica)

Машина Тьюринга, представляющая собой абстрактный исполнитель, была предложена британским математиком Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. В состав машины Тьюринга входит бесконечная в обе стороны лента, разделенная на ячейки, и управляющее устройство (каретка), способное находиться в одном из состояний, число которых точно определено. Каретка может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. При этом управляющее устройство работает в соответствии с набором правил, которые предписывают каретке переместиться на одну клетку, записать символ и т.д. Универсальной называют такую машину Тьюринга, которая может заменить собой любую другую машину Тьюринга.
Весной нынешнего года известный американский математик Стивен Вольфрам предложил желающим доказать или опровергнуть предположение о том, что машина Тьюринга с двумя состояниями каретки, набором правил и алфавитом из трех символов является универсальной. В качестве приза за решение задачи Вольфрам учредил денежное вознаграждение в размере 25 тысяч долларов США.
Как теперь [URL="http://arstechnica.com/news.ars/post/20071024-simple-turing-machine-shown-capable-of-solving-any-computational-problem.html"][COLOR=#004982]сообщает[/COLOR][/URL] ArsTechnica, первым с поставленной задачей справился Алекс Смит, которому удалось доказать, что предложенная Вольфрамом машина Тьюринга действительно является универсальной. С изысканиями Смита можно ознакомиться [URL="http://www.wolframscience.com/prizes/tm23/TM23Proof.pdf"][COLOR=#004982]здесь[/COLOR][/URL] (файл в формате PDF).

[URL="http://science.compulenta.ru/337135/"]compulenta.ru[/URL]