Полнота по Тьюрингу
В теории вычислимости система правил манипулирования данными (например, модель вычислений компьютера , набор команд , язык программирования или клеточный автомат ) называется тьюринг-полной или вычислительно универсальной , если ее можно использовать для моделирования. любая машина Тьюринга [ нужна цитата ] (придуман английским математиком и ученым-компьютерщиком Аланом Тьюрингом ). Это означает, что эта система способна распознавать или декодировать другие наборы правил манипулирования данными. Полнота по Тьюрингу используется как способ выразить мощь такого набора правил манипулирования данными. Практически все современные языки программирования являются полными по Тьюрингу. [ нужна цитата ]
Связанная с этим концепция — это концепция эквивалентности Тьюринга : два компьютера P и Q называются эквивалентными, если P может моделировать Q, а Q может моделировать P. [ нужна цитата ] Тезис Чёрча-Тьюринга предполагает, что любая функция, значения которой могут быть вычислены с помощью алгоритма , может быть вычислена с помощью машины Тьюринга, и, следовательно, если любой реальный компьютер может моделировать машину Тьюринга, он эквивалентен машине Тьюринга по Тьюрингу. Универсальную машину Тьюринга можно использовать для моделирования любой машины Тьюринга и, как следствие, чисто вычислительных аспектов любого возможного реального компьютера. [ нужна цитата ]
Чтобы показать, что что-то является полным по Тьюрингу, достаточно продемонстрировать, что его можно использовать для моделирования некоторой полной по Тьюрингу системы. Ни одна физическая система не может иметь бесконечную память, но если игнорировать ограничение конечной памяти, большинство языков программирования в противном случае будут полными по Тьюрингу. [ нужна цитата ]
Нематематическое использование [ править ]
В разговорной речи термины «Тьюринг-полный» и «Тьюринг-эквивалент» используются для обозначения того, что любой реальный компьютер общего назначения или компьютерный язык может приблизительно моделировать вычислительные аспекты любого другого реального компьютера общего назначения или компьютерного языка. компьютерный язык. В реальной жизни это приводит к практическим концепциям виртуализации и эмуляции вычислений . [ нужна цитата ]
Реальные компьютеры, созданные на данный момент, можно функционально анализировать как одноленточную машину Тьюринга (которая использует «ленту» в качестве памяти); таким образом, соответствующая математика может применяться, достаточно абстрагируя их действие. Однако реальные компьютеры имеют ограниченные физические ресурсы, поэтому они представляют собой только линейный ограниченный автомат . Напротив, абстракция универсального компьютера определяется как устройство с полным по Тьюрингу набором команд, бесконечной памятью и бесконечным доступным временем. [ нужна цитата ]
Формальные определения [ править ]
В теории вычислимости для описания вычислительной мощности вычислительной системы (например, абстрактной машины или языка программирования ) используются несколько тесно связанных терминов:
- Полнота по Тьюрингу
- Вычислительная система, которая может вычислить любую вычислимую по Тьюрингу функцию, называется полной по Тьюрингу (или мощной по Тьюрингу). В качестве альтернативы такая система может моделировать универсальную машину Тьюринга .
- Тьюринговая эквивалентность
- Полная по Тьюрингу система называется эквивалентной по Тьюрингу, если каждая функция, которую она может вычислить, также вычислима по Тьюрингу; т. е. он вычисляет точно тот же класс функций, что и машины Тьюринга . Альтернативно, эквивалентной Тьюрингу системой является система, которая может моделировать универсальную машину Тьюринга и моделироваться с ее помощью. (Все известные физически реализуемые Тьюринг-полные системы являются Тьюринг-эквивалентными, что добавляет поддержку тезису Чёрча-Тьюринга . [ нужна цитата ] )
- (Вычислительная) универсальность
- Система называется универсальной по отношению к классу систем, если она может вычислить любую функцию, вычислимую системами этого класса (или может моделировать каждую из этих систем). Обычно термин «универсальность» молчаливо используется по отношению к тьюринг-полному классу систем. Термин «слабо универсальная» иногда используется для обозначения системы (например, клеточного автомата ), универсальность которой достигается только за счет изменения стандартного определения машины Тьюринга таким образом, чтобы она включала входные потоки с бесконечным числом единиц.
История [ править ]
Полнота по Тьюрингу важна тем, что любую реальную конструкцию вычислительного устройства можно смоделировать с помощью универсальной машины Тьюринга . Тезис Чёрча -Тьюринга утверждает, что это закон математики: универсальная машина Тьюринга в принципе может выполнять любые вычисления, которые может выполнить любой другой программируемый компьютер . Это ничего не говорит об усилиях, необходимых для написания программы , или о времени, которое может потребоваться машине для выполнения вычислений, или о любых способностях, которыми может обладать машина, не имеющих ничего общего с вычислениями.
Чарльза Бэббиджа ( Аналитическая машина 1830-е годы) была бы первой машиной, полной по Тьюрингу, если бы она была построена в то время, когда была спроектирована. Бэббидж понимал, что машина способна на великие расчеты, включая примитивные логические рассуждения, но не понимал, что ни одна другая машина не может добиться большего. [ нужна цитата ] С 1830-х по 1940-е годы механические вычислительные машины, такие как сумматоры и умножители, были построены и усовершенствованы, но они не могли выполнять условный переход и, следовательно, не были полными по Тьюрингу.
В конце 19 века Леопольд Кронекер сформулировал понятия вычислимости, определив примитивно-рекурсивные функции . Эти функции можно вычислить путем механического вычисления, но их недостаточно для создания универсального компьютера, поскольку инструкции, которые их вычисляют, не допускают бесконечного цикла. В начале 20-го века Дэвид Гильберт возглавил программу аксиоматизации всей математики с помощью точных аксиом и точных логических правил дедукции, которые могли быть выполнены машиной. Вскоре стало ясно, что небольшого набора правил дедукции достаточно, чтобы получить следствия из любого набора аксиом. в 1930 году доказал, Курт Гёдель что этих правил достаточно для вывода любой теоремы.
Само понятие вычислений вскоре было изолировано, начиная с теоремы Гёделя о неполноте . Эта теорема показала, что системы аксиом были ограничены при рассуждениях о вычислениях, из которых выводятся их теоремы. (проблема принятия решений) Гильберта Чёрч и Тьюринг независимо друг от друга продемонстрировали, что проблема Entscheidungsproblem неразрешима. [1] тем самым определяя вычислительное ядро теоремы о неполноте. Эта работа, наряду с работой Гёделя по общерекурсивным функциям , установила, что существуют наборы простых инструкций, которые, собранные вместе, способны производить любые вычисления. Работа Гёделя показала, что понятие вычислений по сути уникально.
В 1941 году Конрад Цузе завершил работу над компьютером Z3 . В то время Цузе не был знаком с работами Тьюринга по вычислимости. В частности, у Z3 не было специальных возможностей для условного прыжка, что не позволяло ему быть полным по Тьюрингу. Однако в 1998 году Рохас показал, что Z3 способен имитировать условные переходы и, следовательно, в теории является полным по Тьюрингу. Для этого ее ленточная программа должна быть достаточно длинной, чтобы выполнить все возможные пути через обе стороны каждой ветки. [2]
Первым компьютером, способным выполнять условное ветвление на практике и, следовательно, полным по Тьюрингу на практике, был ENIAC в 1946 году. Компьютер Цузе Z4 начал работать в 1945 году, но он не поддерживал условное ветвление до 1950 года. [3]
Теория вычислимости [ править ]
Теория вычислимости использует модели вычислений ли они для анализа проблем и определения, вычислимы и при каких обстоятельствах. Первый результат теории вычислимости состоит в том, что существуют проблемы, для которых невозможно предсказать, что будет делать (полная по Тьюрингу) система в течение сколь угодно длительного времени.
Классическим примером является проблема остановки : создать алгоритм, который принимает в качестве входных данных программу на некотором языке, полном по Тьюрингу, и некоторые данные, которые необходимо передать в эту программу, и определяет, остановится ли программа, работающая на входных данных, в конечном итоге или продолжит работу. навсегда. входных данных, тривиально Создать алгоритм, который может сделать это для некоторых , но в целом это невозможно. Для любой характеристики конечного результата программы невозможно определить, сохранится ли эта характеристика.
Эта невозможность создает проблемы при анализе реальных компьютерных программ. Например, невозможно написать инструмент, который полностью защитит программистов от написания бесконечных циклов или защитит пользователей от ввода входных данных, которые могут вызвать бесконечные циклы.
Вместо этого можно ограничить выполнение программы только в течение фиксированного периода времени ( timeout ) или ограничить мощность инструкций управления потоком (например, предоставляя только циклы, которые перебирают элементы существующего массива). Однако другая теорема показывает, что существуют проблемы, решаемые с помощью Тьюринг-полных языков, которые не могут быть решены ни одним языком с ограниченными возможностями цикла (т. е. языками, которые гарантируют, что каждая программа в конечном итоге завершится остановкой). Таким образом, любой такой язык не является полным по Тьюрингу. Например, язык, на котором программы гарантированно завершатся и остановятся, не может вычислить вычислимую функцию, созданную диагональным аргументом Кантора для всех вычислимых функций на этом языке.
Оракулы Тьюринга [ править ]
Компьютер, имеющий доступ к бесконечной ленте данных, может быть более мощным, чем машина Тьюринга: например, лента может содержать решение проблемы остановки или какой-либо другой неразрешимой по Тьюрингу проблемы. Такая бесконечная лента данных называется оракулом Тьюринга . Даже оракул Тьюринга со случайными данными не вычислим ( с вероятностью 1 ), поскольку существует только счетное количество вычислений, но несчетное количество оракулов. Таким образом, компьютер со случайным оракулом Тьюринга может вычислять то, чего не может сделать машина Тьюринга.
Цифровая физика [ править ]
Все известные законы физики имеют последствия, которые можно вычислить с помощью ряда приближений на цифровом компьютере. Гипотеза под названием « цифровая физика» утверждает, что это не случайно, поскольку сама Вселенная вычислима на универсальной машине Тьюринга. Это означало бы, что физически невозможно построить компьютер более мощный, чем универсальная машина Тьюринга. [4]
Примеры [ править ]
Вычислительные системы (алгебры, исчисления), которые рассматриваются как полные по Тьюрингу системы, предназначены для изучения теоретической информатики . Они призваны быть максимально простыми, чтобы было легче понять пределы вычислений. Вот некоторые из них:
- Теория автоматов
- Формальная грамматика (языковые генераторы)
- Формальный язык (распознаватели языка)
- Лямбда-исчисление
- Пост-Тьюринговые машины
- Исчисление процессов
Большинство языков программирования (их абстрактные модели, возможно, с некоторыми конкретными конструкциями, предполагающими опущение конечной памяти), как традиционных, так и нетрадиционных, являются полными по Тьюрингу. Это включает в себя:
- Все языки общего назначения широко используются.
- Процедурные языки программирования, такие как C , Pascal .
- Объектно-ориентированные языки, такие как Java , Smalltalk или C# .
- Мультипарадигмальные такие как Ada , C++ , Common Lisp , Fortran , JavaScript , Object Pascal , Perl , Python , R. языки ,
- Большинство языков используют менее распространенные парадигмы:
- Функциональные языки, такие как Lisp и Haskell .
- логического программирования Языки , такие как Пролог .
- Макропроцессор общего назначения, например m4 .
- Декларативные языки, такие как SQL и XSLT . [5] [6]
- VHDL и другие языки описания оборудования.
- TeX — система набора текста.
- Эзотерические языки программирования — форма математического отдыха , в которой программисты отрабатывают базовые конструкции программирования на чрезвычайно сложном, но математически эквивалентном Тьюрингу языке.
Некоторые системы перезаписи являются полными по Тьюрингу.
Полнота по Тьюрингу — это абстрактное утверждение о способности, а не предписание конкретных языковых функций, используемых для реализации этой способности. Функции, используемые для достижения полноты по Тьюрингу, могут быть совершенно разными; Системы Фортрана будут использовать конструкции циклов или, возможно, даже операторы перехода для достижения повторения; Haskell и Prolog, почти полностью лишенные циклов, будут использовать рекурсию . Большинство языков программирования описывают вычисления на архитектурах фон Неймана , которые имеют память (ОЗУ и регистр) и блок управления. Эти два элемента делают эту архитектуру полной по Тьюрингу. Даже чистые функциональные языки полны по Тьюрингу. [7] [8]
Полнота по Тьюрингу в декларативном SQL реализуется посредством рекурсивных общих табличных выражений . Неудивительно, что процедурные расширения SQL ( PLSQL и т. д.) также являются полными по Тьюрингу. Это иллюстрирует одну из причин, почему относительно мощные, неполные по Тьюрингу языки встречаются редко: чем мощнее язык изначально, тем сложнее задачи, для решения которых он применяется, и тем скорее его недостаточная полнота начинает восприниматься как недостаток, поощряя его расширение до тех пор, пока оно не станет полным по Тьюрингу.
Нетипизированное лямбда-исчисление является Тьюринг-полным, но многие типизированные лямбда-исчисления, включая Систему F , таковыми не являются. Ценность типизированных систем основана на их способности представлять большинство типичных компьютерных программ, обнаруживая при этом больше ошибок.
Правило 110 и «Игра жизни» Конвея — клеточные автоматы — полны по Тьюрингу.
Непреднамеренная по Тьюрингу полнота
Некоторые программы и видеоигры являются полными по Тьюрингу случайно, то есть не намеренно.
Программное обеспечение:
Игры:
- Крепость гномов [10]
- Города: Горизонты [11]
- Отличная работа [12]
- Шахтерское ремесло [13]
- Магия: Сбор [14] [15]
- с бесконечной сеткой Сапер [16]
Социальные медиа:
Вычислительные языки:
- Шаблоны С++ [18]
- строка формата printf [19]
- Система типов TypeScript [20]
- сборки x86 Инструкция MOV [21] [22] [23]
Биология:
- Сети химических реакций [24] [25] [26] [27] и ДНК-компьютеры на основе ферментов [28] было показано, что они эквивалентны Тьюрингу
-Тьюринг- языки Не полные
Существует множество вычислительных языков, которые не являются полными по Тьюрингу. Одним из таких примеров является множество регулярных языков , которые генерируются регулярными выражениями и распознаются конечными автоматами . Более мощное, но все же не полное по Тьюрингу расширение конечных автоматов — это категория автоматов с выталкиванием и контекстно-свободных грамматик , которые обычно используются для генерации деревьев синтаксического анализа на начальном этапе компиляции программы . Дополнительные примеры включают некоторые ранние версии языков пиксельных шейдеров, встроенные в Direct3D и OpenGL . расширения [ нужна цитата ]
В языках функционального программирования , таких как Charity и Epigram , все функции являются тотальными и должны завершаться. Charity использует систему типов и конструкции управления , основанные на теории категорий , тогда как Epigram использует зависимые типы . Язык LOOP функции спроектирован таким образом, что он вычисляет только примитивно-рекурсивные . Все они вычисляют правильные подмножества всех вычислимых функций, поскольку полный набор всех вычислимых функций не является вычислимо перечислимым . Кроме того, поскольку все функции в этих языках тотальны, алгоритмы для рекурсивно перечислимых множеств на них нельзя написать , в отличие от машин Тьюринга.
Хотя (нетипизированное) лямбда-исчисление является Тьюринг-полным, просто типизированное лямбда-исчисление таковым не является.
См. также [ править ]
Ссылки [ править ]
- ^ Ходжес, Эндрю (1992) [1983], Алан Тьюринг: Загадка , Лондон: Burnett Books, стр. 111, ISBN 0-04-510060-8
- ^ Рохас, Рауль (1998). «Как сделать Zuse Z3 универсальным компьютером» . Анналы истории вычислительной техники . 20 (3): 51–54. дои : 10.1109/85.707574 .
- ^ Рохас, Рауль (1 февраля 2014 г.). «Конрад Цузе и условный прыжок» [Конрад Цузе и условный прыжок]. Спектр компьютерных наук (на немецком языке). 37 (1): 50–53. дои : 10.1007/s00287-013-0717-9 . ISSN 0170-6012 . S2CID 1086397 .
- ^ Шмидхубер, Юрген (1997), Фрекса, Кристиан; Янцен, Матиас; Валк, Рюдигер (ред.), «Взгляд ученого-компьютерщика на жизнь, вселенную и все остальное» , «Основы информатики: потенциал — теория — познание» , конспекты лекций по информатике, том. 1337, Берлин, Гейдельберг: Springer, стр. 201–208, arXiv : quant-ph/9904050 , doi : 10.1007/bfb0052088 , ISBN 978-3-540-69640-7 , S2CID 17830241 , получено 23 мая 2022 г.
- ^ Дфеттер; Брейнбаас (8 августа 2011 г.). «Циклическая система тегов» . PostgreSQL вики . Проверено 10 сентября 2014 г.
- ^ Лайонс, Боб (30 марта 2001 г.). «Универсальная машина Тьюринга в XSLT» . Решения для интеграции B2B от Unidex . Архивировано из оригинала 17 июля 2011 года . Проверено 5 июля 2010 г.
- ^ Бойер, Роберт С.; Мур, Дж. Стротер (май 1983 г.). Механическое доказательство полноты по Тьюрингу чистого Lisp (PDF) (технический отчет). Институт компьютерных наук Техасского университета в Остине. 37. Архивировано (PDF) из оригинала 22 сентября 2017 г.
- ^ Раубер, Томас; Рюнгер, Гудула (2013). Параллельное программирование: для многоядерных и кластерных систем (2-е изд.). Спрингер. ISBN 9783642378010 .
- ^ «Анонсируем LAMBDA: превратите формулы Excel в пользовательские функции» . TECHCOMMUNITY.MICROSOFT.COM . 3 декабря 2020 г. Проверено 8 декабря 2020 г.
- ^ Чедотал, Эндрю (16 апреля 2010 г.). «Человек использует самую сложную в мире компьютерную игру, чтобы создать… работающую машину Тьюринга» . Мэри Сью . Архивировано из оригинала 27 июня 2015 года . Проверено 2 июня 2015 г.
- ^ Планкетт, Люк (16 июля 2019 г.). «Карта городов: горизонты становится компьютером, работающим на фекалиях» . Котаку . Проверено 16 июля 2019 г.
- ^ Колдуэлл, Брендан (20 ноября 2017 г.). «Игрок Opus Magnum делает алхимический компьютер» . Каменный бумажный дробовик . Проверено 23 сентября 2019 г.
- ^ Крайдер, Майкл. «Этот 8-битный процессор, встроенный в Minecraft, может запускать собственные игры» . ПКМир . Проверено 21 июля 2022 г.
- ^ Черчилль, Алекс; Бидерман, Стелла; Херрик, Остин (2020). Magic: The Gathering Is Turing Complete (PDF) . 10-я Международная конференция «Развлечение с алгоритмами».
- ^ Уэллетт, Дженнифер (23 июня 2019 г.). «В Magic: The Gathering можно построить машину Тьюринга» . Арс Техника . Проверено 12 марта 2023 г.
- ^ Kaye, Richard (31 May 2007). "Infinite versions of minesweeper are Turing complete" (PDF). Archived from the original (PDF) on 3 August 2016. Retrieved 8 July 2016.
- ^ «Тема Хаббо в Твиттере о реализации машины Тьюринга в игре» . 9 ноября 2020 г. Проверено 11 ноября 2020 г.
- ^ Мейерс, Скотт (Скотт Дуглас) (2005). Эффективный C++: 55 конкретных способов улучшить ваши программы и проекты (3-е изд.). Река Аппер-Сэддл, Нью-Джерси: Аддисон-Уэсли. ISBN 0321334876 . OCLC 60425273 .
- ^ 27-й победитель IOCCC
Карлини, Николас; Баррези, Антонио; Пайер, Матиас; Вагнер, Дэвид; Гросс, Томас Р. (август 2015 г.). «Изгиб потока управления: об эффективности целостности потока управления» . Материалы 24-й конференции USENIX по симпозиуму по безопасности . стр. 161–176. ISBN 9781931971232 . - ^ Даблер, Райан (23 сентября 2021 г.). «TypeScript и полнота по Тьюрингу» . ЭТОДАЛЕЕ . ЛИНКИТ . Проверено 12 ноября 2022 г.
- ^ Долан, Стивен. «mov является полным по Тьюрингу» (PDF) . stedolan.net . Архивировано из оригинала (PDF) 14 февраля 2021 года . Проверено 9 мая 2019 г.
- ^ Уильямс, Эл (21 марта 2021 г.). «Одна инструкция, чтобы управлять ими всеми: компилятор C генерирует только MOV» . Хакадей . Проверено 23 октября 2023 г.
- ^ Break Me00 The MoVfuscator Превращение фильма в душераздирающий кошмар RE Кристофер Домас , получено 5 ноября 2022 г.
- ^ Шах, Шалин; Ви, Жасмин; Сун, Тяньци; Сезе, Луис; Штраус, Карин ; Чен, Юань-Цзюэ; Рейф, Джон (4 мая 2020 г.). «Использование полимеразы, вытесняющей цепи, для программирования сетей химических реакций». Журнал Американского химического общества . 142 (21): 9587–9593. дои : 10.1021/jacs.0c02240 . ISSN 0002-7863 . ПМИД 32364723 . S2CID 218504535 .
- ^ Чен, Юань-Цзюэ; Далчау, Нил; Шринивас, Ниранджан; Филлипс, Эндрю; Карделли, Лука; Соловейчик, Давид; Зеилиг, Георг (октябрь 2013 г.). «Программируемые химические контроллеры из ДНК» . Природные нанотехнологии . 8 (10): 755–762. Бибкод : 2013NatNa...8..755C . дои : 10.1038/nnano.2013.189 . ISSN 1748-3395 . ПМК 4150546 . ПМИД 24077029 .
- ^ Шринивас, Ниранджан; Паркин, Джеймс; Зеилиг, Георг; Уинфри, Эрик; Соловейчик, Давид (15 декабря 2017 г.). «Безферментные динамические системы нуклеиновых кислот» . Наука . 358 (6369): eaal2052. дои : 10.1126/science.aal2052 . ISSN 0036-8075 . ПМИД 29242317 .
- ^ Соловейчик, Давид; Зеилиг, Георг; Уинфри, Эрик (23 марта 2010 г.). «ДНК как универсальный субстрат химической кинетики» . Труды Национальной академии наук . 107 (12): 5393–5398. Бибкод : 2010PNAS..107.5393S . дои : 10.1073/pnas.0909380107 . ISSN 0027-8424 . ПМЦ 2851759 . ПМИД 20203007 .
- ^ Шапиро, Эхуд (7 декабря 1999 г.). «Механическая машина Тьюринга: проект биомолекулярного компьютера» . Фокус на интерфейсе . 2 (4). Научный институт Вейцмана : 497–503. дои : 10.1098/rsfs.2011.0118 . ПМК 3363030 . ПМИД 22649583 . Архивировано из оригинала 3 января 2009 года . Проверено 13 августа 2009 г.
Дальнейшее чтение [ править ]
- Брейнерд, штат Вашингтон; Ландвебер, Л.Х. (1974). Теория вычислений . Уайли. ISBN 0-471-09585-0 .
- Джайлз, Джим (24 октября 2007 г.). «Простейший «универсальный компьютер» принес студенту 25 000 долларов» . Новый учёный .
- Херкен, Рольф, изд. (1995). Универсальная машина Тьюринга: обзор полувека . Спрингер Верлаг. ISBN 3-211-82637-8 .
- Тьюринг, AM (1936). «О вычислимых числах с применением к проблеме Entscheidungs» (PDF) . Труды Лондонского математического общества . 2. 42 : 230–265. дои : 10.1112/plms/s2-42.1.230 . S2CID 73712 .
- Тьюринг, AM (1938). «О вычислимых числах с применением к проблеме Entscheidungs: исправление». Труды Лондонского математического общества . 2. 43 : 544–546. дои : 10.1112/plms/s2-43.6.544 .
Внешние ссылки [ править ]
- «Полный Тьюринг» . wiki.c2.com .