The lower estimate of number of steps for reversing normal algorithms and other similar algorithms

A general theorem is proved which shows, in particular, that any normal algorithm reversing any wbrd over some alphabet uses no less than $Cn^2$ steps for “almost all” words, $n$ being the length of the word and $C$ a constant depending on the algorithm. As the technique of crossing sequences used for Turing machines cannot be applied here, a different approach is proposed. The initial word is divided into two parts, $P$ and $Q$ and for each intermediate word $R$ two functions are defined, one indicating the “quantity of information” about $Q$ contained in each beginning of $R$ and the other similarly for $P$ and all endings of $R$. These functions are defined in probabilistic terms; the number of steps is them estimated through the mathematical expectation of a certain quantity measuring the degree of “mutual propagation” of information about $P$ and $Q$. A similar approach but not using probabilities leads to a weaker estimate.