129
правок
Изменения
м
Нет описания правки
Язык нечётных неотрицательных чисел коперечислим.
|proof=
<tex>\overline L</tex> {{- --}} язык чётных неотрицательных чисел. Так как язык чётных неотрицательных чисел перечислим, то и язык нечётных неотрицательных чисел тоже перечислим.
}}
Язык простых чисел коперечислим.
|proof=
Пусть <tex>L</tex> - язык простых чисел, тогда <tex>\overline L</tex> {{- --}} язык, состоящий из составных чисел и единицы. Покажем, что <tex>\overline L</tex> полуразрешим, а, следовательно, и перечислим согласно теореме, приведённой выше.
Построим простой полуразрешитель:
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Разрешимые и перечислимые языки]]
