Изменения

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

Перечислимые языки

6 байт добавлено, 21:28, 23 ноября 2016
м
дефисы -> тире
Язык простых чисел коперечислим.
|proof=
Пусть <tex>L</tex> {{- --}} язык простых чисел, тогда <tex>\overline L</tex> {{---}} язык, состоящий из составных чисел и единицы. Покажем, что <tex>\overline L</tex> полуразрешим, а, следовательно, и перечислим согласно теореме, приведённой выше.
Построим простой полуразрешитель:
129
правок

Навигация