141
правка
Изменения
Словесные пояснения для псевдокода в леммах
Свойство <tex>A_{\gamma}</tex> перечислимо для любого образца <tex>\gamma</tex>.
|proof =
Построим полуразрешитель <tex>A_{\gamma}</tex>:. Он будет возвращать 1 для программы <tex>p</tex>, если <tex>p(x_i)</tex> завершится с результатом <tex>y_i</tex> для всех элементов образца <tex>\langle x_i, y_i\rangle</tex>. В противном случае полуразрешитель будет зависать.
<tex>q(p):</tex>
for <tex>\langle x_i, y_i\rangle \in \gamma</tex>
Тогда <tex>A_{\Gamma}</tex> является перечислимым.
|proof =
Построим полуразрешитель <tex>A_{\Gamma}</tex>:. Он будет брать <tex>k</tex> первых образцов из <tex>\Gamma</tex> и для каждого их них проверять принадлежность программы <tex>p</tex> свойству этого образца с ограничением по времени <tex>k</tex> для всех <tex>k</tex> от 1 до бесконечности. При обнаружении <tex>p</tex> полуразрешитель завершится и вернёт 1. В противном случае он останется зависшим.
<tex>q(p):</tex>
for <tex>k = 1\ldots +\infty</tex>
