Полнота по Тьюрингу - Turing completeness

Об использовании этого термина в теории относительной вычислимости на машинах-оракулах см. Редукция Тьюринга.

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

Связанная концепция - это концепция Эквивалентность Тьюринга - два компьютера P и Q называются эквивалентными, если P может моделировать Q, а Q может моделировать P. Тезис Черча – Тьюринга предполагает, что любая функция, значения которой могут быть вычислены алгоритм может быть вычислен машиной Тьюринга, и, следовательно, если какой-либо реальный компьютер может моделировать машину Тьюринга, он эквивалентен машине Тьюринга. А универсальная машина Тьюринга может использоваться для моделирования любой машины Тьюринга и, как следствие, вычислительных аспектов любого возможного реального компьютера.[NB 1]

Чтобы показать, что что-то является полным по Тьюрингу, достаточно показать, что это можно использовать для моделирования некоторой полной системы по Тьюрингу. Например, повелительный язык является полным по Тьюрингу, если условное ветвление (например, операторы «if» и «goto» или инструкция «переход при нулевом значении»; см. компьютер с одной командой ) и возможность изменять произвольное количество объем памяти (например, возможность поддерживать произвольное количество элементов данных). Конечно, никакая физическая система не может иметь бесконечную память; но если игнорировать ограничение конечной памяти, большинство языков программирования в остальном являются полными по Тьюрингу.

Нематематическое использование

В разговорный Термины "полный по Тьюрингу" или "эквивалент по Тьюрингу" используются для обозначения того, что любой реальный компьютер общего назначения или компьютерный язык может приблизительно имитировать вычислительные аспекты любого другого реального компьютера общего назначения или компьютерного языка. .

Реальные компьютеры, сконструированные до сих пор, можно функционально проанализировать как однопленочную машину Тьюринга («лента», соответствующая их памяти); таким образом, связанная математика может применяться, достаточно абстрагируя их работу. Однако реальные компьютеры имеют ограниченные физические ресурсы, поэтому они линейно ограниченный автомат полный. Напротив, универсальный компьютер определяется как устройство с полным набором инструкций по Тьюрингу, бесконечной памятью и бесконечным временем доступности.

Формальные определения

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

Полнота по Тьюрингу
Вычислительная система, которая может вычислить все значения Тьюринга.вычислимая функция называется полным по Тьюрингу (или мощным по Тьюрингу). В качестве альтернативы такая система может моделировать универсальная машина Тьюринга.
Эквивалентность Тьюринга
Полная по Тьюрингу система называется эквивалентной по Тьюрингу, если каждая функция, которую она может вычислить, также вычислима по Тьюрингу; т.е. он вычисляет в точности тот же класс функций, что и do Машины Тьюринга. В качестве альтернативы, система, эквивалентная Тьюрингу, может имитировать и моделировать универсальную машину Тьюринга. (Все известные полные по Тьюрингу системы эквивалентны Тьюрингу, что добавляет поддержку Тезис Черча – Тьюринга.)
(Вычислительная) универсальность
Система называется универсальной по отношению к классу систем, если она может вычислить каждую функцию, вычисляемую системами этого класса (или может моделировать каждую из этих систем). Обычно термин универсальность неявно используется по отношению к полному по Тьюрингу классу систем. Термин «слабо универсальный» иногда используется для обозначения системы (например, клеточный автомат ), универсальность которого достигается только изменением стандартного определения Машина Тьюринга чтобы включить входные потоки с бесконечным количеством единиц.

История

Полнота по Тьюрингу важна в том смысле, что каждый реальный проект вычислительного устройства может быть смоделирован с помощью универсальная машина Тьюринга. В Тезис Черча – Тьюринга утверждает, что это закон математики - что универсальная машина Тьюринга в принципе может выполнять любые вычисления, которые любая другая программируемая компьютер может. Это ничего не говорит об усилиях, необходимых для написания программа или время, которое может потребоваться машине для выполнения вычислений, или любые способности машины, которые не имеют ничего общего с вычислениями.

Чарльз Бэббидж с аналитическая машина (1830-е гг.) Была бы первой полной по Тьюрингу машиной, если бы она была построена в то время, когда была разработана. Бэббидж ценил, что машина способна на великие вычисления, включая примитивные логические рассуждения, но он не понимал, что никакая другая машина не может работать лучше. С 1830-х до 1940-х годов механические вычислительные машины, такие как сумматоры и умножители, были построены и улучшены, но они не могли выполнять условный переход и, следовательно, не были полными по Тьюрингу.

В конце 19 века Леопольд Кронекер сформулировал понятия вычислимости, определяя примитивные рекурсивные функции. Эти функции могут быть вычислены механически, но их недостаточно для создания универсального компьютера, потому что инструкции, которые их вычисляют, не допускают бесконечного цикла. В начале 20 века Дэвид Гильберт возглавил программу аксиоматизации всей математики с помощью точных аксиом и точных логических правил вывода, которые могли бы выполняться машиной. Вскоре стало ясно, что небольшого набора правил дедукции достаточно, чтобы произвести следствия любого набора аксиом. Эти правила были подтверждены Курт Гёдель в 1930 году, чтобы получить все теоремы.

Фактическое понятие вычислений было выделено вскоре после этого, начиная с Теорема Гёделя о неполноте. Эта теорема показала, что системы аксиом были ограничены при рассуждении о вычислениях, которые выводят их теоремы. Черч и Тьюринг независимо продемонстрировали, что теория Гильберта Entscheidungsproblem (проблема решения) была неразрешимой,[1] таким образом идентифицируя вычислительное ядро ​​теоремы о неполноте. Эта работа, наряду с работой Гёделя по общие рекурсивные функции, установлено, что существуют наборы простых инструкций, которые, собранные вместе, способны производить любые вычисления. Работа Гёделя показала, что понятие вычисления по сути уникально.

В 1941 г. Конрад Зузе завершил Z3 компьютер. В то время Цузе не был знаком с работами Тьюринга по вычислимости. В частности, в Z3 не хватало специальных средств для условного перехода, что не позволяло ему быть полным по Тьюрингу. Только в 1998 г. это показали Рохас и др. что Z3 способен к условным переходам и, следовательно, к завершению по Тьюрингу, за счет использования некоторых его функций непреднамеренным образом.[2]

Теория вычислимости

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

Классический пример - это проблема остановки: создать алгоритм, который принимает в качестве входных данных программу на некотором полном по Тьюрингу языке и некоторые данные, которые необходимо передать в который program и определяет, остановится ли программа, работающая с вводом, или будет продолжаться вечно. Создать алгоритм, который сможет это сделать для немного входов, но сделать это в целом невозможно. Для любой характеристики конечного результата программы невозможно определить, сохранится ли эта характеристика.

Эта невозможность создает проблемы при анализе реальных компьютерных программ. Например, нельзя написать инструмент, который полностью защищает программистов от написания бесконечных циклов или защищает пользователей от ввода данных, которые могут вызвать бесконечные циклы.

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

Оракулы Тьюринга

Основная статья: Машина Oracle

Компьютер с доступом к бесконечной ленте данных может быть более мощным, чем машина Тьюринга: например, лента может содержать решение проблемы проблема остановки или другая проблема, неразрешимая по Тьюрингу. Такая бесконечная лента данных называется Оракул Тьюринга. Даже оракул Тьюринга со случайными данными не вычислим (с вероятностью 1 ), поскольку вычислений неисчислимо много, а оракулов - бесчисленное множество. Таким образом, компьютер со случайным оракулом Тьюринга может вычислить то, что машина Тьюринга не может.

Цифровая физика

Смотрите также: Тезис Черча – Тьюринга § Философские последствия

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

Примеры

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

Наиболее языки программирования (их абстрактные модели, возможно, с некоторыми конкретными конструкциями, предполагающими исключение конечной памяти), традиционные и нетрадиционные, являются полными по Тьюрингу. Это включает в себя:

Немного переписывать системы полны по Тьюрингу.

Полнота по Тьюрингу - это абстрактное утверждение способностей, а не рецепт конкретных языковых функций, используемых для реализации этой способности. Функции, используемые для достижения полноты по Тьюрингу, могут быть совершенно разными; Фортран системы будут использовать конструкции цикла или, возможно, даже идти к высказывания для достижения повторения; Haskell и Prolog, почти полностью лишенные цикла, будут использовать рекурсия. Большинство языков программирования описывают вычисления на архитектуры фон Неймана, которые имеют память (RAM и регистр) и блок управления. Эти два элемента делают эту архитектуру полной по Тьюрингу. Даже чистый функциональные языки полны по Тьюрингу.[4][NB 2]

Полнота по Тьюрингу в декларативной SQL реализуется через рекурсивные общие табличные выражения.[5] Неудивительно, что процедурные расширения SQL (PLSQL и др.) также полны по Тьюрингу. Это иллюстрирует одну причину того, почему относительно мощные неполные по Тьюрингу языки встречаются редко: чем мощнее язык изначально, тем сложнее задачи, к которым он применяется, и тем скорее его недостаточная полнота воспринимается как недостаток, поощряя его расширение, пока оно не станет полным по Тьюрингу.

Нетипизированный лямбда-исчисление является полным по Тьюрингу, но многие типизированные лямбда-исчисления, включая Система F, не. Ценность типизированных систем основана на их способности отображать наиболее типичные компьютерные программы при одновременном обнаружении большего количества ошибок.

Правило 110 и Игра жизни Конвея, обе клеточные автоматы, являются полными по Тьюрингу.

Непреднамеренная полнота по Тьюрингу

Некоторые игры и другое программное обеспечение являются полными по Тьюрингу случайно, то есть не намеренно.

Программного обеспечения:

Видеоигры:

Социальные медиа:

Карточные игры:

Игры с нулевым лицом (симуляторы):

Вычислительные языки:

Компьютерное железо:

  • инструкция x86 MOV[22]

Не полные по Тьюрингу языки

Существует множество вычислительных языков, которые не являются полными по Тьюрингу. Одним из таких примеров является набор обычные языки, которые порождаются обычные выражения и которые признаны конечные автоматы. Более мощным, но еще не полным по Тьюрингу расширением конечных автоматов является категория выталкивающие автоматы и контекстно-свободные грамматики, которые обычно используются для генерации деревьев синтаксического анализа на начальном этапе программы. составление. Дополнительные примеры включают некоторые из ранних версий языков пиксельных шейдеров, встроенных в Direct3D и OpenGL расширения.[нужна цитата ]

В полное функциональное программирование языки, такие как Благотворительность и Эпиграмма, все функции являются общими и должны завершаться. Благотворительность использует систему типов и управляющие конструкции на основе теория категорий, тогда как Epigram использует зависимые типы. В ПЕТЛЯ язык разработан так, что он вычисляет только те функции, которые примитивно рекурсивный. Все они вычисляют правильные подмножества полных вычислимых функций, поскольку полный набор полных вычислимых функций не вычислимо перечислимый. Кроме того, поскольку все функции на этих языках являются общими, алгоритмы для рекурсивно перечислимые множества не могут быть написаны на этих языках, в отличие от машин Тьюринга.

Хотя (нетипизированный) лямбда-исчисление является полным по Тьюрингу, просто типизированное лямбда-исчисление не является.

Языки данных

Понятие полноты по Тьюрингу не распространяется на такие языки, как XML, HTML, JSON, и YAML, потому что они обычно используются для представления структурированных данных, а не для описания вычислений. Иногда их называют языки разметки, или, точнее, «языки-контейнеры» или «языки описания данных».[нужна цитата ]

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

Примечания

  1. ^ UTM не может моделировать не вычислительные аспекты, такие как Ввод / вывод.
  2. ^ Следующая книга представляет собой введение в вычислительные модели: Раубер, Томас; Рюнгер, Гудула (2013). Параллельное программирование: для многоядерных и кластерных систем (2-е изд.). Springer. ISBN  9783642378010.

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

  1. ^ Ходжес, Эндрю (1992) [1983], Алан Тьюринг: Загадка, Лондон: Burnett Books, стр. 111, ISBN  0-04-510060-8
  2. ^ Рохас, Рауль (1998). «Как сделать Z3 Цузе универсальным компьютером». Анналы истории вычислительной техники. 20 (3): 51–54. Дои:10.1109/85.707574.
  3. ^ Лайонс, Боб (30 марта 2001 г.). «Универсальная машина Тьюринга в XSLT». Решения для интеграции B2B от Unidex. В архиве из оригинала 17 июля 2011 г.. Получено 5 июля 2010.
  4. ^ Бойер, Роберт С .; Мур, Дж. Стротер (май 1983 г.). Механическое доказательство полноты по Тьюрингу чистого Лиспа (PDF) (Технический отчет). Институт вычислительной техники Техасского университета в Остине. 37. В архиве (PDF) из оригинала от 22 сентября 2017 г.
  5. ^ Дфеттер; Брейнбаас (8 августа 2011 г.). «Система циклических тегов». PostgreSQL вики. Получено 10 сентября 2014.
  6. ^ Уилденхайн, Том (9 апреля 2020 г.). «О полноте по Тьюрингу MS PowerPoint» (PDF).[самостоятельно опубликованный источник ]
  7. ^ Седоталь, Эндрю (16 апреля 2010 г.). «Человек использует самую сложную компьютерную игру в мире, чтобы создать… рабочую машину Тьюринга». Мэри Сью. В архиве из оригинала 27 июня 2015 г.. Получено 2 июн 2015.
  8. ^ а б c Цвинкау, Андреас (20 октября 2013 г.). "Случайно завершенный по Тьюрингу". Андреас Цвинкау. Архивировано из оригинал 5 июня 2015 г.. Получено 2 июн 2015.[самостоятельно опубликованный источник ]
  9. ^ Кэй, Ричард (31 мая 2007 г.). "Бесконечные версии тральщика завершены по Тьюрингу" (PDF). Страницы Сапера Ричарда Кея. В архиве (PDF) из оригинала 2 февраля 2017 г.. Получено 14 марта 2017.[самостоятельно опубликованный источник ]
  10. ^ "БАБА ЗАВЕРШАЕТСЯ: Эскиз доказательства (v2)". 25 марта 2019 г.. Получено 2 июн 2020.
  11. ^ "Твит Мэтью Родригеса (@ mattar0d) о видео, показывающем реализацию правила 110 сотового автомата в Baba Is You". 25 марта 2019 г.. Получено 2 июн 2020.
  12. ^ «Я сделал программируемый полный компьютер по Тьюрингу в Factorio». Reddit. 31 января 2016 г.. Получено 2 февраля 2020.
  13. ^ Планкетт, Люк (16 июля 2019 г.). "Cities: Skylines Map превращается в компьютер с питанием от какашки". Котаку. Получено 16 июля 2019.
  14. ^ Колдуэлл, Брендан (20 ноября 2017 г.). «Игрок Opus Magnum делает алхимический компьютер». Ружье из каменной бумаги. Получено 23 сентября 2019.
  15. ^ Татум, Александр (16 июля 2019). «Трёхзначный двоичный калькулятор». Пар. Получено 1 июля 2019.
  16. ^ «Тема в Твиттере Habbo о реализации машины Тьюринга внутри игры». 9 ноября 2020 г.. Получено 11 ноября 2020.
  17. ^ Алекс Черчилль; Стелла Бидерман; Остин Херрик (2019). "Magic: The Gathering завершена по Тьюрингу". arXiv:1904.09828 [cs.AI ].
  18. ^ Ренделл, Пол (12 января 2005 г.). "Машина Тьюринга в игре жизни Конвея". Rendell-Attic. В архиве из оригинала от 8 июля 2009 г.. Получено 22 июн 2009.[самостоятельно опубликованный источник ]
  19. ^ Кальциман; Джонстон, Натаниэль (16 июня 2009 г.). «Спартанский универсальный компьютер-конструктор». LifeWiki. Получено 22 июн 2009.
  20. ^ Мейерс, Скотт (Скотт Дуглас) (2005). Эффективный C ++: 55 конкретных способов улучшить ваши программы и дизайн (3-е изд.). Река Аппер Сэдл, Нью-Джерси: Аддисон-Уэсли. ISBN  0321334876. OCLC  60425273.
  21. ^ Видеть История ТМП в Викиучебниках.
  22. ^ Долан, Стивен. "mov является полным по Тьюрингу" (PDF). stedolan.net. Получено 9 мая 2019.

дальнейшее чтение

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