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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Примеры[править | править вики-текст]

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

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

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

Универсальная система[править | править вики-текст]

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

Библиография[править | править вики-текст]

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

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]

Примечания[править | править вики-текст]