Markov Algorithms

Origin. Andrei Andreevich Markov — the younger, son of the probabilist — announced normal algorithms in "Teoriya algorifmov" (Trudy Matematicheskogo Instituta imeni V. A. Steklova 38, 1951, pp. 176–189; English translation "The theory of algorithms", American Mathematical Society Translations, series 2, volume 15, 1960, pp. 1–14) and developed them in the monograph Teoriya algorifmov (Trudy Mat. Inst. Steklova 42, 1954; English translation Theory of Algorithms, Israel Program for Scientific Translations, Jerusalem 1961, reissued 1962; second edition with Nikolai M. Nagorny, Nauka 1984, English edition Kluwer 1988). The unsolvability results came first: two 1947 Doklady Akademii Nauk notes, "Nevozmozhnost' nekotorykh algorifmov v teorii assotsiativnykh sistem" (On the impossibility of certain algorithms in the theory of associative systems), settled the word problem for finitely presented semigroups — Thue's problem — in the same year as Post and independently of him, and the 1951 note "Nevozmozhnost' algorifmov raspoznavaniya nekotorykh svoistv assotsiativnykh sistem" extended the impossibility to the algorithmic recognition of properties of associative systems.

Models. A normal algorithm computes where a canonical system generates. Post's productions carry word variables and apply wherever a derivation chooses, so the system's content is a set — the generated language; Markov's substitution formulas are literal words in a fixed order, the discipline selects one formula and one occurrence at every step, and the content is a run — a partial function on words. That determinism is what the Soviet constructive school required of it, since Markov founded the school on two notions: a constructive object is a word over an alphabet, and a constructive procedure is a normal algorithm. Constructive mathematics in this tradition is the study of normal algorithms over constructive objects — the mathematics the Markov's Principle entry records as RUSS — and the normalization principle, that every verbal algorithm is equivalent to a normal algorithm over an extension of its alphabet, is the school's form of the Church–Turing thesis, stated over words rather than numbers.

Formalism.

Alphabet: a finite alphabet A; words over A, among them the empty word Λ.

Scheme: a finite ordered list of substitution formulas, α → β (simple) α →· β (final) with α and β fixed words, possibly empty. No variables: matching is literal.

Step: scan the scheme in order; the first formula whose left side occurs in the current word applies, and β replaces the leftmost occurrence of α.

Halting: a final formula halts the run after applying; a word containing no left side halts it; otherwise the scan restarts from the top of the list.

Determinism: one formula, one occurrence, at every step. A word fixes its entire run; the algorithm 𝔄 is the partial word function P ↦ 𝔄(P).

Over and in: an algorithm over A may use working letters beyond A; one whose formulas stay inside A is an algorithm in A.

Combination: composition, branching and iteration of normal algorithms are again normal — the monograph's combination theorems — and a universal normal algorithm exists.

Normalization principle: every verbal algorithm is equivalent to a normal algorithm over an extension of its alphabet. A thesis, exactly as Church's is.

Symbols.

Metatheory. V. K. Detlovs, "Ekvivalentnost' normal'nykh algorifmov i rekursivnykh funkcij" (The equivalence of normal algorithms and recursive functions, 1958), proved that normal algorithms compute exactly the partial recursive functions, so the formalism matches Turing machines and the normalization principle stands or falls with Church's thesis; the applicability problem — whether a given normal algorithm halts on a given word — is unsolvable, by the monograph's theorems on the non-existence of algorithms. The 1947 Doklady notes construct a finitely presented semigroup whose word problem no algorithm decides, the result Post reached independently in the same year (the Post Canonical Systems entry records the pair), and the 1951 note proves that certain properties of finitely presented associative systems admit no recognition algorithm. On the school's side the signature admission is Markov's principle, his principle of constructive selection: if a normal algorithm's failure to halt is refuted, it halts — double-negation elimination for a search, rejected by Brouwer and defended by Markov. The Markov's Principle entry carries its exact strength and the analysis built on it; Ceitin's continuity theorem is, in the school's reading, a theorem about normal algorithms.

Applies to. The Soviet constructive school, whose analysis is the theory of normal algorithms over words coding rationals and sequences — Kushner's lectures are the systematic record. Undecidability reductions for word problems in algebra, alongside Post's systems. String processing: Valentin Turchin's REFAL, a pattern-matching rewriting language of the late 1960s, is the practiced descendant. Computability courses, as the standard string-rewriting member of the equivalent models.

Limitations. The determinism and the leftmost-first discipline make the formalism sharp as a definition and awkward as a programming model: every run is a unique word sequence, and every formula competes with every other at every step, so control must be arranged through rule order and working letters. The formulas are variable-free — no terms, no templates: Post's productions add word variables, and Rewriting Logic adds terms modulo equations, where a normal algorithm rewrites one flat word. Everything — numbers, pairs, machines — must be coded as words. The normalization principle is a thesis, so the formalism's adequacy is an empirical claim, as Church's is. A normal algorithm defines a set only through a semicharacteristic function; the generative reading that is native to canonical systems has to be simulated.

© 2026 Lingenic LLC