Вольфрамовая машина Тьюринга с 2 состояниями и 3 символами - Википедия - Wolframs 2-state 3-symbol Turing machine

Машины Тьюринга
Машина
Варианты
Наука

В его книге Новый вид науки, Стивен Вольфрам описал универсальный 2 состояния 5 символов Машина Тьюринга, и предположил, что 2-состояние 3-символьная машина Тьюринга (далее (2,3) Машина Тьюринга) также может быть универсальным.[1]

14 мая 2007 года Вольфрам объявил, что приз в размере 25 000 долларов будет выигран первым человеком, который докажет или опровергнет универсальность (2,3) машины Тьюринга.[2] 24 октября 2007 года было объявлено, что приз выиграл Алекс Смит, студент факультета электроники и вычислительной техники. Бирмингемский университет, за его доказательство универсальности, хотя изначально это доказательство оспаривалось.

Описание

В следующей таблице указаны действия, которые должна выполнить машина Тьюринга в зависимости от того, является ли ее текущее состояние А или же B, а текущий считываемый символ - 0, 1 или 2. Записи в таблице указывают символ, который должен быть напечатан, направление, в котором должна двигаться головка ленты, и последующее состояние машины.

АB
0P1, R,BP2, L,А
1P2, L,АP2, R,B
2П1, Л,АP0, R,А

(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][16]

Доказательство показало, что машина эквивалентна варианту система тегов уже известно как универсальный. Смит первым построил последовательность систем правил, показывающих, что (2,3) машина Тьюринга способна производить произвольные конечные вычисления. Затем он применил новый подход, чтобы распространить эту конструкцию на неограниченные вычисления. Доказательство проходит в два этапа. Первая часть имитирует конечную эволюцию любой двухцветной циклической системы тегов. Эмуляция представляет собой составную часть серии имитаций, включающих индексированные системы правил от «система 0» до «система 5». Каждая система правил имитирует следующую в последовательности. Затем Смит показал, что, хотя начальное условие (2, 3) машины Тьюринга не повторяется, построение этого начального условия не является универсальным. Следовательно, (2, 3) машина Тьюринга универсальна.

Вольфрам утверждает, что доказательство Смита - еще одно свидетельство генерала Вольфрама. Принцип вычислительной эквивалентности (PCE).[17] Этот принцип гласит, что если человек видит поведение, которое не является очевидно простым, поведение будет соответствовать вычислению, которое в некотором смысле является «максимально сложным».[18] Доказательство Смита вызвало дискуссию о точных рабочих условиях, которым должна удовлетворять машина Тьюринга, чтобы стать кандидатом на универсальную машину.

Универсальная (2, 3) машина Тьюринга имеет мыслимые приложения.[19] Например, такая маленькая и простая машина может быть встроена или сконструирована с использованием небольшого числа частиц или молекул. Но алгоритм "компилятора" Смита не создает компактного или эффективного кода, по крайней мере, для чего-либо, кроме простейших случаев. Следовательно, результирующий код имеет тенденцию быть астрономически большим и очень неэффективным. Существуют ли более эффективные кодировки, позволяющие (2, 3) машине Тьюринга выполнять более быстрые вычисления, остается открытым вопросом.

Спор

Объявление о том, что доказательство Алекса Смита выиграло, было сделано без одобрения судейского комитета.[20] как отметил Мартин Дэвис, член комитета, в должности в Список рассылки FOM:

«Насколько мне известно, ни один член комитета не утвердил достоверность этого 40-страничного доказательства. Решение о том, что доказательство Смита верное, похоже, было сделано полностью организацией Wolfram. Насколько я понимаю, ввод-вывод включает сложные кодировки ".[21]

Воан Пратт впоследствии оспорила правильность этого доказательства в публичном списке обсуждений,[22] отмечая, что аналогичные методы позволят линейно ограниченный автомат (или LBA) быть универсальным, что противоречило бы известному результату неуниверсальности из-за Ноам Хомский. Алекс Смит присоединился к списку рассылки после этого сообщения и ответил на следующий день, объяснив, что LBA потребуется перезапустить вручную, чтобы стать универсальным с той же начальной конфигурацией, в то время как его конструкция перезапускает машину Тьюринга автоматически без внешнего вмешательства.[23] Некоторое время дискуссии по поводу доказательства продолжались между Алексом Смитом, Воганом Праттом и другими.[24]

Смотрите также

Рекомендации

  1. ^ Вольфрам, Стивен (2002). Новый вид науки. п. 709. Получено 10 февраля 2009.
  2. ^ «Премия Вольфрама 2,3 за исследования машин Тьюринга». Получено 10 февраля 2009.
  3. ^ «Машины Тьюринга с двумя буквами и двумя состояниями». Сложные системы. 2010. Получено 25 октября 2017.
  4. ^ "Студенческий приз по математике". Естественный. 2007. Получено 10 февраля 2009.
  5. ^ Кейм, Брэндон (24 октября 2007 г.). «Студентка доказывает, что машина Тьюринга Вольфрама - простейший универсальный компьютер». Проводной. Получено 10 февраля 2009.
  6. ^ Джефф Брамфил. "Nature.com". Nature.com. Получено 9 марта 2010.
  7. ^ «Новый ученый». Новый ученый. Получено 9 марта 2010.
  8. ^ "Thaindian.com". Thaindian.com. Получено 9 марта 2010.
  9. ^ "Бирмингемский университет". Newscentre.bham.ac.uk. Получено 9 марта 2010.
  10. ^ «Математика в новостях от математического общества». Ams.org. Получено 9 марта 2010.
  11. ^ Крайтон, Бен (26 ноября 2007 г.). «Доказательство простого компьютера Тьюринга». Новости BBC. Получено 9 марта 2010.
  12. ^ "Статья в Bitwise Mag". Статья в Bitwise Mag. 24 октября 2007 г.. Получено 9 марта 2010.
  13. ^ «Математическая ассоциация Америки». Maa.org. Получено 9 марта 2010.
  14. ^ Минкель, Дж. Р. (25 октября 2007 г.). «Автор нового вида науки платит старшекласснику $ 25 000 за определение простейшего компьютера». Scientific American. Получено 9 марта 2010.
  15. ^ "плюс журнал". Plus.maths.org. Получено 9 марта 2010.
  16. ^ Стюарт, Том (29 ноября 2007 г.). «Комплексное доказательство очень простого компьютера». Хранитель. Лондон. Получено 9 марта 2010.
  17. ^ "Ответ Стивена Вольфрама в списке FOM". Нью-Йоркский университет. Октябрь 2007 г.
  18. ^ «Премия Вольфрама и универсальные вычисления: теперь это ваша проблема».
  19. ^ «Самый простой« универсальный компьютер »приносит студенту 25 000 долларов». Новый ученый. 24 октября 2007 г.. Получено 28 января 2016.
  20. ^ http://cs.nyu.edu/pipermail/fom/2007-October/012163.html
  21. ^ http://cs.nyu.edu/pipermail/fom/2007-October/012132.html
  22. ^ "Послание Воана Пратта списку FOM".
  23. ^ "Первый ответ Алекса Смита Воану Пратту в списке FOM".
  24. ^ "Архив списка ФОМ за ноябрь 2007 г.". Cs.nyu.edu. Получено 9 марта 2010.

Библиография

Историческое чтение

внешняя ссылка