если Tmi не останавливается, то
Наконец, если Tmi не останавливается, то Tm не останавливается.
Таким образом L2 рекурсивно перечислимо, поскольку L2 - это множество допускаемое Tm. Но дополнение к не может быть рекурсивно перечислимо, поскольку если Tj - машина Тьюринга, допускающая
тогда и только тогда, когда xj не допускается Tmj . Это противоречит утверждению, что - это язык, допускаемый Tj .
Теорема 2.3. Существует рекурсивно перечислимое множество, не являющееся рекурсивным.
Доказательство. Доказательство. По лемме 2.2 L2 - рекурсивно перечислимое множество, дополнение которого не рекурсивно перечислимо. Если бы L2 было рекурсивно, по лемме
было бы рекурсивно, и следовательно рекурсивно перечислимо, что противоречит второй половине леммы 2.2.
Содержание Назад Вперед
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий