Машина Тьюринга, представляющая собой абстрактный исполнитель, была предложена
британским математиком Аланом Тьюрингом в 1936 году для формализации понятия
алгоритма. В состав машины Тьюринга входит бесконечная в обе стороны лента,
разделенная на ячейки, и управляющее устройство (каретка), способное находиться
в одном из состояний, число которых точно определено. Каретка может перемещаться
влево и вправо по ленте, читать и записывать в ячейки символы некоторого
конечного алфавита. При этом управляющее устройство работает в соответствии с
набором правил, которые предписывают каретке переместиться на одну клетку,
записать символ и т.д. Универсальной называют такую машину Тьюринга, которая
может заменить собой любую другую машину Тьюринга.
![]()
Фото из открытых источников
Двадцатилетний британский студент Алекс Смит из Бирмингемского университета
решил сложную математическую задачу, доказав, что машина Тьюринга с двумя
состояниями каретки и алфавитом из трех символов является универсальной.
Весной нынешнего года известный американский математик Стивен Вольфрам предложил
желающим доказать или опровергнуть предположение о том, что машина Тьюринга с
двумя состояниями каретки, набором правил и алфавитом из трех символов является
универсальной. В качестве приза за решение задачи Вольфрам учредил денежное
вознаграждение в размере 25 тысяч долларов США.
Как теперь сообщает ArsTechnica, первым с поставленной задачей справился Алекс
Смит, которому удалось доказать, что предложенная Вольфрамом машина Тьюринга
действительно является универсальной. С изысканиями Смита можно ознакомиться
здесь (файл в формате PDF).
Владимир Парамонов
