Изменения

Рассмотрим последовательность машин Тьюринга <tex>M_i</tex>, имеющих доступ к оракулу языка <tex>B</tex>. Построение множество <tex>B</tex> разделим на счетное число шагов. Будем строить <tex>B</tex> так, чтобы на <tex>i</tex>-м шаге было выполнено: <tex>T(M_i, x) \ge 2^{n-1}</tex>. Очевидно, что это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P_B}</tex>. Начнем поэтапно строить множество <tex>B</tex>.

* <tex>i</tex>-й шаг. Будем считать шаги с 0-го по <tex>(i-1)</tex>-й сделаны. Тогда в <tex>B</tex> на данном этапе содержится — конечное число множество слов. Пусть самое длинное из них состоит из <tex>(n-1)</tex>-го символа. Запустим машину <tex>M_i</tex> на входе <tex>1^n</tex> на <tex>2^{n-1}</tex> шагов. Когда <tex>M_i</tex> требуется ответ оракула языка <tex>B</tex> о слове <tex>x</tex>, происходит следующеебудем определять принадлежность этого слова к <tex>B</tex>:** Если если принадлежность <tex>x</tex> множеству <tex>B</tex> была определена на предыдущем шаге, то она сохраняется.;** Если если принадлежность <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</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>. Противоречие.