129
правок
Изменения
пример коперечисл. языка + отформатирован псевдокод
: Пусть <tex>L</tex> {{---}} перечислимый язык. Тогда для него существует программа <tex>g</tex>, которая по номеру <tex>i</tex> выводит слово из <tex>L</tex>. Значит, для всех <tex>x</tex> из <tex>L</tex> путем перебора значений функции <tex>g</tex> мы можем найти такое <tex>i</tex>, что <tex> g(i) = x</tex>. Следовательно, существует программа <tex>p</tex>, такая, что <tex>\forall x: x \in L \Leftrightarrow p(x)=1</tex>. Тогда <tex>L</tex> является полуразрешимым языком.
<tex> \Longleftarrow </tex>:
</code>
:Пусть <tex>L</tex> {{---}} полуразрешимый язык. Тогда для него существует программа <tex>p</tex>, результат которой равен <tex>1</tex> для любого слова из <tex>L</tex>. Чтобы программа <tex>p</tex> не зависала на словах, которые не принадлежат <tex>L</tex>, будем запускать ее с тайм-лимитом. Для поиска <tex>i</tex>-го слова из языка <tex>L</tex> будем перебирать <tex>k</tex> {{---}} тайм-лимит с которым будем запускать программу <tex>p</tex>. Таким образом существует программа <tex>g_0</tex>, которая выводит <tex>i</tex> слово языка <tex>L</tex> с повторениями. Для того, чтобы выводить слова без повторений, заведем множество <tex>U</tex>, в котором будем хранить уже выведенные слова. Программа <tex>g</tex> доказывает, что <tex>L</tex> является перечислимым языком.
: <code>
'''function''' <tex>{\bf g_0}</tex>(i: '''int'''):'''int''' <tex>cnt = 0</tex> '''for''' k = 1 to <tex> k = 1 ~ .. ~ \infty</tex> '''for''' x <tex> x \in \{x_1, x_2, .., x_k\}</tex> '''if''' <tex> p|_k</tex>(x) == 1</tex> <tex>cnt</tex>++ '''if''' <tex> cnt == i</tex> '''return''' <tex> x</tex>
</code>
<code>
'''function''' <tex>{\bf g}</tex>(i: '''int'''):'''int'''
<tex>U = \emptyset</tex>
'''for''' j = 1 to <tex> j = 1 ~ .. ~ \infty</tex> x = <tex>x = {\bf g_0}(j)</tex>(j) '''if''' x <tex> x \notin U</tex>U <tex>cnt</tex>++ '''if''' <tex> cnt == i</tex> '''return''' <tex> x</tex> <tex>U.insert(x)</tex>
</code>
}}
Приведём программу, перечисляющую язык натуральных чисел:
<code>
'''return''' i
</code>
Приведём программу, перечисляющую язык чётных неотрицательных чисел:
<code>
'''return''' i * 2
</code>
}}
{{Утверждение
|id=st2
|statement=
Язык простых чисел коперечислим.
|proof=
Пусть <tex>L</tex> - язык простых чисел, тогда <tex>\overline L</tex> - язык, состоящий из составных чисел и единицы. Покажем, что <tex>\overline L</tex> полуразрешим, а, следовательно, и перечислим согласно теореме, приведённой выше.
Построим простой полуразрешитель:
<code>
'''function''' p(n: '''int'''): '''int'''
'''for''' i = 2 to <tex>\sqrt{n}</tex>
'''if''' n mod i == 0
'''return''' 0
'''return''' 1
</code>
}}
== Примеры неперечислимых языков ==
