Изменения
Нет описания правки
*если <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>.
}}
