Редактирование: Свойства перечислимых языков. Теорема Успенского-Райса

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 59: Строка 59:
 
\end{cases} </tex>
 
\end{cases} </tex>
  
 +
<code>
 
  '''function''' <tex>V_n</tex>(x):
 
  '''function''' <tex>V_n</tex>(x):
 
   '''if''' <tex>p_X</tex>(n) == 1
 
   '''if''' <tex>p_X</tex>(n) == 1
 
     '''return''' <tex>p_S</tex>(x)
 
     '''return''' <tex>p_S</tex>(x)
 
   '''while''' ''true''
 
   '''while''' ''true''
 +
</code>
  
 
Получили, что если <tex>n \in X</tex>, то <tex>V_n \in L(\overline A)</tex>, а если <tex>n \notin X</tex>, то <tex>V_n \in L(A)</tex>. Таким образом, <tex>n \in X \iff V_n \in L(\overline A)</tex>.  
 
Получили, что если <tex>n \in X</tex>, то <tex>V_n \in L(\overline A)</tex>, а если <tex>n \notin X</tex>, то <tex>V_n \in L(A)</tex>. Таким образом, <tex>n \in X \iff V_n \in L(\overline A)</tex>.  
Строка 80: Строка 82:
 
Теперь допустим, что язык <tex> L_A </tex> разрешим. Тогда напишем такую программу:
 
Теперь допустим, что язык <tex> L_A </tex> разрешим. Тогда напишем такую программу:
  
 +
<code>
 
   <tex>propA(code){:}</tex>
 
   <tex>propA(code){:}</tex>
 
     // программа, разрешающее свойство языка <tex> A </tex>
 
     // программа, разрешающее свойство языка <tex> A </tex>
Строка 91: Строка 94:
 
     '''else'''
 
     '''else'''
 
         '''return''' <tex>f(x)</tex>
 
         '''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(f) </tex>. Но язык программы <tex> f </tex> принадлежит <tex> A </tex>. Получили противоречие.

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

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

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

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