В своей книге Новый вид науки , Стивен Вольфрам описал универсальный 2-состояния 5-символа машина Тьюринга , и предположил , что конкретный 2-состояние 3-символ Тьюринга машина ( в дальнейшем (2,3) Тьюринга машина ) может быть универсальным , как хорошо. [1]
14 мая 2007 года Вольфрам объявил, что приз в размере 25 000 долларов будет выигран первым человеком, который докажет или опровергнет универсальность (2,3) машины Тьюринга. [2] 24 октября 2007 года было объявлено, что приз выиграл Алекс Смит, студент факультета электроники и вычислительной техники Университета Бирмингема , за доказательство его универсальности, хотя изначально это доказательство оспаривалось.
Описание
В следующей таблице указаны действия, которые должна выполнить машина Тьюринга в зависимости от того, является ли ее текущее состояние A или B , а текущий считываемый символ - 0, 1 или 2. Записи в таблице указывают символ, который должен быть напечатан, направление в которое должна перемещать головка ленты, и последующее состояние машины.
А B 0 P1, R, B P2, L, A 1 P2, L, A P2, R, B 2 P1, L, A P0, R, A
(2,3) машина Тьюринга:
- Не имеет состояния остановки;
- Связан с 23 другими машинами тривиальным обменом состояний, символов и направлений.
Минский (1967) вкратце утверждал, что стандартные (2,2) машины не могут быть универсальными, а М. Маргенштерн (2010) представил математическое доказательство [3], основанное на результате Л. Павлоцкой в 1973 г. (не опубликовано, но упомянуто в статье Маргенштерна). ; таким образом, может показаться, что (2, 3) машина Тьюринга будет наименьшей возможной универсальной машиной Тьюринга (с точки зрения количества состояний, умноженного на количество символов). Однако результаты нельзя напрямую сопоставить, потому что Мински рассматривает только машины, которые явно останавливаются, а машина (2,3) - нет. В более общем плане почти все формальные определения машин Тьюринга различаются деталями, не имеющими отношения к их мощности, но, возможно, относящимися к тому, что можно выразить с помощью данного количества состояний и символов; единого стандартного формального определения не существует. (2, 3) машина Тьюринга также требует бесконечного неповторяющегося ввода, что опять же делает прямое сравнение с более ранними небольшими универсальными машинами Тьюринга проблематичным.
Следовательно, хотя может быть и правда, что (2, 3) машина в некотором смысле является «наименьшей возможной универсальной машиной Тьюринга», это не было строго доказано в классическом смысле, и это утверждение открыто для обсуждения, если принять во внимание традиционные определения универсальности и то, может ли ослабление свойств машины Тьюринга, используемых для доказательства, быть разрешено в целом, и может даже быть предложено новые способы определения вычислительной универсальности, более независимые от произвольного выбора (например, наличие конфигурации остановки или требование чистой ленты) .
Состояние головы (верхняя или нижняя капля (A и B соответственно)) и цветовой узор (белый, желтый и оранжевый (0,1 и 2 соответственно)) в данной строке зависит исключительно от содержимого строки сразу над ним.
Несмотря на то, что машина имеет головку только с двумя состояниями и ленту, которая может содержать только три цвета (в зависимости от исходного содержимого ленты), вывод машины все равно может быть чрезвычайно сложным. [4]
Доказательство универсальности
24 октября 2007 года компания Wolfram Research объявила, что Алекс Смит, студент факультета электроники и вычислительной техники Бирмингемского университета (Великобритания), доказал универсальность (2,3) машины Тьюринга и, таким образом, получил приз Вольфрама, описанный выше. [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] »
Доказательство показало, что машина эквивалентна уже известному как универсальному варианту системы тегов . Смит первым построил последовательность систем правил, показывающих, что (2, 3) машина Тьюринга способна производить произвольные конечные вычисления. Затем он применил новый подход, чтобы распространить эту конструкцию на неограниченные вычисления. Доказательство проходит в два этапа. Первая часть имитирует конечную эволюцию любой двухцветной циклической системы тегов. Эмуляция представляет собой комбинацию серии имитаций, включающих индексированные системы правил от «система 0» до «система 5». Каждая система правил имитирует следующую в последовательности. Затем Смит показал, что даже несмотря на то, что начальное условие (2, 3) машины Тьюринга не повторяется, построение этого начального условия не является универсальным. Следовательно, (2, 3) машина Тьюринга универсальна.
Вольфрам утверждает, что доказательство Смита является еще одним доказательством общего принципа вычислительной эквивалентности Вольфрама (PCE). [16] Этот принцип гласит, что если человек видит поведение, которое не является очевидно простым, поведение будет соответствовать вычислению, которое в некотором смысле является «максимально сложным». [17] Доказательство Смита вызвало дискуссию о точных рабочих условиях, которым должна удовлетворять машина Тьюринга, чтобы стать кандидатом универсальной машины.
Универсальная (2, 3) машина Тьюринга имеет мыслимые приложения. [18] Например, такая маленькая и простая машина может быть встроена или сконструирована с использованием небольшого числа частиц или молекул. Но алгоритм "компилятора" Смита не создает компактного или эффективного кода, по крайней мере, для чего-либо, кроме простейших случаев. Следовательно, результирующий код имеет тенденцию быть астрономически большим и очень неэффективным. Существуют ли более эффективные кодировки, позволяющие (2, 3) машине Тьюринга выполнять более быстрые вычисления, остается открытым вопросом.
Спор
Объявление о том, что доказательство Алекса Смита выиграло, было сделано без одобрения судейского комитета [19], как отметил Мартин Дэвис , член комитета, в сообщении в списке рассылки FOM :
- «Насколько мне известно, ни один член комитета не подтвердил достоверность этого 40-страничного доказательства. Решение о том, что доказательство Смита верное, похоже, было сделано полностью организацией Wolfram. Насколько я понимаю, ввод-вывод включает сложные кодировки ". [20]
Впоследствии Воан Пратт оспорил правильность этого доказательства в публичном списке обсуждений [21], отметив, что аналогичные методы позволили бы линейному ограниченному автомату (или LBA) быть универсальным, что противоречило бы известному результату неуниверсальности, полученному Ноамом Хомским. . Алекс Смит присоединился к списку рассылки после этого сообщения и ответил на следующий день, объяснив, что LBA потребуется перезапустить вручную, чтобы стать универсальным с той же начальной конфигурацией, в то время как его конструкция перезапускает машину Тьюринга автоматически без внешнего вмешательства. [22] Споры о доказательстве продолжались некоторое время между Алексом Смитом, Воаном Праттом и другими. [23]
Смотрите также
- Полнота по Тьюрингу - возможность моделирования любой машины Тьюринга
- Правило 110 - полный элементарный клеточный автомат по Тьюрингу
Рекомендации
- ^ Вольфрам, Стивен (2002). Новый вид науки . п. 709 . Проверено 10 февраля 2009 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ «Премия Вольфрама 2,3 за исследования машин Тьюринга» . Проверено 10 февраля 2009 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ «Машины Тьюринга с двумя буквами и двумя состояниями» . Сложные системы . 2010 . Проверено 25 октября 2017 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ «Студенческий приз по математике» . Натуральный . 2007 . Проверено 10 февраля 2009 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ Кейм, Брэндон (24 октября 2007 г.). «Студентка доказывает, что машина Тьюринга Вольфрама - простейший универсальный компьютер» . Проводной . Проверено 10 февраля 2009 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ Джефф Брамфил. «Nature.com» . Nature.com . Проверено 9 марта 2010 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ «Новый ученый» . Новый ученый . Проверено 9 марта 2010 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ «Бирмингемский университет» . Newscentre.bham.ac.uk . Проверено 9 марта 2010 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ «Математика в новостях математического общества» . Ams.org . Проверено 9 марта 2010 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ Крайтон, Бен (26 ноября 2007 г.). «Доказательство простого компьютера Тьюринга» . BBC News . Проверено 9 марта 2010 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ «Статья побитового Mag» . Статья в Bitwise Mag. 24 октября 2007 . Проверено 9 марта 2010 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ «Математическая ассоциация Америки» . Maa.org . Проверено 9 марта 2010 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ Минкель-младший (25 октября 2007 г.). «Автор нового вида науки платит старшекласснику $ 25 000 за определение простейшего компьютера» . Scientific American . Проверено 9 марта 2010 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ "плюс журнал" . Plus.maths.org . Проверено 9 марта 2010 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ Стюарт, Том (29 ноября 2007 г.). «Комплексное доказательство очень простого компьютера» . Хранитель . Лондон . Проверено 9 марта 2010 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ «Ответ Стивена Вольфрама в списке FOM» . Нью-Йоркский университет . Октябрь 2007 г.
- ^ «Премия Вольфрама и универсальные вычисления: теперь это ваша проблема» .
- ^ «Самый простой« универсальный компьютер »приносит студенту 25 000 долларов» . Новый ученый . 24 октября 2007 . Проверено 28 января 2016 . CS1 maint: обескураженный параметр ( ссылка )
- ^ http://cs.nyu.edu/pipermail/fom/2007-October/012163.html
- ^ http://cs.nyu.edu/pipermail/fom/2007-October/012132.html
- ^ "Послание Воана Пратта списку FOM" .
- ^ "Первый ответ Алекса Смита Воану Пратту в списке FOM" .
- ^ «Архив списка ФОМ за ноябрь 2007 года» . Cs.nyu.edu . Проверено 9 марта 2010 года . CS1 maint: обескураженный параметр ( ссылка )
Библиография
- Вольфрам, S (2002) Новый вид науки . Wolfram Media.
- Wolfram Research, Inc., «Объявлена премия за определение границ вычислений машины Тьюринга». Официальное объявление о том, что Алекс Смит выиграл приз.
- -, Вольфрам 2,3 Премия за исследования машин Тьюринга. Приглашение конкурсантам.
Историческое чтение
- Марвин Мински (1967) Вычисления: конечные и бесконечные машины . Прентис Холл.
- Тьюринг, A (1937) «О вычислимых числах в приложении к Entscheidungsproblem », Труды Лондонского математического общества, серия 2, 42 : 230-265.
- - (1938) «О вычислимых числах в приложении к Entscheidungsproblem . Исправление», Труды Лондонского математического общества, серия 2, 43 : 544-546.
Внешние ссылки
- Премия " Студенческая коряга по математике " Природа . Опубликовано в сети 24 октября 2007 г.
- « Колледж Kid Доказывает , что машина Тьюринга Вольфрама является простейшие универсального компьютера ,» Wired Science . Опубликовано в сети 24 октября 2007 г.
- " 'Универсальный компьютер' Простейшие выигрывает студент $ 25,000 ," New Scientist . Опубликовано в сети 24 октября 2007 г.
- « Премия Вольфрама и универсальные вычисления: теперь это ваша проблема » , журнал доктора Добба . Опубликовано в Интернете 22 октября 2007 г.
- Минкель-младший, « Автор нового вида науки платит студенту с умом 25 000 долларов за определение простейшего компьютера », Scientific American , 25 октября 2007 г.
- Из веток обсуждения Основ математики:
- Простые машины Тьюринга, универсальность, кодировки и т. Д.
- Простейшая универсальная машина Тьюринга
- Самая маленькая универсальная машина
- Утверждение Воана Пратта о том, что доказательство Смита недействительно
- Ответ Вольфрама Пратту на том же форуме
- Ответ Пратту Тодда Роуленда, одного из судей приза