A reduced form of normal algorithms and a linear speed-up theorem

G. S. Tseitin

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

Résumé

A special class of normal algorithms i s defined wlth the property that if the initial word contains no occurrences of letters from a specified “operating alphabet” then each intermediate word contains exactly one such occrurrence and all replacements occur around those occurrences. The main result is that for any normal algorithm $\mathfrak M$ an equivalent algorithm $\mathfrak N$ of that class can be constructed such that for any word $P$ $$ t_{\mathfrak N}(P)\leq C_1\cdot t_{\mathfrak M}(P)+C_2\cdot|P|+C_3 $$ provided that $\mathfrak M(P)$ is defined, $t_{\mathfrak M}$ and $t_{\mathfrak N}$ denoting the respective number-of-steps functions and $|P|$ the length of $P$. A corollary is proved where the constants $C_1$ and $C_2$ are replaced by arbitrarily small positive number.