Изменения

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

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

8 байт добавлено, 17:13, 2 января 2017
Альтернативное доказательство с использованием теоремы о рекурсии
</code>
Если <tex> u(p, x) = 1 </tex>, тогда программа <tex> p </tex> на входе <tex> x </tex> должна вернуть <tex> 1 </tex>, но по условию <tex> \mathrm{if } </tex> она зависает, а следовательно, не принадлежит универсальному языку.
Если же <tex> u(p, x) \neq 1 </tex>, то мы пойдём во вторую ветку условного оператора и вернём <tex> 1 </tex>, значит, пара <tex>
313
правок

Навигация