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

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

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

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

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

Полными по Тьюрингу являются также грамматики общего вида.

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