Изменения

| 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\Omega(n)</tex> дополнительной памяти. Будем поэтому Поэтому будем хранить только позицию <tex>i</tex> головкиМТ для <tex>\mathrm{B}</tex> на входной ленте (в двоичной записи это требует <tex>O(\log n)</tex> памяти), и на каждом шаге вычислять соответствующий <tex>i</tex>-ый бит с помощью функции <tex>f(x)</tex> при необходимости обращения к нему путём исполнения <tex>f(x)</tex>без записи результата целиком. Таким образом построим МТ для <tex>\mathrm{A}</tex>, удовлетворяющую определению.