stringtranslate.com

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

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

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

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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

Игры:

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

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

Биология:

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

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

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

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

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

Примечания

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

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

  1. ^ Ходжес, Эндрю (1992) [1983], Алан Тьюринг: Загадка , Лондон: Burnett Books, стр. 111, ISBN 0-04-510060-8
  2. ^ Рохас, Рауль (1998). «Как сделать Zuse Z3 универсальным компьютером». Анналы истории вычислительной техники . 20 (3): 51–54. дои : 10.1109/85.707574.
  3. ↑ Рохас, Рауль (1 февраля 2014 г.). «Конрад Цузе и условный прыжок». Информатик-Спектр (на немецком языке). 37 (1): 50–53. дои : 10.1007/s00287-013-0717-9. ISSN  0170-6012. S2CID  1086397.
  4. ^ Шмидхубер, Юрген (1997), Фрекса, Кристиан; Янцен, Матиас; Валк, Рюдигер (ред.), «Взгляд ученого-компьютерщика на жизнь, вселенную и все остальное», « Основы информатики: потенциал — теория — познание» , конспект лекций по информатике, Берлин, Гейдельберг: Springer, vol. 1337, стр. 201–208, arXiv : quant-ph/9904050 , doi : 10.1007/bfb0052088, ISBN 978-3-540-69640-7, S2CID  17830241 , получено 23 мая 2022 г.
  5. ^ Дфеттер; Брейнбаас (8 августа 2011 г.). «Циклическая система тегов». PostgreSQL вики . Проверено 10 сентября 2014 г.
  6. ↑ Лайонс, Боб (30 марта 2001 г.). «Универсальная машина Тьюринга в XSLT». Решения для интеграции B2B от Unidex . Архивировано из оригинала 17 июля 2011 года . Проверено 5 июля 2010 г.
  7. ^ Бойер, Роберт С.; Мур, Дж. Стротер (май 1983 г.). Механическое доказательство полноты по Тьюрингу чистого Lisp (PDF) (технический отчет). Институт компьютерных наук Техасского университета в Остине. 37. Архивировано (PDF) из оригинала 22 сентября 2017 г.
  8. ^ «Анонс LAMBDA: превратите формулы Excel в пользовательские функции» . TECHCOMMUNITY.MICROSOFT.COM . 3 декабря 2020 г. Проверено 8 декабря 2020 г.
  9. ↑ Чедотал, Эндрю (16 апреля 2010 г.). «Человек использует самую сложную компьютерную игру в мире, чтобы создать… работающую машину Тьюринга». Мэри Сью . Архивировано из оригинала 27 июня 2015 года . Проверено 2 июня 2015 г.
  10. ↑ Планкетт, Люк (16 июля 2019 г.). «Города: Карта горизонтов становится компьютером, работающим на фекалиях». Котаку . Проверено 16 июля 2019 г.
  11. ↑ Колдуэлл, Брендан (20 ноября 2017 г.). «Игрок Opus Magnum создает алхимический компьютер». Каменно-бумажный дробовик . Проверено 23 сентября 2019 г.
  12. ^ Крайдер, Майкл. «Этот 8-битный процессор, встроенный в Minecraft, может запускать собственные игры». ПКМир . Проверено 21 июля 2022 г.
  13. ^ Черчилль, Алекс; Бидерман, Стелла; Херрик, Остин (2020). Magic: The Gathering Is Turing Complete (PDF) . 10-я Международная конференция «Развлечение с алгоритмами».
  14. ↑ Уэллетт, Дженнифер (23 июня 2019 г.). «В Magic: The Gathering можно построить машину Тьюринга». Арс Техника . Проверено 12 марта 2023 г.
  15. ↑ Кэй, Ричард (31 мая 2007 г.). «Бесконечные версии тральщика полны по Тьюрингу» (PDF) . Архивировано из оригинала (PDF) 3 августа 2016 года . Проверено 8 июля 2016 г.
  16. ^ "Тема Хаббо в Твиттере о реализации машины Тьюринга в игре" . 9 ноября 2020 г. Проверено 11 ноября 2020 г.
  17. ^ Мейерс, Скотт (Скотт Дуглас) (2005). Эффективный C++: 55 конкретных способов улучшить ваши программы и проекты (3-е изд.). Река Аппер-Сэддл, Нью-Джерси: Аддисон-Уэсли. ISBN 0321334876. ОСЛК  60425273.
  18. ^ 27-й победитель IOCCC Карлини, Николас; Баррези, Антонио; Пайер, Матиас; Вагнер, Дэвид; Гросс, Томас Р. (август 2015 г.). «Изгиб потока управления: об эффективности целостности потока управления». Материалы 24-й конференции USENIX по симпозиуму по безопасности . стр. 161–176. ISBN
     9781931971232.
  19. ↑ Даблер, Райан (23 сентября 2021 г.). «TypeScript и полнота по Тьюрингу». ЭТОДАЛЕЕ . ЛИНКИТ . Проверено 12 ноября 2022 г.
  20. ^ Долан, Стивен. «mov является полным по Тьюрингу» (PDF) . stedolan.net . Архивировано из оригинала (PDF) 14 февраля 2021 года . Проверено 9 мая 2019 г.
  21. ↑ Уильямс, Эл (21 марта 2021 г.). «Одна инструкция, чтобы управлять ими всеми: компилятор C генерирует только MOV». Хакадей . Проверено 23 октября 2023 г.
  22. ^ Break Me00 The MoVfuscator Превращает движение в душераздирающий кошмар RE Кристофер Домас , получено 5 ноября 2022 г.
  23. ^ Шах, Шалин; Ви, Жасмин; Сун, Тяньци; Сезе, Луис; Штраус, Карин ; Чен, Юань-Цзюэ; Рейф, Джон (4 мая 2020 г.). «Использование полимеразы, вытесняющей цепи, для программирования сетей химических реакций». Журнал Американского химического общества . 142 (21): 9587–9593. doi : 10.1021/jacs.0c02240. ISSN  0002-7863. PMID  32364723. S2CID  218504535.
  24. ^ Чен, Юань-Цзюэ; Далчау, Нил; Шринивас, Ниранджан; Филлипс, Эндрю; Карделли, Лука; Соловейчик, Давид; Зеилиг, Георг (октябрь 2013 г.). «Программируемые химические контроллеры из ДНК». Природные нанотехнологии . 8 (10): 755–762. Бибкод : 2013NatNa...8..755C. дои : 10.1038/nnano.2013.189. ISSN  1748-3395. ПМК 4150546 . ПМИД  24077029. 
  25. ^ Шринивас, Ниранджан; Паркин, Джеймс; Зеилиг, Георг; Уинфри, Эрик; Соловейчик, Давид (15 декабря 2017 г.). «Безферментные динамические системы нуклеиновых кислот». Наука . 358 (6369): eaal2052. дои : 10.1126/science.aal2052 . ISSN  0036-8075. ПМИД  29242317.
  26. ^ Соловейчик, Давид; Зеилиг, Георг; Уинфри, Эрик (23 марта 2010 г.). «ДНК как универсальный субстрат химической кинетики». Труды Национальной академии наук . 107 (12): 5393–5398. Бибкод : 2010PNAS..107.5393S. дои : 10.1073/pnas.0909380107 . ISSN  0027-8424. ПМЦ 2851759 . ПМИД  20203007. 
  27. ↑ Шапиро, Эхуд (7 декабря 1999 г.). «Механическая машина Тьюринга: проект биомолекулярного компьютера». Фокус на интерфейсе . Институт науки Вейцмана . 2 (4): 497–503. дои : 10.1098/rsfs.2011.0118. ПМК 3363030 . PMID  22649583. Архивировано из оригинала 3 января 2009 года . Проверено 13 августа 2009 г. 

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

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