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

Свойство названо по имени Алана Тьюринга , разработавшего абстрактный вычислитель — машину Тьюринга, и давшего определение множества функций, вычислимых посредством машин Тьюринга.

Примеры

Большинство широко используемых языков программирования — тьюринг-полные. Это касается как императивных языков , таких как Паскаль , так и функциональных ( Haskell ) и языков логического программирования ( Пролог ). Некоторые языки программирования (Haskell, C++ ) обладают тьюринг-полнотой времени компиляции, помимо тьюринг-полноты времени исполнения.

Полный по Тьюрингу нормальный алгоритм Маркова , , клеточный автомат с правилом 110 , ингибиторная сеть Петри , лямбда-исчисление с бета-редукцией . Полными по Тьюрингу являются также неограниченные грамматики .

Примерами неполных по Тьюрингу формализмов являются конечные автоматы , примитивно рекурсивные функции , контекстно-свободные и регулярные грамматики.

Универсальная система

В каждом тьюринг-полном классе вычислителей существует универсальный представитель класса, имитирующий выполнение произвольного заданного представителя класса. Так, например, универсальная машина Тьюринга по ленте, содержащей шифр произвольной заданной машины Тьюринга М и её входной цепочки В, имитирует выполнение М над В. В настоящее время построены универсальные машины Тьюринга, содержащие менее 23 инструкций для комбинаций числа состояний-символов 4×6, 5×5. Универсальная ингибиторная сеть Петри содержит 56 вершин .

Примечания

Литература

• Brainerd, W.S., Landweber, L.H. Theory of Computation. — Wiley, 1974.

Ссылки

• от 8 апреля 2005 на Wayback Machine