403
правки
Изменения
м
Нет описания правки
Пронумеруем все полиномиальные программы, получим последовательность <tex>M_i</tex>. Множество <tex>B</tex> будем строить итеративно, на очередной итерации номер <tex>i</tex> делая так, что программа <tex>M_i</tex> не распознает множество <tex>U_B</tex>.
В начале каждой итерации определимся с тем, с какой длиной слова <tex>nn_i</tex> мы будем работать. Для <tex>nn_i</tex> должны быть выполнены три условия:* <tex>2^{n_i } > T(M_i, (1)^{n_i})</tex> (это ограничение может быть достигнуто, так как мы исследуем только полиномиальные программы)* <tex>n_i > n_{i-1}</tex>, где <tex>n_j</tex> (слово должно быть длиннее, чем слово, с которым мы работали на предыдущем шаге)
* <tex>n_i > \max\limits_{s \in B} |s|</tex> (это ограничение может быть достигнуто, так как в множестве <tex>B</tex> всегда конечное число элементов)
