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

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