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

G. S. Tseitin

Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part IV, Tome 20 (1971), pp. 243-262

Résumé

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.