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