Изменения
→Некоторые другие ЯП
|-
|style="background-color:#FFF;padding:2px 8px"| JavaScript
|style="background-color:#FFF;padding:2px 8px"| 19651995
|style="background-color:#FFF;padding:2px 8px"| Объектно-ориентированный
|style="background-color:#FFF;padding:2px 8px"| Высокий
Многие эзотерические языки программирования также являются «трясинами Тьюринга» (напр. 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> доказывает не только истинные факты (так как она только непротиворечива), т.е. доказываемое утверждение может быть ложным.# Тем не менее, мы фактически решили проблему остановки.}}
==См. также==
