Материал из Викиконспекты
|
|
| (не показаны 2 промежуточные версии 2 участников) |
| Строка 1: |
Строка 1: |
| − | {{Утверждение
| |
| − | |id=proposalU.
| |
| − | |statement=[[Разрешимые (рекурсивные) языки#Пример неразрешимого множества | Универсальный язык]] неразрешим
| |
| − | |proof=
| |
| − | Допустим, что он разрешим. Тогда напишем такую программу:
| |
| − | <code>
| |
| − | p(x):
| |
| − | '''if''' u(getSrc(), x)
| |
| − | '''while''' ''true''
| |
| − | '''else'''
| |
| − | '''return''' 1
| |
| − | </code>
| |
| | | | |
| − | Если <tex> u(p, x) = 1 </tex>, тогда программа <tex> p </tex> на входе <tex> x </tex> должна вернуть <tex> 1 </tex>, но по условию <tex> if </tex> она зависает, а следовательно, не принадлежит универсальному языку.
| |
| − |
| |
| − | Если же <tex> u(p, x) \neq 1 </tex>, то мы пойдём во вторую ветку условного оператора и вернём <tex> 1 </tex>, значит, пара <tex>
| |
| − | \langle p, x \rangle </tex> принадлежит универсальному языку, но <tex> u(p, x) \neq 1 </tex>, значит, пара не принадлежит. Опять получили противоречие.
| |
| − | }}
| |
Текущая версия на 19:32, 4 сентября 2022
