Изменения

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

Разрешимые (рекурсивные) языки

58 байт убрано, 02:14, 10 января 2015
Нет описания правки
\end{cases}
</tex>
}}
{{Определение
Приведём доказательство от противного.
Пусть язык <tex>U</tex> разрешим, тогда существует программа  <tex> u </tex> : <tex> \forall \langle p, x \rangle \in U \Rightarrow u(\langle p, x \rangle) = \begin{cases}1</tex>, <tex> \forall \langle p, x \rangle \notin in U \Rightarrow u(\0, \ \langle p, x \rangle) = 0\notin U.\end{cases}</tex>.}}
Составим следующую программу:
Анонимный участник

Навигация