Изменения

 Но <tex>M_i</tex> могла остановится раньше, чем за <tex>2^{n-1}</tex> шагов и вернуть какое-либо значение. Но мы строим Так как <tex>B</tex> строится с условием <tex>T(M_i, x) \ge 2^{n-1}</tex>, поэтому то решение машины о принадлежности слова должно быть неверным:* если <tex>M_i</tex> приняла слово, то будем считать, что выбросим исключим из <tex>B</tex> все слова вида <tex>\{0,1\}^n</tex>;* Если <tex>M_i</tex> отклонила слово, то выберем слово <tex>x</tex> длины <tex>n</tex>, принадлежность которого <tex>B</tex> еще не определено. Тогда Добавим <tex>x \in </tex> в <tex>B</tex>. Такое слово всегда найдется, так как на предыдущий шагах мы могли сделать не более, чем <tex>2^n-1</tex> запросов к оракулу(то есть добавить в <tex>B</tex> не более <tex>2^n-1</tex> слов длины <tex>n</tex>), а всего слов длины n <tex>2^n</tex>.

Рассмотрим построенное по описанному выше алгоритму множество <tex>B</tex>. Предположим, что <tex>M_i</tex> отработала менее, чем за время <tex>2^{n-1}</tex>, тогда на слове <tex>1^n</tex>, где <tex>n</tex> определено для каждого <tex>i</tex> в алгоритме, описанном выше. Тогда