Изменения
→Доказательство
Сделаем машину <tex>m_2</tex>, которая будет запускать <tex>m_1</tex> на <tex>2*p(|x|)</tex> шагов, если <tex>m_1</tex> не завершила свою работу, то <tex>m_2</tex> выдаст 'не знаю', в противном случаи вернет результат работы <tex>m_1</tex>.
Пусть <tex>p(m_1(x) = ?) \ge \frac{1}{2}</tex>, тогда <tex>E(T(m_1(x))) \ge p(|x|)</tex>, — противоречие.
Значит, <tex>p(m_1(x) = ?) \le \frac{1}{2}</tex>, следовательно <tex>L \in ZPP^{'}</tex>.
