313
правок
Изменения
Новая страница: «<tex> A </tex> {{---}} разрешимое семейство языков. <tex> L_A </tex> {{---}} множество программ, удовлетворя...»
<tex> A </tex> {{---}} разрешимое семейство языков.
<tex> L_A </tex> {{---}} множество программ, удовлетворяющих св-ву <tex> A </tex>.
Теперь допустим, что язык <tex> L_A </tex> разрешим. Тогда напишем такую программу:
<code>
propA(code):
// программа, разрешающее свойство языка <tex> A </tex>
f(x):
// такая программа <tex> f </tex>, что <tex>f \in A </tex>; существует потому что <tex> A </tex> {{---}} нетривиальное свойство
g(x):
// такая программа <tex> g </tex>, что <tex>g \notin A </tex>; существует потому что <tex> A </tex> {{---}} нетривиальное свойство
p(x):
'''if''' propA(getSrc())
'''return''' g(x)
'''else'''
'''return''' f(x)
</code>
Если <tex> p </tex> не удовлетворяет свойству <tex> A </tex>, тогда будет выполняться всегда вторая ветка, и <tex> L(p) = L(f) </tex>. Но язык программы <tex> f </tex> принадлежит <tex> A </tex>. Получили противоречие.
Если <tex> p </tex> удовлетворяет свойству <tex> A </tex>, то <tex> L(p) = L(g) </tex>, а <tex> g \notin A </tex>. Опять получили противоречие.
<tex> L_A </tex> {{---}} множество программ, удовлетворяющих св-ву <tex> A </tex>.
Теперь допустим, что язык <tex> L_A </tex> разрешим. Тогда напишем такую программу:
<code>
propA(code):
// программа, разрешающее свойство языка <tex> A </tex>
f(x):
// такая программа <tex> f </tex>, что <tex>f \in A </tex>; существует потому что <tex> A </tex> {{---}} нетривиальное свойство
g(x):
// такая программа <tex> g </tex>, что <tex>g \notin A </tex>; существует потому что <tex> A </tex> {{---}} нетривиальное свойство
p(x):
'''if''' propA(getSrc())
'''return''' g(x)
'''else'''
'''return''' f(x)
</code>
Если <tex> p </tex> не удовлетворяет свойству <tex> A </tex>, тогда будет выполняться всегда вторая ветка, и <tex> L(p) = L(f) </tex>. Но язык программы <tex> f </tex> принадлежит <tex> A </tex>. Получили противоречие.
Если <tex> p </tex> удовлетворяет свойству <tex> A </tex>, то <tex> L(p) = L(g) </tex>, а <tex> g \notin A </tex>. Опять получили противоречие.
