Изменения
Нет описания правки
** если принадлежность <tex>x</tex> множеству <tex>B</tex> не установлена ранее, то далее считаем, что <tex>x \not\in B</tex>.
Но <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 B</tex>. Такое слово всегда найдется, так как на предыдущий шагах мы могли сделать не более, чем <tex>2^n-1</tex> запросов к оракулу, а всего слов длины n <tex>2^n</tex>.
Предположим, что <tex>M_i</tex> отработала менее, чем за время <tex>2^{n-1}</tex>, тогда
*если <tex>M_i</tex> допускает слово <tex>1^n</tex>, то в <tex>B</tex> нет слова <tex>1^n</tex>;
*если <tex>M_i</tex> отклоняет слово <tex>1^n</tex>, то в <tex>B</tex> содержится слово <tex>x</tex>, причем <tex>|x| = n</tex>.
Противоречие.
Следовательно, <tex>M_i</tex> не может решить язык <tex>U_B</tex> за время меньшее <tex>2^{n-1}</tex>.
}}
