Close
2019-01-18 16:07:15

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

15.10.2007 448



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

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

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

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

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

Самое популярное
Банкир моргнула в эфире «нечеловеческими» глазами
18.01.2019 475

Случайный зритель смотрел недавно новости на американском телеканале «CNBC» и заметил нечто странное в эфире. На экране показывали..

Пришельцы давно среди нас
Российские ученые разработали экологически чистый и экономически выгодный метод переработки мусора
Новости партнеров