Изменения
→Некоторые другие ЯП
|-
|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>".# Переберем все доказательства (доказанной Аланом Тьюрингом в 1936<tex>P</tex> {{---}} истинно). и опровержения (<tex>\neg P</tex> {{Теорема---}} истинно) в системе <tex>T</tex>, чья длина совпадает с длиной <tex>O</tex>.|statement= Для данной машины Тьюринга и входных данных для нее невозможно определить# Так как система <tex>T</tex> полна, остановиться ли рано или поздно мы найдем опровержение или доказательство утверждения <tex>O</tex># Система <tex>T</tex> доказывает не только истинные факты (так как она когда-либо (запущенная на этих данныхтолько непротиворечива) или нет, т.е. доказываемое утверждение может быть ложным.}}# Тем не менее, мы фактически решили проблему остановки.
}}
