Теория и реализация языков программирования




Класс рекурсивных множеств - часть 2


Наконец, если Tmi не останавливается, то Tm не останавливается.
  • Таким образом L2 рекурсивно перечислимо, поскольку L2 - это множество допускаемое Tm. Но дополнение к
    L_2(\sim L_2)
    не может быть рекурсивно перечислимо, поскольку если Tj - машина Тьюринга, допускающая
    \sim L_2, то x_j \in \sim L_2

    тогда и только тогда, когда xj не допускается Tmj . Это противоречит утверждению, что

    \sim L_2
    - это язык, допускаемый Tj .
  • Теорема 2.3. Существует рекурсивно перечислимое множество, не являющееся рекурсивным.

    Доказательство. Доказательство. По лемме 2.2 L2 - рекурсивно перечислимое множество, дополнение которого не рекурсивно перечислимо. Если бы L2 было рекурсивно, по лемме

    1 \sim L_2
    было бы рекурсивно, и следовательно рекурсивно перечислимо, что противоречит второй половине леммы 2.2.




    Содержание  Назад  Вперед