313
правок
Изменения
→Альтернативное доказательство с использованием теоремы о рекурсии
== Свойства языков ==
Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> \mathrm {RE} </tex>.
{{Определение
|definition='''Свойством языков''' (англ. ''property of languages'') называется множество <tex> A \subset \mathrm {RE} </tex>.
}}
{{Определение
|definition=Рассмотрим множество перечислимых языков <tex>RE</tex>.*Свойством языков называется множество <tex>A \subset RE</tex>.*Свойство <tex>A</tex> называется '''тривиальным''' (англ. ''trivial''), если <tex>A = \varnothing </tex> или <tex>A = \mathrm {RE} </tex>.*Языком }}{{Определение|definition='''Язык свойства называется ''' (англ. ''language of property'') <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p | \mid L(p) \in A \rbrace </tex>.*Свойство <tex>A</tex> называется разрешимым (перечислимым), если <tex>L(A)</tex> разрешимо (перечислимо).
}}
'''Отметим''', что принадлежность программы <tex>p</tex> языку свойства <tex>A</tex> можно выразить двумя эквивалентными утверждениями:
:<tex>L(p) \in A</tex>
:<tex>p \in L(A)</tex>
Далее в конспекте будет употребляться <tex>p \in L(A)</tex>.
{{Определение
|definition=Свойство <tex> A </tex> называется '''разрешимым''' (англ. ''recursive''), если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].
}}
=== Примеры ===
'''Примеры свойств''':
# Язык должен содержать слово ''hello''.
# Язык должен содержать хотя бы одно простое число.
Псевдокод для разрешителя <tex>L(A)</tex>, где <tex>A = \mathrm {RE}: </tex>
<tex>p_A(p_X)</tex> <font color="green"> // <tex>p_X</tex> {{---}} полуразрешитель некоторого языка</font>
'''return''' ''true''
Псевдокод для программы в общем случае, то есть для проверки того, что язык удовлетворяет свойству :
<tex>p_A(p_X)</tex>
'''return''' <tex>p_X \in L(A)</tex>
Псевдокод полуразрешителя для языка свойства из первого примера:
<tex>p_A(p_X)</tex> <font color="green"> // <tex>X</tex> {{---}} перечислимый язык в общем случае, поэтому <tex>p_A</tex> {{---}} полуразрешитель (по [[Теорема Райса-Шапиро |теореме Райса-Шапиро]])</font>
'''return''' <tex>p_X</tex>('hello')
== Теорема Успенского-Райса ==
{{Теорема
|statement=
'''Теперь рассмотрим случай, когда <tex>p_\infty \in L(\overline{A})</tex>.''' Так как <tex>\overline{A}</tex> {{---}} нетривиально (как дополнение к нетривиальному множеству), то по первой части доказательства оно неразрешимо. Следовательно, <br/tex> A</tex> также неразрешимо.US(\langle i===Альтернативное доказательство с использованием теоремы о рекурсии===По [[Теорема о рекурсии | теореме о рекурсии]], программа может знать свой исходный код. Значит, x в неё можно написать функцию <tex> \rangle mathrm{getSrc() = p_A(g_} </tex>, которая вернёт строку {{i,x---}}) = \beginисходный код программы. <tex> A </tex> {{cases---}} разрешимое семейство языков. <tex> L_A </tex> {{---}} множество программ, удовлетворяющих св-ву <tex> A </tex>. Теперь допустим, что язык <tex> L_A </tex> разрешим. Тогда напишем такую программу: <code> p_A<tex>propA(p_Xcode) & U(i{:}</tex> // программа, x) = 1 \\разрешающее свойство языка <tex> A </tex> p_A(p_\varnothing ) & U<tex>f(i, x) \neq 1 \\{:}</tex> // такая программа <tex> f </tex>, что <tex>f \endin A </tex>; существует потому что <tex> A </tex> {cases{---} = \begin{cases}нетривиальное свойство 1 & U<tex>g(i, x) = 1 \{:}</tex> // такая программа <tex> g </tex>, что <tex>g \notin A </tex>; существует потому что <tex> A </tex> {{---}} нетривиальное свойство 0 & U<tex>p(i, x) \neq 1 \\{:}</tex> '''if''' <tex>propA(\endmathrm{casesgetSrc()})</tex> '''return''' <tex>g(x)</tex> '''else''' '''return''' <tex>f(x)</tex></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>. Опять получили противоречие. == См. также ==* [[Теорема о рекурсии]]* [[Теорема Райса- программаШапиро]] == Источники информации ==* [https://en.wikipedia.org/wiki/Rice%27s_theorem Wikipedia — Rice's theorem]* Rice, разрешающая универсальное множествоH. G. {{---}} Classes of Recursively Enumerable Sets and Their Decision Problems." {{---}} Trans. Amer. Math. ПротиворечиеSoc. 74, 358-366, 1953.* Хопкрофт Д., Мотванн Р., Ульманн Д. {{---}}Введение в теорию автоматов, языков и вычислений {{---}}стр. 397.[[Категория: Теория формальных языков]][[Категория: Теория вычислимости]][[Категория: Разрешимые и перечислимые языки]]