Изменения

| proof = По определению <tex>\mathrm{\widetilde{L}}</tex>-сводимости <tex>\exists f \in \widetilde{L} : x \in \mathrm{A} \Leftrightarrow f(x) \in \mathrm{B}.Просто выполнить <tex>f(x)</tex> и передать результат в качестве ввода МТ для <tex>\mathrm{B}</tex> не может хранить вводнельзя, так как работает на для этого требуется <tex> O(\log n) </tex> дополнительной памяти. Будем поэтому хранить только позицию головки, и на каждом шаге вычислять соответствующий бит с помощью функции <tex>f</tex>. Таким образом построим МТ для <tex>\mathrm{A}</tex>, удовлетворяющую определению.