stringtranslate.com

полнота по Тьюрингу

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

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

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

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

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

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

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

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

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

История

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

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

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

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

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

Первым компьютером, способным на практике выполнять условное ветвление, и, следовательно, практически полным по Тьюрингу, был ENIAC в 1946 году. Компьютер Z4 Цузе был готов к работе в 1945 году, но он не поддерживал условное ветвление до 1950 года. [4]

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

Полнота по Тьюрингу — это абстрактное утверждение о способности, а не предписание конкретных языковых возможностей, используемых для реализации этой способности. Возможности, используемые для достижения полноты по Тьюрингу, могут быть совершенно разными; системы Fortran будут использовать конструкции циклов или, возможно, даже операторы goto для достижения повторения; Haskell и Prolog, почти полностью лишенные циклов, будут использовать рекурсию . Большинство языков программирования описывают вычисления на архитектурах фон Неймана , которые имеют память (ОЗУ и регистр) и блок управления. Эти два элемента делают эту архитектуру полной по Тьюрингу. Даже чистые функциональные языки являются полными по Тьюрингу. [8] [9]

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

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

Правило 110 и игра Конвея «Жизнь» — оба клеточные автоматы — являются полными по Тьюрингу.

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

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

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

Игры:

Социальные сети:

Языки программирования:

Биология:

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

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

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

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

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

Сноски

  1. ^ Можно утверждать, что Т[уринговское] вычисление [полное] является единственной парадигмой для теории, лежащей в основе компьютерной науки... Утверждается, что в настоящее время доминирующая парадигма компьютерной науки может быть охарактеризована теоретически как TC-вычисление, охватывающее языки программирования, и практически как вычислительное мышление, охватывающее методологии программирования. [1]

Ссылки

  1. ^ Майклсон, Грег (14 февраля 2020 г.). «Парадигмы программирования, полнота по Тьюрингу и вычислительное мышление». Искусство, наука и инженерия программирования . 4 (3). arXiv : 2002.06178 . doi :10.22152/programming-journal.org/2020/4/4.
  2. ^ Ходжес, Эндрю (1992) [1983], Алан Тьюринг: Энигма , Лондон: Burnett Books, стр. 111, ISBN 0-04-510060-8
  3. ^ Рохас, Рауль (1998). «Как сделать Z3 Цузе универсальным компьютером». Annals of the History of Computing . 20 (3): 51–54. doi :10.1109/85.707574.
  4. ↑ Рохас, Рауль (1 февраля 2014 г.). «Конрад Цузе и условный прыжок». Информатик-Спектр (на немецком языке). 37 (1): 50–53. дои : 10.1007/s00287-013-0717-9. ISSN  0170-6012. S2CID  1086397.
  5. ^ Schmidhuber, Jürgen (1997), Freksa, Christian; Jantzen, Matthias; Valk, Rüdiger (ред.), "Взгляд специалиста по информатике на жизнь, вселенную и всё остальное", Foundations of Computer Science: Potential — Theory — Cognition , Lecture Notes in Computer Science, т. 1337, Berlin, Heidelberg: Springer, стр. 201–208, arXiv : quant-ph/9904050 , doi :10.1007/bfb0052088, ISBN 978-3-540-69640-7, S2CID  17830241 , получено 23 мая 2022 г.
  6. ^ Dfetter; Breinbaas (8 августа 2011 г.). "Cyclic Tag System". PostgreSQL wiki . Получено 10 сентября 2014 г.
  7. ^ Lyons, Bob (30 марта 2001 г.). «Универсальная машина Тьюринга в XSLT». Решения по интеграции B2B от Unidex . Архивировано из оригинала 17 июля 2011 г. Получено 5 июля 2010 г.
  8. ^ Boyer, Robert S.; Moore, J. Strother (май 1983 г.). Механическое доказательство полноты Тьюринга чистого Lisp (PDF) (технический отчет). Институт вычислительной науки, Техасский университет в Остине. 37. Архивировано (PDF) из оригинала 22 сентября 2017 г.
  9. ^ Раубер, Томас; Рюнгер, Гудула (2013). Параллельное программирование: для многоядерных и кластерных систем (2-е изд.). Springer. ISBN 9783642378010.
  10. ^ "Представляем LAMBDA: превращаем формулы Excel в пользовательские функции". TECHCOMMUNITY.MICROSOFT.COM . 3 декабря 2020 г. . Получено 8 декабря 2020 г. .
  11. ^ Седотал, Эндрю (16 апреля 2010 г.). «Человек использует самую сложную в мире компьютерную игру, чтобы создать… рабочую машину Тьюринга». Мэри Сью . Архивировано из оригинала 27 июня 2015 г. Получено 2 июня 2015 г.
  12. ^ Планкетт, Люк (16 июля 2019 г.). «Города: карта горизонтов становится компьютером, работающим на какашках». Kotaku . Получено 16 июля 2019 г.
  13. ↑ Колдуэлл, Брендан (20 ноября 2017 г.). «Игрок Opus Magnum создает алхимический компьютер». Rock Paper Shotgun . Получено 23 сентября 2019 г.
  14. ^ Крайдер, Майкл. «Этот 8-битный процессор, встроенный в Minecraft, может запускать свои собственные игры». PCWorld . Получено 21 июля 2022 г.
  15. ^ Черчилль, Алекс; Бидерман, Стелла; Херрик, Остин (2020). Magic: The Gathering Is Turing Complete (PDF) . 10-я Международная конференция по развлечениям с алгоритмами.
  16. ^ Уэллетт, Дженнифер (23 июня 2019 г.). «Возможно построить машину Тьюринга в Magic: The Gathering». Ars Technica . Получено 12 марта 2023 г.
  17. ^ Кей, Ричард (31 мая 2007 г.). «Бесконечные версии минного тральщика являются полными по Тьюрингу» (PDF) . Архивировано из оригинала (PDF) 3 августа 2016 г. . Получено 8 июля 2016 г. .
  18. ^ "Твиттер-тред Habbo о реализации машины Тьюринга внутри игры". 9 ноября 2020 г. Получено 11 ноября 2020 г.
  19. ^ Мейерс, Скотт (Скотт Дуглас) (2005). Эффективный C++: 55 конкретных способов улучшить ваши программы и проекты (3-е изд.). Upper Saddle River, NJ: Addison-Wesley. ISBN 0321334876. OCLC  60425273.
  20. ^ Победитель 27-го IOCCC Карлини, Николас; Баррези, Антонио; Пайер, Матиас; Вагнер, Дэвид; Гросс, Томас Р. (август 2015 г.). «Изгиб потока управления: об эффективности целостности потока управления». Труды 24-й конференции USENIX по симпозиуму по безопасности . стр. 161–176. ISBN
     9781931971232.
  21. ^ Дэблер, Райан (23 сентября 2021 г.). «TypeScript и полнота по Тьюрингу». ITNEXT . LINKIT . Получено 12 ноября 2022 г. .
  22. ^ Долан, Стивен. "mov is Turing-complete" (PDF) . stedolan.net . Архивировано из оригинала (PDF) 14 февраля 2021 г. . Получено 9 мая 2019 г. .
  23. ^ Уильямс, Эл (21 марта 2021 г.). «Одна инструкция, которая правит всеми: компилятор C выдает только MOV». Hackaday . Получено 23 октября 2023 г. .
  24. ^ Break Me00 The MoVfuscator Превращаем mov в душераздирающий кошмар RE Кристофер Домас , получено 5 ноября 2022 г.
  25. ^ Шах, Шалин; Ви, Жасмин; Сонг, Тяньци; Сезе, Луис; Штраус, Карин ; Чэнь, Юань-Цзюэ; Рейф, Джон (4 мая 2020 г.). «Использование полимеразы, вытесняющей цепи, для программирования сетей химических реакций». Журнал Американского химического общества . 142 (21): 9587–9593. doi :10.1021/jacs.0c02240. ISSN  0002-7863. PMID  32364723. S2CID  218504535.
  26. ^ Чэнь, Юань-Цзюэ; Далчау, Нил; Шринивас, Ниранджан; Филлипс, Эндрю; Карделли, Лука; Соловейчик, Дэвид; Силиг, Георг (октябрь 2013 г.). «Программируемые химические контроллеры, сделанные из ДНК». Nature Nanotechnology . 8 (10): 755–762. Bibcode :2013NatNa...8..755C. doi :10.1038/nnano.2013.189. ISSN  1748-3395. PMC 4150546 . PMID  24077029. 
  27. ^ Шринивас, Ниранджан; Паркин, Джеймс; Силиг, Георг; Уинфри, Эрик; Соловейчик, Дэвид (15 декабря 2017 г.). «Динамические системы нуклеиновых кислот без ферментов». Science . 358 (6369): eaal2052. doi : 10.1126/science.aal2052 . ISSN  0036-8075. PMID  29242317.
  28. ^ Соловейчик, Дэвид; Зеелиг, Георг; Уинфри, Эрик (23 марта 2010 г.). «ДНК как универсальный субстрат для химической кинетики». Труды Национальной академии наук . 107 (12): 5393–5398. Bibcode : 2010PNAS..107.5393S. doi : 10.1073/pnas.0909380107 . ISSN  0027-8424. PMC 2851759. PMID 20203007  . 
  29. ^ Шапиро, Эхуд (7 декабря 1999 г.). «Механическая машина Тьюринга: план биомолекулярного компьютера». Interface Focus . 2 (4). Weizmann Institute of Science : 497–503. doi :10.1098/rsfs.2011.0118. PMC 3363030. PMID 22649583.  Архивировано из оригинала 3 января 2009 г. Получено 13 августа 2009 г. 

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

Внешние ссылки