271
правка
Изменения
Нет описания правки
{{Определение
|definition=Язык <tex>L</tex> называется '''разрешимым''' ('''рекурсивным'''), если существует такая программа <tex> p </tex>, что <tex> \forall w \in L: p(w) = 1</tex>, а для <tex> \forall w \notin L: p(w) = 0</tex>.
}}
Доказательство от противного. <br/>
Пусть язык <tex> U </tex> разрешим. <br/>
Тогда существует такая программа <tex> u </tex>, что <tex> \forall \langle p, x \rangle \in U: u(\langle p, x \rangle) = 1</tex>, а для <tex> \forall \langle p, x \rangle \notin U: u(\langle p, x \rangle) = 0</tex>. <br/>
Составим следующую программу:
