Talk:1.1

How is 1.1 "essentially equivalent" to Markov algorithms?

The 2nd paragraph says that Knuth says in AOCP that "the language is essentially equivalent to the one given in the book A. A. Markov, The Theory of Algorithms", where "the one given" links to the Markov algorithm article. Yet, 1.1 (as this article describes it) has many differences from the language of Markov algorithms (as that article describes that language). For instance, in 1.1 each state names a "next state" explicitly, while a MA has a set of rewriting rules, and on each step one applicable rule is picked.

I suspect either that Knuth is referring to a language in that book by Markov that is not the language of Markov algorithms as we know it; or that Knuth was using "essentially equivalent" in a wider sense than one might expect here, but that the provided context is missing. --Chris Pressey (talk) 12:01, 11 January 2024 (UTC)