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