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

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

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

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

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

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

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

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



 Источник: science.compulenta.ru

Назначена награда в 12 тысяч долларов за доказательство существования сверхспособностей
Назначена награда в 12 тысяч долларов за доказательство существования сверхспособностей
Немецкое Общество исследования паранормальных наук назначило награду за доказательство существования сверхспособностей у человека. Каждому, кто продемонстрирует ученым какое-либо не поддающееся рациональному объяснению умение, будет гарантированно выплачена сумма в размере 12 тысяч долларов.
САМОЕ ЧИТАЕМОЕ
ФОТО ДНЯ
И это без всяких рыболовных снастей...
2003-2018 "Факты о невероятном" / "Эзорейтер"

Материалы данного сайта предназначены для лиц 16 лет и старше (16+)

Авторские права на материалы, размещенные на сайте, принадлежат авторам статей. Все права защищены и охраняются законом РФ. При использовании материалов с сайта ссылка на наш сайт обязательна. Если вы считаете, что публикация того или иного материала на нашем сайте нарушает законные права правообладателя, свяжитесь с нами.

Рейтинг@Mail.ru