33
правки
Изменения
м
→Построение m_{2}
====Построение <tex>m_{2}</tex>====
Машина <tex>m_{2}</tex> будет работать таким образом:
запустим <tex>N_{strweak}(p(|x|),m_{1})</tex> раз машину <tex>m_{1}</tex>, запоминая результат каждого запуска.
Вернем <tex>1</tex>, если больше половины запусков вернули <tex>1</tex>. Иначе вернем <tex>0</tex>.
Если <tex>N_{weak}</tex> таково, что <tex>P(m_{2}(x) = [x \in L]) > 2/3) \wedge N_{weak} \in poly(|x|)</tex>, то искомая машина построена.
