Новости

« вернуться к списку

версия для печати

Британский студент получит 25 тысяч долларов за математическое доказательство

"Вольфрамовская" машина Тьюринга в виде конечного автомата: первые двести переходов. Направление "капельки" (вверх/вниз) символизирует состояние каретки, цвет квадратика (белый, желтый, оранжевый) – символ алфавита. Изображение с сайта wolframscience.comДвадцатилетний британский студент Алекс Смит (Alex Smith) решил задачу, предложенную в мае 2007 года известным американским математиком Стивеном Вольфрамом (Stephen Wolfram), и теперь получит учрежденный Вольфрамом приз в 25 тысяч долларов, сообщает журнал Nature.

Вольфрам родился в Лондоне, но впоследствии переехал в Америку и основал там компанию Wolfram Research. Известен, в частности, как создатель распространенной компьютерной программы Mathematica. В мае этого года Вольфрам предложил всем желающим доказать, что конкретная машина Тьюринга с двумя состояними каретки и алфавитом из трех символов является универсальной (или доказать обратное).

Машиной Тьюринга в честь британского математика Алана Тьюринга (Alan Turing) называют абстрактный исполнитель алгоритмов, упрощенную модель вычислительной машины. В состав машины Тьюринга входит бесконечная в обе стороны лента, разделённая на ячейки, в каждой ячейке может быть записан один из символов заданного алфавита. Над лентой передвигается каретка, которая может находиться в одном из заданных состояний.

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

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

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

источник: Lenta.ru

Последние материалы раздела

• 30 декабря 2016
  На орбите Земли Новый год отметят 16 раз
• 30 декабря 2016
  В забайкальской школе из-за невыплаты зарплаты массово уволились учителя
• 30 декабря 2016
  Рособрнадзор запретил прием студентов в пять вузов
• 30 декабря 2016
  Россия в I квартале 2017 года планирует выполнить не менее четырех космических пусков
• 30 декабря 2016
  Карякин стал чемпионом мира по блицу

Обсуждение

Добавить комментарий

Обсуждение материалов доступно только после регистрации.

« к началу страницы