192
правки
Изменения
Нет описания правки
Говорят, что задача является Тьюринг-полной, если её можно решить, используя только машину Тьюринга или любую систему, являющуюся Тьюринг-эквивалентной. Зачастую Тьюринг-эквивалентные языки программирования называют Тьюринг-полными.
===Критерии Тьюринг-полноты===
Если на языке программирования можно реализовать машину Тьюринга, то такой язык Тьюринг-полон, и наоборот. Возможность реализации машины Тьюринга на конкретном языке программирования можно грубо описать как перечень требований, которым этот язык должен для этого удовлетворять:
* Конечность (нет бесконечных символьных множеств и пр.)
* Фиксированное описание
* Всегда достаточный объём доступной памяти — в идеале здесь имеется в виду бесконечная память, однако физические рамки не позволяют сделать память ЭВМ бесконечной, поэтому она просто должна быть "always big enough".
* Неограниченность времени выполнения
* Возможность функциональной композиции (вызов одной функции из другой, рекурсия)
* Циклы while с прерыванием или им эквивалентные
* Возможность останавливать выполнение или каким-то образом подавать сигнал о результатах выполнения
* Представление множества натуральных чисел, понятие "следующее число". Возможны другие подобные системы.
* Поддержка входных и выходных данных (I/O), причём без ограничений в объёме. Если любая программа, написанная на каком-то языке программирования, принимает на вход не более 5 бит данных и возвращает не более 5 бит, этот язык не может быть Тьюринг-полным.
===Тьюринг-полнота некоторых языков программирования===
