Изменения

Если <tex>w \in L</tex>, то существует путь из стартовой конфигурации в финишную, причём длины не более , чем <tex>2^{O(p(n))}</tex>, а значит формула <tex>\phi</tex> верна.

Если формула <tex>f(M, w)</tex> оказалась верна, то существует путь из стартовой конфигурации в финишную не более , чем <tex>2^{O(p(n))}</tex>. Значит, ДМТ <tex>M</tex> допускает слово <tex>w</tex>. Тогда <tex>w \in L</tex>.