141
правка
Изменения
→Теорема Райса-Шапиро: Ещё кусок доказательства леммы 2 внутри т. Р.-Ш.
где условие <tex>(1)</tex> следующее: через <tex>x</tex> шагов перечисления <tex>K</tex> число <tex>n</tex> не появилось.
Если <tex>n \notin K</tex>, то <tex>V(n, x) = g(x)</tex>.
Если <tex>n \in K</tex>, то <tex>V(n, x) = g(x)</tex> при <tex>x = 0\ldots t-1</tex> для какого-то <tex>t</tex>.
Запустим параллельно проверку, принадлежит ли <tex>n</tex> множеству <tex>K</tex> и проверку, принадлежит ли <tex>V(n, x)</tex> множетсву <tex>A</tex>.
<продолжение доказательства леммы>
