Изменения

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

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

2 байта добавлено, 10:54, 23 декабря 2011
Пример неразрешимого множества
|id=st1
|statement=
Универсальный язык неразрешимне разрешим.
|proof=
Приведем доказательство от противного. <br/>
Таким образом, из предположения о разрешимости универсального языка мы пришли к противоречию.
}}
 
== Литература ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
Анонимный участник

Навигация