192
правки
Изменения
→Критерии Тьюринг-полноты
==Критерии Тьюринг-полноты==
Если на языке программирования можно реализовать машину Тьюринга, то такой язык Тьюринг-полон, и наоборот. Возможность реализации машины Тьюринга на конкретном языке программирования можно ''грубо '' описать как перечень требований, которым этот язык должен для этого удовлетворять:
* Конечность (нет бесконечных символьных множеств и пр.).
* Фиксированное описание([https://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA формальность]).
* Всегда достаточный объём доступной памяти — в идеале здесь имеется в виду бесконечная неограниченная память, однако физические рамки не позволяют сделать память ЭВМ бесконечной, поэтому она просто должна быть ''"always big enough"''.
* Неограниченность времени выполнения— любая программа в должна иметь возможность работать до тех пор, пока не завершится.
* Возможность функциональной композиции (вызов одной функции из другой, рекурсия).
* Циклы Наличие циклов <tex>{\bf while}</tex> с прерыванием или эквивалентные эквивалентных имконструкций.
* Возможность останавливать выполнение (''halt'') или каким-то образом подавать сигнал о результатах выполнения.
* Представление множества натуральных чисел, понятие нуля и следующего числа. Возможны другие подобные системы.
* Поддержка входных и выходных данных (I/O), причём без формальных ограничений в объёме. Если Очевидно, что если любая программа, написанная на каком-то языке программирования, принимает на вход не более фиксированного n бит данных и возвращает не более n бит, этот язык не может быть Тьюринг-полным.
==Тьюринг-полнота и неполнота некоторых языков программирования==
