Полнота по Тьюрингу
Полнота по Тьюрингу — характеристика исполнителя (множества вычисляющих элементов) в теории вычислимости, означающая возможность реализовать на нём любую вычислимую функцию, а также воссоздание себя самого. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных).
Свойство названо по имени Алана Тьюринга, разработавшего абстрактный вычислитель — машину Тьюринга, и давшего определение множества функций, вычислимых посредством машин Тьюринга.
Примеры[править | править код]
Большинство широко используемых языков программирования — тьюринг-полные. Это касается как императивных языков, таких как Паскаль, так и функциональных (Haskell) и языков логического программирования (Пролог). Некоторые языки программирования (Haskell, C++) обладают тьюринг-полнотой времени компиляции, помимо тьюринг-полноты времени исполнения.
Полны по Тьюрингу нормальный алгоритм Маркова, 2-теговая система, клеточный автомат с правилом 110, ингибиторная сеть Петри, лямбда-исчисление с бета-редукцией, неограниченные грамматики.
Неполны по Тьюрингу конечные автоматы, примитивно рекурсивные функции, контекстно-свободные и регулярные грамматики.
Универсальная система[править | править код]
В каждом тьюринг-полном классе вычислителей существует универсальный представитель класса, имитирующий выполнение произвольного заданного представителя класса. Так, например, универсальная машина Тьюринга по ленте, содержащей шифр произвольной заданной машины Тьюринга М и её входной цепочки В, имитирует выполнение М над В. В настоящее время построены универсальные машины Тьюринга, содержащие менее 23 инструкций[1] для комбинаций числа состояний-символов 4×6, 5×5. Универсальная ингибиторная сеть Петри содержит 56 вершин[2].
Примечания[править | править код]
- ↑ T. Neary Архивная копия от 24 сентября 2015 на Wayback Machine and D. Woods. Four small universal Turing machines. Fundamenta Informaticae, 91(1):123-144, 2009. Архивная копия от 24 сентября 2015 на Wayback Machine
- ↑ Zaitsev D.A. Архивная копия от 1 апреля 2022 на Wayback Machine Toward the Minimal Universal Petri Net, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2013, 1- 12.
Литература[править | править код]
- Brainerd, W.S., Landweber, L.H. Theory of Computation. — Wiley, 1974.
Ссылки[править | править код]
- c2.com Архивная копия от 8 апреля 2005 на Wayback Machine
 | Это заготовка статьи по информатике. Помогите Википедии, дополнив её. |