Talk:Bag

This article is DEFINITELY related to: Guy, Richard. Conway's prime producing machine. Mathematics Magazine, Vol. 56, No. 1 (1983), pages 26-33 03D10 Publication Type: Article MR: MR84j:10008 ---- Asher Holley (asher at infinitegmork dot com)

Argh! And here I had used every search I could think of to try and find the idea again. So with your information, not only did I find the formalism, but the language already has another name, Fractran. (At least the numeric part.) Sigh. --Ørjan 00:46, 22 Jun 2006 (UTC)

Markov bag-rewriting algorithms

This connection may be obvious, but I think it's worth explicit mention. Bag programs correspond to Markov bag-rewriting algorithms that are natural analogs of Markov string-rewriting algorithms, reformulating the latter to rewrite unordered strings rather than (ordered) strings. More specifically, a Bag program [B1/A1, ..., Bk/Ak] (where the Ai, Bi are bags) together with an initial state bag S, is effectively a list of rewrite rules [A1 -> B1, A2 -> B2, ..., Ak -> Bk] iteratively applied to S in just the manner expected of such a Markov analog: apply to S the first rule that's applicable, stopping when no rule is applicable. (A rule A -> B is applicable to S iff A occurs in S at least once; to apply the rule to S is to replace in S one instance of A by B; etc. The analog would be complete by allowing some rules to be "terminal", but FRACTRAN proves this is not necessary for Turing completeness.)
-- r.e.s. 18:14, 4 January 2010 (UTC)