192
правки
Изменения
Нет описания правки
==Введение==
Говорят, что задача является '''Тьюринг-полной''', если её можно решить, используя только [[Машина Тьюринга|машину Тьюринга]] или любую систему, являющуюся Тьюринг-эквивалентной.
{{Определение
В теории вычислимости ''исполнитель'' (множество вычисляющих элементов) называется '''Тьюринг-полным''', если на нём можно реализовать любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных).
Любой полный по Тьюрингу язык достаточно универсальный, чтобы имитировать все другие (хотя и с потенциальным замедлением в работе). Такие языки эквивалентны в рамках вычислений, которые могут произвести. Полные по Тьюрингу языки настолько распространены, что их можно обнаружить даже в примитивных на первый взгляд системах, например, [Линейный клеточный автомат, эквивалентность МТ|клеточных автоматах ] или мозаичных системах.
На практике полнота по Тьюрингу — идеализация. Компьютеры имеют ограниченное количество памяти и будут работать ограниченное количество времени, прежде чем их выключат.
Если на языке программирования можно реализовать машину Тьюринга, то такой язык Тьюринг-полон, и наоборот. Возможность реализации машины Тьюринга на конкретном языке программирования можно грубо описать как перечень требований, которым этот язык должен для этого удовлетворять:
* Конечность (нет бесконечных символьных множеств и пр.).
* Фиксированное описание.
* Всегда достаточный объём доступной памяти — в идеале здесь имеется в виду бесконечная память, однако физические рамки не позволяют сделать память ЭВМ бесконечной, поэтому она просто должна быть ''"always big enough"''.
* Неограниченность времени выполнения.
* Возможность функциональной композиции (вызов одной функции из другой, рекурсия).
* Циклы <tex>{\bf while }</tex> с прерыванием или эквивалентные им.
* Возможность останавливать выполнение (''halt'') или каким-то образом подавать сигнал о результатах выполнения.
* Представление множества натуральных чисел, понятие "следующее число"нуля и следующего числа. Возможны другие подобные системы.
* Поддержка входных и выходных данных (I/O), причём без ограничений в объёме. Если любая программа, написанная на каком-то языке программирования, принимает на вход не более фиксированного n бит данных и возвращает не более n бит, этот язык не может быть Тьюринг-полным.
==Тьюринг-полнота и неполнота некоторых языков программирования==
Доказать Тьюринг-полноту языка программирования можно, предложив способ реализации машины Тьюринга на этом языке. Кроме того, можно предложить на нём интерпретатор языка на другом Тьюринг-полном языкеполного языка.
===Assembly language===
Язык Ассемблера сильно ограничендостаточно примитивен относительно языков программирования высокого уровня: он рассчитан на архитектуру с конечной памятью и работает с конечным набором регистров. Однако, не был бы он полным по Тьюрингу, не были бы Тьюринг-полны и другие любые высокоуровневые языки программирования.
Всё необходимое для машины Тьюринга на asm можно сделать примерно так:
ADDS r0, r0, #1 ; <font color=green>сдвиг ленты вправо</font> ADDS r0, r0, #-1 ; <font color=green>сдвиг ленты влево</font> ADDS [r0], [r0], #1 ; <font color=green>инкремент значения, на которое "указывает" головка ленты</font> ADDS [r0], [r0], #-1 ; <font color=green>декремент значения, на которое "указывает" головка ленты</font>
И далее использовать инструкцию ''<tex>\mathrm{BEQ'' }</tex> или ей подобную, чтобы выполнять определённую последовательность команд при определённом текущем значении, таким образом обеспечив ветвление.
===Pascal===
Язык Pascal позволяет смоделировать ленту машины Тьюринга с помощью двунаправленного списка из переменных, создаваемых оператором ''<tex>\mathrm{new''}</tex>, семантика которого не предполагает отказа в создании переменной. Также с помощью списков
можно смоделировать сколь угодно большие числа. Стандарт не накладывает никаких ограничений: указательный тип абстрактен, множество значений указательного типа языком не ограничено.
В Паскале есть еще один тип данных с неограниченным множеством значений, файловый, также пригодный для моделирования ленты машины Тьюринга и представления больших чисел. Достаточно утверждений для очевидности Тьюринг-полноты языка Pascal.
|[[Файл:gcc_asm.png|400px|thumb|Результат работы GCC]]
|[[Файл:mov_asm.png|400px|thumb|Результат работы M/o/Vfuscator]]
|-|[[Файл:Demo_mov.gif|right|thumb|900px500px|Простые числа с использованием одной инструкции]]
|}
Нововведения новых версий HTML/CSS позволяют построить<ref>[http://eli.fox-epste.in/rule110-full.html Rule 110]</ref> [https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D0%BE_110 правило 110], которое является Тьюринг-полным.
===Minecraft<ref>[https://www.youtube.com/watch?v=7sNge0Ywz-M|Demonstrating the CPU. Then coughing a lot. Sorry about that. I may be dying.]</ref>Excel===
===Little Big Planet<ref>[https://www.youtube.com/watch?v=13GOFa1C4e4| LittleBigLife — The Game of Life in LittleBigPlanet]</ref>Тьюринг-полнота в играх===
Little Big Planet<ref>[https://www.youtube.com/watch?v===[[Неразрешимость игры Braid13GOFa1C4e4|BraidLittleBigLife — The Game of Life in LittleBigPlanet]]===</ref>
Super Mario World<ref>[https://www.youtube.com/watch?v===Excel===hB6eY73sLV0 SNES Code Injection -- Flappy Bird in SMW]</ref> [[Неразрешимость игры Braid|Braid]]
==Тьюринговская трясина==
==См. также==
* [[Машина Тьюринга]]
==Примечания==
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Вычислительные формализмы]]
[[Категория: Машина Тьюринга]]
