Изменения

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

Любой полный по Тьюрингу язык достаточно универсальный, чтобы имитировать все другие В теории вычислимости ''исполнитель'' (хотя и с потенциальным замедлением в работемножество вычисляющих элементов). Такие языки эквивалентны в рамках вычисленийназывается '''Тьюринг-полным''', которые могут произвестиесли на нём можно реализовать любую вычислимую функцию. Полные по Тьюрингу языки настолько распространены, что их можно обнаружить даже в примитивных на первый взгляд системахДругими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, клеточных автоматах машина Тьюринга) или мозаичных системахпрограмма для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных).

На практике полнота Любой полный по Тьюрингу — идеализацияязык достаточно универсален, чтобы иметь возможность имитировать любой другой язык (хотя и с потенциальным замедлением в работе). Компьютеры имеют ограниченное количество памяти и будут работать ограниченное количество времениТакие языки эквивалентны в рамках вычислений, которые могут произвести. Полные по Тьюрингу языки настолько распространены, прежде чем что их выключатможно обнаружить даже в примитивных на первый взгляд системах, например, [[Линейный клеточный автомат, эквивалентность МТ | клеточных автоматах]] или мозаичных системах.

Если на языке программирования можно реализовать машину Тьюринга, то такой язык Тьюринг-полон, и наоборот. Возможность реализации машины Тьюринга на конкретном языке программирования можно ''грубо '' описать как перечень требований, которым этот язык должен для этого удовлетворять:

* Конечность (нет бесконечных символьных множеств и пр.).

* Фиксированное описание(формальность<ref>[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 Википедия — Формальный язык]</ref>).

* Всегда достаточный объём доступной памяти — в идеале здесь имеется в виду бесконечная неограниченная память, однако физические рамки не позволяют сделать память ЭВМ бесконечной, поэтому она просто должна быть ''"always big enough"''.

* Неограниченность времени выполнения— любая программа в должна иметь возможность работать до тех пор, пока не завершится.

* Возможность функциональной композиции (вызов одной функции из другой, рекурсия).

* Циклы Наличие циклов <tex>{\bf while }</tex> с прерыванием или эквивалентные эквивалентных имконструкций.

* Возможность останавливать выполнение (''halt'') или каким-то образом подавать сигнал о результатах выполнения.

* Представление множества натуральных чисел, понятие "следующее число"нуля и следующего числа. Возможны другие подобные системы.

* Поддержка входных и выходных данных (I/O), причём без формальных ограничений в объёме. Если Очевидно, что если любая программа, написанная на каком-то языке программирования, принимает на вход не более фиксированного n бит данных и возвращает не более n бит, этот язык не может быть Тьюринг-полным.

Доказать Тьюринг-полноту языка программирования можно, предложив способ реализации машины Тьюринга на этом языке. Кроме того, можно предложить на нём интерпретатор языка на другом Тьюринг-полном языкеполного языка.

Мы можем HTML можно назвать HTML языком программирования только в контексте формальной полемики. На деле он является языком гипертекстовой разметки и ни чем больше. Но читатель должен пониматьТ. е. на HTML можно совершить только некоторую ограниченную совокупность действий, что если нет четко прописанных стандартовинтерпретируемых браузером, то однако никто не запрещает сделать язык, идентичный по синтаксису с HTML, но интерпретируемый совершенно по другому таким образом, чтобы он был полным по Тьюрингу.

!style="background-color:#EEE;padding:2px 8px"| '''Машинно-зависимостьЗависимость от архитектуры процессора'''

|style="background-color:#FFF;padding:2px 8px"| 19651995

Шаблоны C++ позволяют производить сложные вычисления ещё на стадии компиляции программы. Впервые это было продемонстрировано Эрвином Унрухом, который реализовал рекурсивный алгоритм распознавания простых чисел в процессе компиляции. Позже в статье Университета Индиана было продемонстрировано кодирование машины Тьюринга в шаблонах C++<ref>[http://web.archive.org/web/20131101122512/http://ubietylab.net/ubigraph/content/Papers/pdf/CppTuring.pdf кодирование машины Тьюринга в шаблонах C++Templates are Turing-complete]</ref>.

Аналогично C++ Templates, Generics, несмотря на свои отличия, тоже оказались полными по Тьюрингу, что было подтверждено Раду Григор в одной из статей Кентского Университета<ref>[http://arxiv.org/pdf/1605.05274.pdf статье Кентского УниверситетаJava Generics are Turing-complete]</ref>. ===URISC=== '''URISC''' (от англ. ''Ultimate RISC'') — предельный случай процессора типа RISC (буквально: компьютер с предельно сокращённым набором инструкций), который умеет выполнять одну-единственную инструкцию. Обычно это «вычесть и пропустить следующую инструкцию, если вычитаемое было больше уменьшаемого» (англ. ''«reverse-subtract and skip if borrow»''). Аналогичная концепция, основанная именно на «вычесть и перейти, если результат не положительный» (англ. ''«subtract and branch unless positive»''), называется '''SUBLEQ'''. '''URISC''' также известен в современной литературе как '''OISC''' (англ. One Instruction Set Computer) и является полным по Тьюрингу.

Утилита M/o/Vfuscator превращает любую программу на языке C в огромную последовательность из инструкций <tex>\mathrm {mov}</tex><ref>[https://github.com/xoreaxeaxeax/movfuscator M/o/Vfuscator] превращает любую программу на языке C в огромную последовательность из инструкций mov</ref>.  {| cellpadding="0" style= align="left";|[[Файл:gcc_asm.png|400px|thumb|left|Результат работы GCC]]|[[Файл:mov_asm. png|400px|thumb|left|Результат работы M/o/Vfuscator]]|}

{| cellpadding="30" style= align="margin-left: auto; margin-right: auto";"|[[Файл:gcc_asm.png|400px|thumb|Результат работы GCC]]|[[Файл:mov_asm.png|400px|thumb|Результат работы M/o/Vfuscator]]|[[Файл:Demo_mov.gif|rightthumb|thumb500px|900pxleft|Простые числа с использованием одной инструкции]]

Нововведения новых версий 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], которое является Тьюринг-полным. ===MinecraftExcel=== Excel имеет свой скриптовый язык. Однако, для кодирования Машины Тьюринга в таблице Excel достаточно использование только формул<ref>[http://www.felienne.com/archives/2974 Excel Turing Machine]</ref>. ===Тьюринг-полнота в играх===

* Minecraft<ref>[https://www.youtube.com/watch?v===Little Big Planet===7sNge0Ywz-M|Demonstrating the CPU. Then coughing a lot. Sorry about that. I may be dying.]</ref>. Возможно, достижение Тьюринг-полноты в игре-песочнице с возможностью создания логических элементов было неизбежным, но сложность компьютеров, собираемых из блоков в данной игре, достойна внимания.

* Little Big Planet<ref>[https://www.youtube.com/watch?v===Super Mario World===13GOFa1C4e4| LittleBigLife — The Game of Life in LittleBigPlanet]</ref>. Некоторые элементы игры представляют из себя ничто иное, как небольшие клеточные автоматы, которые можно запрограммировать.

* Super Mario World<ref>[https://www.youtube.com/watch?v===Braid===hB6eY73sLV0 SNES Code Injection -- Flappy Bird in SMW]</ref>. Умелое обращение с багами игры позволяет сделать в ней буквально всё, что позволяет 2d-пространство Nintendo.

'''Тьюринговская трясина ''' — жаргонное общее название для языков программирования, которые ''Тьюринг-полны'', но обладают крайне примитивными синтаксисом и семантикой. Они неудобны для практического программирования (из-за трудности написания программ и низкой производительности), зато хорошо подходят для некоторых других задач (доказательство невычислимости некоторых функций, иллюстрация базовых принципов программирования и т. д.). Поэтому они интересны для информатики. Первыми представителями &laquo;трясины&raquo; были ''лямбда-исчисление'', ''комбинаторная логика'' и сама машина Тьюринга.  Многие эзотерические языки программирования также являются «трясинами Тьюринга»(напр. Brainfuck, Spoon, Malbolge, Whitespace).

==Тезис ЧёрчаПроблема остановки=={{Определение|definition= Проблема остановки {{---}} проблема определения факта остановки данной машины Тьюринга на данных входных данных (закончит выполнение или нет).}}{{Теорема|statement= Проблема остановки неразрешима|proof= Докажем от противного. Предположим существует такая полностью вычислимая функция <tex>halts(f)</tex>, которая возвращает <tex>true</tex>, если функция <tex>f</tex> остановится когда-либо, и <tex>false</tex>, если функция <tex>f</tex> никогда не остановится. Рассмотрим следующую функцию <tex>g</tex>  '''void''' g(): '''if''' halts(g): '''for'''(;;)<tex>halts(g)</tex> должна возвращать либо <tex>true</tex>, либо <tex>false</tex>.* Если <tex>halts(g)</tex> вернула <tex>true</tex>, то <tex>g</tex> никогда не остановится, получили противоречие* Если <tex>halts(g)</tex> вернула <tex>false</tex>, то <tex>g</tex> остановится, получили противоречие}} ==Теорема Геделя о неполноте==Чтобы доказать теорему, можно воспользоваться проблемой остановки машины Тьюринга.{{Теорема|statement= Любая непротиворечивая формальная система аксиом <tex>T</tex>, способная выражать утверждения о натуральных числах и доказывать простые арифметические факты, неполна {{---}} существуют утверждения о натуральных числах, которые она не может ни доказать, ни опровергнуть.|proof=# Предположим, что система <tex>T</tex> полна, т.е. доказывает или опровергает любое утверждение.# Сформулируем и запишем на языке арифметики утверждение <tex>O</tex> ="машина Тьюринга <tex>M</tex> точно остановится, если запустить ее с данными <tex>D</tex>".# Переберем все доказательства (<tex>P</tex> {{---}} истинно) и опровержения (<tex>\neg P</tex> {{---}} истинно) в системе <tex>T</tex>, чья длина совпадает с длиной <tex>O</tex>.# Так как система <tex>T</tex> полна, рано или поздно мы найдем опровержение или доказательство утверждения <tex>O</tex># Система <tex>T</tex> доказывает не только истинные факты (так как она только непротиворечива), т.е. доказываемое утверждение может быть ложным.# Тем не менее, мы фактически решили проблему остановки.}}

* [http://webbeza1e1.archivetuxen.orgde/webarticles/20131101122512/httpaccidentally_turing_complete.html Andreas Zwinkau — Accidentially Turing-complete] * [https://ubietylabru.netwikipedia.org/ubigraphwiki/content/Papers/pdf/CppTuring.pdf Todd L. Veldhuizen URISC Википедия — C++ Templates are Turing CompleteURISC]

* [http[Категория: Теория формальных языков]][[Категория: Теория вычислимости]][[Категория: Вычислительные формализмы]][[Категория://arxiv.org/pdf/1605.05274.pdf Radu Gregore — Java Generics are Turing CompleteМашина Тьюринга]]