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

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

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

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

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

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

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

Формальные определения [ править ]

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

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

История [ править ]

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

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

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

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

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

Теория вычислимости [ править ]

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

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

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

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

Оракулы Тьюринга [ править ]

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

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

Цифровая физика [ править ]

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

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

Примеры [ править ]

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

  • Теория автоматов
  • Формальная грамматика (генераторы языков)
  • Формальный язык (распознаватели языка)
  • Лямбда-исчисление
  • Машины Пост-Тьюринга
  • Расчет процесса

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

  • Все универсальные языки широко используются.
    • Языки процедурного программирования, такие как C , Pascal .
    • Объектно-ориентированные языки, такие как Java , Smalltalk или C # .
    • Multi-парадигме языков , таких как Ada , C ++ , Common Lisp , Fortran , Object Pascal , Python , R .
  • Большинство языков, использующих менее распространенные парадигмы:
    • Функциональные языки, такие как Lisp и Haskell .
    • Языки логического программирования, такие как Пролог .
    • Макропроцессор общего назначения, например m4 .
    • Декларативные языки, такие как XSLT . [3]
    • VHDL и другие языки описания оборудования.
    • TeX , система набора.
    • Эзотерические языки программирования , форма математического отдыха, в которой программисты решают, как создавать базовые программные конструкции на чрезвычайно сложном, но математически эквивалентном Тьюрингу языке.

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

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

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

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

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

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

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

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

  • Microsoft Excel [6]
  • Microsoft PowerPoint [7]

Видеоигры:

  • Крепость гномов [8]
  • OpenTTD [ необходима ссылка ]
  • Terraria [ необходима ссылка ]
  • Minecraft [9] [ самостоятельно опубликованный источник ]
  • Сапер [10]
  • LittleBigPlanet [9]
  • Баба - это ты [11] [12]
  • Факторио [13]
  • Города: горизонты [14]
  • Opus Magnum [15]
  • Портал 2 [16] [ самостоятельно опубликованный источник ]
  • Шэньчжэнь I / O [17]

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

  • Отель Хаббо [18]

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

  • Magic: The Gathering [9] [19]

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

  • Игра жизни Конвея [20] [21]

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

  • Шаблоны C ++ [22] [23]

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

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

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

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

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

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

Языки данных [ править ]

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

См. Также [ править ]

  • AI-полнота
  • Алгоритмическая теория информации
  • Иерархия Хомского
  • Тезис Черча – Тьюринга
  • Теория вычислимости
  • Внутренняя петля
  • Цикл (вычисления)
  • Машина, которая всегда останавливается
  • Теорема Райса
  • s mn теорема
  • Теорема о структурированной программе
  • Брезент Тьюринга

Заметки [ править ]

  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. DOI : 10.1109 / 85.707574 .
  3. ↑ Лайонс, Боб (30 марта 2001 г.). «Универсальная машина Тьюринга в XSLT» . Решения для интеграции B2B от Unidex . Архивировано 17 июля 2011 года . Проверено 5 июля 2010 года .
  4. ^ Boyer, Роберт S .; Мур, Дж. Стротер (май 1983 г.). Механическое доказательство полноты Тьюринга чистого Лиспа (PDF) (Технический отчет). Институт вычислительной техники Техасского университета в Остине. 37. Архивировано (PDF) из оригинала 22 сентября 2017 года.
  5. ^ Dfetter; Брейнбаас (8 августа 2011 г.). «Циклическая система тегов» . PostgreSQL вики . Проверено 10 сентября 2014 года .
  6. ^ «Объявление LAMBDA: превратите формулы Excel в пользовательские функции» . TECHCOMMUNITY.MICROSOFT.COM . 3 декабря 2020 . Проверено 8 декабря 2020 .
  7. ^ Wildenhain, Том (9 апреля 2020). «О полноте по Тьюрингу MS PowerPoint» (PDF) . [ самостоятельно опубликованный источник ]
  8. ^ Cedotal, Эндрю (16 апреля 2010). «Человек использует самую сложную компьютерную игру в мире, чтобы создать… рабочую машину Тьюринга» . Мэри Сью . Архивировано 27 июня 2015 года . Дата обращения 2 июня 2015 .
  9. ^ a b c Цвинкау, Андреас (20 октября 2013 г.). «Случайно полный по Тьюрингу» . Андреас Цвинкау . Архивировано из оригинала на 5 июня 2015 года . Дата обращения 2 июня 2015 .[ самостоятельно опубликованный источник ]
  10. ↑ Кэй, Ричард (31 мая 2007 г.). «Бесконечные версии тральщика являются полными по Тьюрингу» (PDF) . Страницы Сапера Ричарда Кея . Архивировано 2 февраля 2017 года (PDF) . Проверено 14 марта 2017 года . [ самостоятельно опубликованный источник ]
  11. ^ "БАБА ЗАВЕРШАЕТСЯ: Эскиз доказательства (v2)" . 25 марта 2019 . Дата обращения 2 июня 2020 .
  12. ^ "Твит Мэтью Родригеса (@ mattar0d) видео, демонстрирующего реализацию правила 110 сотового автомата в Baba Is You" . 25 марта 2019 . Дата обращения 2 июня 2020 .
  13. ^ "Я сделал программируемый полный компьютер по Тьюрингу в Factorio" . Reddit . 31 января 2016 . Дата обращения 2 февраля 2020 .
  14. ↑ Планкетт, Люк (16 июля 2019 г.). "Cities: Skylines Map становится компьютером с питанием от какашек" . Котаку . Проверено 16 июля 2019 .
  15. Рианна Колдуэлл, Брендан (20 ноября 2017 г.). «Игрок Opus Magnum делает алхимический компьютер» . Ружье Rock Paper . Проверено 23 сентября 2019 года .
  16. ↑ Татум, Александр (16 июля 2019). «Трехзначный двоичный калькулятор» . Steam . Проверено 1 июля 2019 года .
  17. ^ "SHENZHEN I / O - Игра жизни Конвея - YouTube" . www.youtube.com . Проверено 27 декабря 2020 года .
  18. ^ "Твиттер Habbo о реализации машины Тьюринга в игре" . 9 ноября 2020 . Проверено 11 ноября 2020 .
  19. ↑ Алекс Черчилль; Стелла Бидерман; Остин Херрик (2019). "Magic: The Gathering завершена по Тьюрингу". arXiv : 1904.09828 [ cs.AI ].
  20. ↑ Ренделл, Пол (12 января 2005 г.). «Машина Тьюринга в игре жизни Конвея» . Ренделл-Чердак . Архивировано 8 июля 2009 года . Проверено 22 июня 2009 года .[ самостоятельно опубликованный источник ]
  21. ^ Calcyman; Джонстон, Натаниэль (16 июня 2009 г.). «Спартанский универсальный компьютер-конструктор» . LifeWiki . Проверено 22 июня 2009 года .
  22. ^ Мейерс, Скотт (Скотт Дуглас) (2005). Эффективный C ++: 55 конкретных способов улучшить ваши программы и дизайн (3-е изд.). Река Аппер Сэдл, Нью-Джерси: Аддисон-Уэсли. ISBN 0321334876. OCLC  60425273 .
  23. ^ См. Историю TMP в Викиучебниках.
  24. ^ Долан, Стивен. "mov является полным по Тьюрингу" (PDF) . stedolan.net . Дата обращения 9 мая 2019 .

Дальнейшее чтение [ править ]

  • Брейнерд, WS; Ландвебер, LH (1974). Теория вычислений . Вайли. ISBN 0-471-09585-0.
  • Джайлз, Джим (24 октября 2007 г.). «Самый простой« универсальный компьютер »приносит студенту 25 000 долларов» . Новый ученый .
  • Херкен, Рольф, изд. (1995). Универсальная машина Тьюринга: обзор за полвека . Springer Verlag. ISBN 3-211-82637-8.
  • Тьюринг, AM (1936). «О вычислимых числах в приложении к Entscheidungsproblem» (PDF) . Труды Лондонского математического общества . 2. 42 : 230–265. DOI : 10.1112 / plms / s2-42.1.230 .
  • Тьюринг, AM (1938). «О вычислимых числах в приложении к Entscheidungsproblem: исправление». Труды Лондонского математического общества . 2. 43 : 544–546. DOI : 10.1112 / ПНИЛИ / s2-43.6.544 .

Внешние ссылки [ править ]

  • «Полный Тьюринга» . wiki.c2.com .