Редактирование: Тьюринг-полнота

Перейти к: навигация, поиск

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 141: Строка 141:
 
|-
 
|-
 
|style="background-color:#FFF;padding:2px 8px"| JavaScript
 
|style="background-color:#FFF;padding:2px 8px"| JavaScript
|style="background-color:#FFF;padding:2px 8px"| 1995
+
|style="background-color:#FFF;padding:2px 8px"| 1965
 
|style="background-color:#FFF;padding:2px 8px"| Объектно-ориентированный
 
|style="background-color:#FFF;padding:2px 8px"| Объектно-ориентированный
 
|style="background-color:#FFF;padding:2px 8px"| Высокий
 
|style="background-color:#FFF;padding:2px 8px"| Высокий
Строка 232: Строка 232:
 
Многие эзотерические языки программирования также являются «трясинами Тьюринга» (напр. Brainfuck, Spoon, Malbolge, Whitespace).
 
Многие эзотерические языки программирования также являются «трясинами Тьюринга» (напр. 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> доказывает не только истинные факты (так как она только непротиворечива), т.е. доказываемое утверждение может быть ложным.
 
# Тем не менее, мы фактически решили проблему остановки.
 
}}
 
  
 
==См. также==
 
==См. также==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: