192
правки
Изменения
м
Зачастую В теории вычислимости ''исполнитель'' (множество вычисляющих элементов) называется '''Тьюринг-эквивалентные языки программирования называют Тьюринг-полнымиполным''', если на нём можно реализовать любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных).
Нет описания правки
Говорят, что задача является '''Тьюринг-полной''', если её можно решить, используя только [[Машина Тьюринга|машину Тьюринга ]] или любую систему, являющуюся Тьюринг-эквивалентной. {{Определение|definition =Вычислительное устройство является '''Тьюринг-эквивалентным''', если оно может эмулировать машину Тьюринга. }}В теории вычислимости исполнитель (множество вычисляющих элементов) называется Зачастую Тьюринг-полным, если на нём можно реализовать любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных)эквивалентные языки программирования называют Тьюринг-полными.
Любой полный по Тьюрингу язык достаточно универсальный, чтобы имитировать все другие (хотя и с потенциальным замедлением в работе). Такие языки эквивалентны в рамках вычислений, которые могут произвести. Полные по Тьюрингу языки настолько распространены, что их можно обнаружить даже в примитивных на первый взгляд системах, например, клеточных автоматах или мозаичных системах.
