Talk:Tag system

Example of cyclic tag system simulation

The cyclic tag system does not properly emulate the halt. It treats H just like any other symbol. It might be better to change the H to a neutral letter like c.

GuenterRote (talk) 07:36, 9 August 2023 (UTC)

Deletion number

Current version of the article does not explicitly state what is the role of m number. Only through the examples it is possible to guess its role. — Preceding unsigned comment added by 89.69.161.56 (talk) 13:18, 26 February 2012 (UTC)

Merging "Post machine" page into this one

Wikipedia also has an article on Post machines, which seem virtually identical to Tag systems, except for the way they are described. It would probably be a good idea to merge/link these two articles somehow. --Chris Pressey 17:20, 16 July 2005 (UTC)

I finally got around to incorporating a brief abstract machine description into Tag system, and have now redirected Post machine to this article.--r.e.s. (Talk) 21:38, 28 December 2005 (UTC)

Empty word

Hi, In the traditionnal tag system definition, can we include the empty word in the alphabet, like in automatons ? I mean, for letter 'A', P(A)=(empty), so that nothing is added at the end when 'A' is read.

King Mike 23:07, 22 November 2005 (UTC)

Yes, the empty word is a valid production.

--r.e.s. (Talk) 11:17, 26 December 2005 (UTC)

Rewording to better integrate cyclic tag systems

I hope JohnnyNyquist will not be too annoyed by my editing -- it seemed a good idea to make the description of cyclic tag systems use more of Rogozhin's terminology for tag systems. Also, although I tried to make the emulation section as brief as I could, it still seems a bit bulky -- but the example seems worth the space, imo.

--r.e.s. (Talk) 11:17, 26 December 2005 (UTC)

Rename?

Perhaps this page should be renamed "Post tag system"? Cosma Shalizi's review of NKS claims that "Post tag system" is the normal term for such things, but Wolfram omits "Post" in his book. I note that he also systematically omits most names of other people in the work he describes, presumably in order to claim credit for things he didn't invent. Perhaps we should not encourage him by accepting his terminology? Or was it often used by other people before him? Kragen Sitaker 21:27, 1 December 2006 (UTC)

Well before NKS, the simple term tag system was used by Minsky, Rogozhin, Wang, and other published authors in this field (all of whom of course credit Post as the inventor). Although it would certainly be correct to say Post tag system in the title, I don't think it would be an improvement, since there seems to be no need for disambiguating against some other meaning of the simpler term. (Compare, for example, lambda calculus versus Church lambda calculus.) --r.e.s. 05:44, 2 December 2006 (UTC)

Minsky 1967 indexes this notion as "tag system". Also, he says that:

"While agraduate student at Princeton in 1921, Post [1965] studied a class of appraently simple but cursiously frustrating problems..." (p. 267)

"Post [1965]" is to the following reference:

Post, Emil L. (1965), "Absolutely unsolvable problems and relatively undecidable propostiions -- account of an anticipation," Martin Davis, The Undecidable (m.s. unpublished, 1941).

I have this, will research. Bill Wvbailey 17:23, 7 October 2007 (UTC)

Weighted, Viral, Population, Tagging, Mechanisms

Viral tagging ftw!

I would like to propose a new spin on the old TAG SYSTEM. I call it VIRAL TAGGING. The basics of it are on my website which is redonkulicity.com/theory.html

I don't know how to use wikipedia to add articles, but would LOVE anyone to create a stub linked to the TAG SYSTEM, and VIRAL kinds of categories, or even understand what I'm saying and put that on the page.

The most specific and useful type of VIRAL TAGGING would be WEIGHTED ITERATIVE VIRAL TAGGING. And the coolest thing I could think of at the moment would be a webcrawler designed as a WIVT machine. —The preceding unsigned comment was added by Wubitog (talk • contribs) 16:21, 30 January 2007 (UTC).

Intractability? proof of impossibility or undecidability?

Does anyone out there know the status of the problem (see the annotation of the Minsky 1967 reference) w.r.t. undedicability and intractability? This fact should be prominent in the article. . My only reference to the "tag" problem is Minsky 1967, i.e. pretty ancient.

I think you're referring to this ad hoc test-case from Post 1943 (which is somewhat misstated by Minsky): Given the 3-tag system with production rules (0 -> 00, 1 -> 1101) on alphabet {0,1}, determine whether iteration of the tag operation eventually terminates in an empty string when started with an arbitrary initial word. (Where, in keeping with Post, the tag operation is as I paraphrase it in the Historical note section of the article, not as Minsky misstates it.) AFAIK, it's still an open question whether this is an unsolvable halting problem, in contrast to certain known 2-tag systems whose halting problem is provably unsolvable. --r.e.s. 22:58, 7 October 2007 (UTC)

Although I agree the test-case might deserve a brief mention merely because it has resisted attempts to prove anything about its solvability, it certainly should not be more prominent than the following point already in the article (in the Definition section): "For each m > 1, the set of m-tag systems is Turing-complete." E.g., we know how to convert any Turing machine into an equivalent 2-tag system. (If you're curious, you can find all the gory details of converting any binary TM to a 2-tag system here, which is a subsection of a webpage about Bitwise Cyclic Tag.) Maybe these points about Turing completeness (which to my mind are the really important ones) should be made more prominent. --r.e.s. 22:58, 7 October 2007 (UTC)

The problem has an unsettling and uncanny similarity to (but I don't believe is identical to) the Collatz conjecture. In particular, I believe that the one-way, one-tape two-headed monogenic/tag Turing machine shown in Minsky 1967:269 can also be used to do computations of the Collatz algorithm (and, lo and behold, some forms of the Conjecture such as 5*N+3 result in loops for a collection of certain numbers). To do Collatz all that is required is the restricted form of Turing machine, the "Minsky" two-counter counter-machine with only { CLR r, INC r, DEC r, JZ yyy, J yyy }. It computes the Collatz { 3*N+1, N/2 } in less than 16 instructions. Lemme know what you know. Thanks, Bill Wvbailey 15:55, 7 October 2007 (UTC)

In my opinion, about all that can be said concerning the test-case in question is that, so far, everyone has found it to be "intractable" -- it might, or might not, actually be an unsolvable halting problem. I don't think speculations or original work on suspected possible "connections" to Collatz should be discussed in the article. --r.e.s. 22:58, 7 October 2007 (UTC)

No, no... I totally agree with you, such speculations would have no place here unless they were corroborated in the literature. I was just hoping it might trigger in someone's mind an association to other work, seemingly unrelated. Early this past winter I spent about 3 months fiddling with the Collatz Conjecture and arrived at a dead end. I was more interested in a possible example for proof of impossibility. Thanks, Bill wvbaileyWvbailey 03:00, 8 October 2007 (UTC)

Following up a bit on the connection between the Collatz problem and tag systems ... An online article by L. De Mol points out that the extremely simple 2-tag system (a -> cb, b -> aaa, c -> a) computes the Collatz sequences for the Collatz function in the form C(n) = (if n is even then n/2 else (3n+1)/2). In this tag system, a positive integer n is represented by the word aa...a with n a's. If the author had used Post's original definition (i.e. halting only on the empty word), the tag system would never halt, and the endless cycle (... -> 1 -> 2 -> 1 -> ...) would be faithfully simulated; however, since she uses the alternative halting criterion, the tag system halts on 1 (i.e. when the word has fewer than 2 letters), which in a way is more convenient.--r.e.s. 06:22, 10 October 2007 (UTC)

The above is very interesting. And exciting: I'm glad to see some sharp minds tackling the problem from this angle. The mathematicians I was corresponding with winter were unaware of this "tag" business, and Minsky's 1961 paper "Recrusive Unsolvability of Post's Problem of "tag" and other Topics in Theory of Turing machines" in particular. I'll enter this paper into the article's bibliography. Thanks, Bill Wvbailey 15:42, 10 October 2007 (UTC)

I've expanded the Definition section of this article to clarify the types of tag system that don't use a halting symbol, and added a worked example of De Mol's 2-tag system for Collatz sequences (and of course cited her article in References). I also slightly expanded the Turing-completeness portion as a separate section. --r.e.s. 17:50, 10 October 2007 (UTC) PS: I've also added an entry and citation on this tag system in the Collatz conjecture article, with a link to this one. --r.e.s. 19:01, 10 October 2007 (UTC)

Your example is really neat. I was gonna suggest the link but you beat me to it. Wow. Bill Wvbailey 22:28, 10 October 2007 (UTC)

As De Mol's article points out, it's notable that the "smallest" known universal tag system has an alphabet of around 500 symbols, and a value of (deletion_number * number_of_symbols) that's correspondingly huge, whereas one might expect universality to crop up in tag systems not much larger (if at all) than the ones capable of computing Collatz sequences — like the present example, where that product is a mere 6. As an aside, FWIW, I've managed to slightly reduce the size of the monster universal tag system cited by De Mol, by removing redundancies in the Cocke-Minsky machine used to simulate the UTM (and have also extended the formalism to simulate any given TM — not just 2-symbol ones — by a tag system); but as it's my "original research", and not peer reviewed, I can only point any interested readers to it by this link. --r.e.s. (talk) 03:17, 20 November 2007 (UTC)

---

EDIT: Discussion on Counter Machines moved to Talk:Counter machine. --r.e.s. (talk) 01:50, 23 November 2007 (UTC)

---

Bill, may I suggest that our discussion about counter machines — everything beginning roughly with "I ran into something important with regards to the inadequacies of a 2-counter Collatz counter-machine", down to here — be removed from this page and inserted in Talk:Counter machines? There are some interesting questions that I'd like to pursue, but which seem likely to be more-and-more inappropriate here. What do you think? --r.e.s. (talk) 19:24, 22 November 2007 (UTC)

Yes. I've wondered the same. I don't know if we should go to the counter machine page or the Collatz tallk-page or where exactly. Off wikipedia ? -- we're probably into O.R. Wherever you're comfortable I'm comfortable. (I did this 2nd drawing fast -- drawing is easy to fix... it doesn't look quite right. The left head's rollers move the tape to the left e.g. 2 'symbols' erasing as it goes but also 'determining' what these symbols are, by counting blank squares between the marks. The right head's rollers also move the tape to left but only after the determination about which symbols are to be written has been made, at which time it then prints the symbols based on the symbols erased. The symbols are encoded as e.g. a = 10, b = 100, c = 1000, etc. (or could be 10, 110, 1110, 11110, given a blank tape to start with). These restrictions on the machine design are very interesting... different than the 2-Collatz machine's srestrictions. Bill Wvbailey (talk) 01:08, 23 November 2007 (UTC)

Alright, I'm moving it to Talk:Counter machine and will try not to butcher it in the process. --r.e.s. (talk) 01:50, 23 November 2007 (UTC)

---

Image inserted. Bill Wvbailey (talk) 18:13, 22 November 2007 (UTC) drawing corrected. Bill Wvbailey (talk) 01:21, 23 November 2007 (UTC)

The following is the two-counter Collatz algorithm but run on a one-way-only (left), two-headed tag-capable machine like the one shown in the drawing -- the left-hand head is read-only, the right-hand head is write only. The instruction set is { LEFT_A, LEFT_B, PRINT_B, JUMP_IF_A_blank(address), JUMP(address) }i.e. abbreviated { LA, LB, PB, Jb(address), J(address), H }. The tape never goes right, and all the previous calculations etc disappear off to the left.

The tape is assumed blank at the start excepting the starting number in unary N=5 wedged between the two heads (shown as bold-faced 0's) ...0000111110000... i.e. the left head to the left of the string of one's (e.g. N=5) and the right head to the right of the string of ones. To the right of the string N the next steps print EVEN(N/2). After this (even part of the) division by 2 is complete the string looks like this ..000111110110000... . The decision EVEN means that the algorithm is "done" and thus it is ready to repeat the above steps. The decision ODD causes the right head to print 2 ones; then left rollers/head shifts left and tests the EVEN(N/2) string 11 for blank and if not then the right rollers/head add three more ones to the number on the right; this continues until the EVEN(N/2) string is on the separator blank between EVEN(N/2) and the string 2+3*EVEN(N/2).

Instruction #:	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
Instruction:	LB	LA	Jb	LA	Jb	PB	J	LB	J	PB	LB	PB	LB	PB	LB	LA	Jb	J
Jump-to #:			1		8		1		12								1	10

Thus the tag machine is perfectly happy playing tag without erasing the left-most symbols and always moving stuff left, and has only the 5 instructions, plus halt. Again, am not sure what all this means, excepting that the algorithms are very simple. Bill Wvbailey (talk) 18:16, 24 November 2007 (UTC)

What you've created is a nice programming language for controlling the read/write heads of the machine in a way that allows it to operate much differently than a tag machine (which has only one state). Your machine, with arbitrarily many states (instructions in a program) can probably simulate binary k-tag for any k, but it can do many other things a k-tag machine cannot do — most importantly, it can freely write any word at any time, and isn't constrained to always perform just the single composite operation of a tag system (i.e., read one symbol and advance the tape a fixed number k of squares at the read-head when appropriate, always writing just the fixed word specified for the symbol that was read, etc.). --r.e.s. (talk) 20:40, 24 November 2007 (UTC)

Yes, now I understand better. Here is a version of the Collatz algorithm that you presented in the article, to be "computed" by a slightly "augmented" machine. This machine has the same instructions as before excepting the right head can print any symbol "s" and the left head can test for any symbol "s":

{ LA, LB, PB(symbol), Js(symbol,address), J(address), halt }.

This simulator does only one symbol-compare at a time. So there are three of them, instructions #1, #2, #3, and three "state executions" as indicated by the colors (the "operations" are assumed to be occurring on the transitions but each is shown as a sequence of instructions) . Thus "blue" prints "bc" and moves two symbols right into the string, "purple" prints "a" and moves two symbols into the string, and "orange" prints "aaa" and moves two symbols into the string.

Instruction #:	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
Instruction:	Js	Js	Js	PB	LB	PB	LB	LA	LA	J	PB	LB	LA	LA	J	PB	LB	PB	LB	PB	LB	LA	LA	J
Print symbol:				b		c					a					a		a		a
Test symbol:	a	b	c
If symbol-match then jump to:	4	11	16							1					1									1

My working through this and your pointing out that the tag "machine" is a one-state machine (with e.g. three transitions for the Collatz sequence) helped me understand this a lot.

I'd suggest that this state-machine aspect of the tag machine become more prominent in the article. I will mull over how to do a state-machine drawing of the Collatz machine; the only "complication" is that a whole lot of stuff happens on a transition. This is a quibble with "true" Turing machines too, that "shift" and "print" or vice versa, are not atomic (i.e. they occur in a sequence. And printing a symbol string is even less a single state if we assume one symbol per square of tape). So, I suppose we might think of the above little machine's actions as representing an "atomization" of the (one-state) tag machine's various actions in a state-transition. Bill Wvbailey (talk) 23:04, 24 November 2007 (UTC)

I'm responding here to a question you asked over in Talk:Counter machines: "can a tag machine calculate 2^N given N encoded as unary on its tape??". For machines that correspond to Post's tag systems (i.e. not multi-state machines), istm that the answer might well be "no", where the "unary" encoding of N would be a same-letter string of length N*k for a k-tag system. (But then, I don't claim to be adept at even elementary number theory, which is what these systems inherently involve — Post called it "the intrusion of number theory".) However, I think it's worth noting that even the simple 1-tag system (a -> aa) computes the function n → 2ⁿ (n ≥ 0) starting with the initial word 'a'. Just as Turing's original computing machines compute the n^th digit of a (computable) real number as the n^th figure written on the tape — without ever halting — here the n^th term of the infinite sequence 2⁰, 2¹, 2² ... is the n^th term produced by the tag system, coded in "unary" as a string of 'a's.--r.e.s. (talk) 01:35, 29 November 2007 (UTC)

Question: I've played around a bit now with the 2-tag system, in particular the Collatz algorithm and a "decrement". Question: have you seen a 2-tag algorithm to decrement a string such as aaaaa to aaaa' to aaa to aa to a to a etc ? I've not had as good luck figuring this out as I'd hoped. If you know of one don't tell me how to do it (it's a great puzzle, if nothing else), just let me know its doable. Thanks. Bill Wvbailey (talk) 21:38, 29 November 2007 (UTC)

No, I'm unaware of such a tag system, which is exactly why I replied 'istm that the answer might well be "no"' to your question above. --r.e.s. (talk) 23:12, 29 November 2007 (UTC)

Tag systems vs. (Multi-state) Post machines

About the terminology ... (1) To my knowledge, the term "tag system" always refers to essentially the kind of system described by Emil Post, in which a single "tag operation" with its fixed set of productions is applied repeatedly to a word. (This corresponds to there being exactly one state when viewed as a "tag machine".) (2) On the other hand, some authors use the term "Post machine" in reference to a multi-state "tag machine", e.g. J. Nievergelt's lectures, http://www.jn.inf.ethz.ch/education/script/chapter8.pdf — but not Uspensky's "A Post Machine", as I'd mistakenly thought (Uspensky's "Post Machine" is in fact Post's Formulation 1). There's probably no way to avoid ambiguity, but I suggest that the article reserve the term tag system for Post's version with a single tag-operation, and use the term multistate tag machine to distinguish from the several other kinds of "Post machine" in the literature. --r.e.s. (talk) 05:05, 25 November 2007 (UTC)

About two years ago, I merged what had been a separate "Post Machine" article (barely a stub, as I recall, but definitely about tag machines) into this one. If tag machines (single- or multi-state) are now to be discussed in any detail in the article, I think a separate section should be created for them. --r.e.s. (talk) 05:05, 25 November 2007 (UTC)

Tag system versus Thue- and semi-Thue systems and "word problems with cancellation": Maybe we can nail down Post's and Markov's algorithms (re one- or multi-state) with a bit of historical research. I'm not familiar with much of this, and I notice that you've been working on other articles. According to Kleene 1952:382-386 all this comes from a problem posed by Thue 1914 (the Thue 1914 reference is in Kleene 1952, in what looks like German). Is that your understanding too? Didn't Post fiddle with this as a young man? (I can look that up in Davis Engines of Logic, I believe).

People were surely formalising various kinds of "word derivation" problems in the early 1900's before Thue — but R. Murawski ("E. L. Post and the development of mathematical logic and recursion theory") writes that it was Post's work on canonical systems in 1920-21 that "founded the the theory of formal languages". It seems that Post didn't work on Thue's problem until much later.--r.e.s. (talk) 03:37, 29 November 2007 (UTC)

Can I infer here that a tag system is a simpler form of Thue system?

I don't think it's correct to say that a tag system is a form of Thue system, though each class can model the other. Both can be regarded as special types of Post canonical system.--r.e.s. (talk) 03:37, 29 November 2007 (UTC)

Thue problems don't cancel, do they? I also see that Kleene states that "Turing 1950 shows that the word problem for semi-groups with cancellation... is likewise unsolvable...."(p. 386)

Turing 1950. The word problem in semi-groups with cancellation. Ann. of Math., 2s., vol. 52, pp. 491-505.

Have you seen Turing's paper? (I just ran into this today, so I haven't). Where's the best place to see where Post posed his problem? The paper in The Undecidable? There's also Post's weird paper at the very end of The Undecidable.

Cancellation is a property of the semigroups in the word problem that Turing 1950 proved unsolvable, and to my knowledge has no counterpart in the "problem of Thue" that Post 1947 proved unsolvable. --r.e.s. (talk) 03:37, 29 November 2007 (UTC)

• 1914: Axel Thue's paper (cf bibliographic reference in Kleene 1952:536). In German.
• 1921: Post's PhD thesis published (appears in van Heijenoort p. 264ff): Explores (i) truth table derivations of propostional calculus and (ii) axiomatic approach to propositional calculus Principia Mathematica
• 1921: "While a graduate student at Princeton in 1921" (Minsky says) that Post [1965] studied what became known as the "tag" problem. Post [1965] is actually unpublished Post 1941 Absolutely Unsolvable Problems and Relatively Undecidable Propostions: account of an Anticipation" that appears in Davis 1965 The Undecidable. See below.
• 1927: Hilbert's talk where he describes an axiomatic system. I have this paper in English but it's translation and quality is suspect. Was gotten off the net. Based on this it seems Kleene 1952 develops almost the identical axiomatic system in his CHAPTER IV: A FORMAL SYSTEM (p. 69ff). Goedel does the same in his 1931.
• 1928: Hilbert & Ackermann's Principles of Mathematical Logic, translated into English and published in 1950.
• 1930: Goedel references Hilbert and Ackermann 1928 (cf van Heijenoort 1967:583) and proves that their 'restricted functional calculus' [restricted predicate calculus] is complete. The notion of "provable" versus "true".
• 1931: Goedel adopts Hilbert's 1927 system together with a [primitive] recursive axiom schema to formally axiomatize a system powerful enough to express the notion of "v is a provable formula" within the system itself. He emphasizes the notion of a "finite sequence of primitive signs... and it is easy to state with complete precision which sequences of primitive signs are meaninful formulas and which are not. Similarly, proofs, from a formal point of view are nothing but finite sequences of formulas with certain properties." (van H. p. 597). He formally defines notions of "immediate consequence" and "provable formulas" (ibid).
• 1936: Post's Formulation I (cf The Undecidable 1965:288ff)
• 1941: Post's Absolutely Unsolvable Problems and Relatively Undecidable Propostions: account of an Anticipation" is rejected. Published in 1965 by Martin Davis in The Undecidable. In his 3. The problem of "tag" Post attributes the name "tag" to "B. P. Gill" (p. 370). He states that he "made [it] the major project of the writer's tenure of a Proctor fellowship in mathematics at Princeton dduring the academic year 1920-21" (p. 372). He began with the question of if, and how, to go from one expression in (~,V) of PM (Principia Mathematica) to another expression in (~,V) and proved in "an early unpublished method" that this could be "completely solved" (p. 370 ibid). But when he tried to embrace all of PM (i.e. predicate calculus) "the general problem proving intractable, successive simplifications thereof where considered, one of the last being this problem of "tag" ... . The solution of this problem thus appeared as a vital stepping stone in any furhter progress to be made." (p. 371 ibid). His formualtion of "tag" is the same as in the wikipedia article.

Tag systems, as Post created them, differ slightly from those defined in the main section of the article; his are as described in the "Historical note..." section. Post himself points out that by his definition, tag systems are almost but not quite monogenic normal canonical systems. Apparently, virtually all later writers simply adjusted the definition so as to make them monogenic normal canonical systems, and the main article does likewise. --r.e.s. (talk) 03:37, 29 November 2007 (UTC)

He mentions the 0 --> 00, 1 --> 1101, v=3 (i.e. erase or pass over 3 symbols on the left) to be "intractable". "This frustration, however, was largely based on the assumption that "tag" was but a very minor, if essential, stepping stone... ." Au contraire: "In the late summer of 1921, how3ever, the reductions carried through at Princeton in proving the equivalence of canonical forms A and B suggested a further transformation of canonical form B, and, indeed, led to a whole series of reductions with the final canonical form very close to the seemingly special form of "tag"."(p. 373, ibid). This is his form C that he arrives at (long) last at " g_iP produces Pg'_i ", or what he calls his "normal system" (p. 409, ibid). It is this that Minsky 1967 calls "one of the most beautiful theorems in mathematics" (p. 240) and writes as g$ --> $h.

• 1943: "Post mentions the (00, 1101) problem in passing, in his [1943] paper -- the one that announces the nromal-form theorem" (Minsky 1967:268).

• Post 1943, Formal reductions of the general combinatorial decision problem," Am. Journal of Math. 65, 197-268. [?? p. 197-215 per the citation in The Undecidable]. This paper is referenced by Minsky 1967 and by Kleene 1952.

• 1944: Emil Post 1944, Recursively Enumerable sets of Positive Integers and their Decision Problems cf Undecidable p. 305. Post references his own paper 1943. Discussions in this paper incorporate the notions of 1943.
• 1947: Emil Post 1947, Recursive Unsolvability of a Problem of Thue, cf Undecidable p. 292ff. He references Thue 1914, above. "The word problem for semigroups." Independently proved by Markov in the same year. Post makes use of a Turing machine in this proof. He goes one direction (semi-Thue) from a starting string to an end string hq_r+2h [state q_r+2 results with head wedged between two special symbols "h"]. But then in the converse direction, starting with hQ'h can he produce the starting string? In a footnote he comments that the reverse process leads to "a tree of assertions, elements not necessarily distinct, The exact same tree occurs with the Collatz sequence is run in reverse. "Certainly then, a solution of the problem of Thue in its full generality would thus lead to a solution of the "decision problem for the class of normal systems on a, b."" (p. 298, The Undecidable). This is a proof that appeared in his:

• 1946: Post 1946, A variant of a recursively unsolvable problem, Bulletin of the American Mathematical Society, vol. 52 (1946), pp. 264-268.

• 1950: Turing 1950. The word problem in semi-groups with cancellation. Ann. of Math., 2s., vol. 52, pp. 491-505. [??]
• 1952: Kleene 1952 discusses "§71. The word problem for semi-groups" on pp. 382-386.
• 1958: Martin Davis 1958, Computability and Unsolvability McGraw-Hill. I've seen the book but haven't explored whether "tag" is discussed.
• 1961: Minsky 1961, Recursive unsolvability of Post's problem of "tag" and other topics in theory of Turing machines". I have this paper.
• 1965, 1941: Martin Davis publishes Emil Post 1941 in his Undecidable p. 338ff. Tag is mentioned directly by Davis; this is a long and tedious paper. A search for tag will be necessary. Davis notes that "The equivalence proofs given between Canonical forms A, B, and C are of historical interest, showing as they do the evolution of Post's ideas from his early work on the propositional calculus.
• 1967: Marvin Minsky 1967, Computation: Finite and Infinite Machines, McGraw-Hill, NJ. Discusses this stuff with particular reference to the notion of "Axiomatic Systems and the Logistic Method", "Effective computability as a Prerequisite for proof" and "Proof-finding procedures" (p. 221-224), Post's symbol manipulation systems, his normal-form theorem, tag, "monogenic Canonical Systems".

--- End time line.

• In particular I'm missing Thue 1914 (in German, couldn't read it anyway), Post 1943, Hilbert-Ackermann 1928 in the 1950 English translation, Turing 1950, Davis 1958 (but have seen in library). I have seen and cc'd part of Markov (ca 1950's) but probably not enough to be useful. Bill Wvbailey (talk) 04:15, 26 November 2007 (UTC)

---

I moved a Question by Wvbailey (and my reply) to the previous section, where I think it belongs as follow-up to what was already posted there. --r.e.s. (talk) 23:18, 29 November 2007 (UTC)

---

Comment: I would agree with Post's algorithm that tacks on the next symbol(s) then deletes the front symbols. Thus this is a two-state machine.

No, it isn't — just as a single TM state involves a compound operation and is nevertheless a single state. --r.e.s. (talk) 23:13, 29 November 2007 (UTC)

I am not convinced that a most-generalized n-tag machine can be built that, under all conditions, can do the whole job in one "state" (where a state transition occurs at one tick of a clock), even if the "delete" and "concatenate" operations are done in parallel. The case of concern is when you start with a single symbol, e.g. "a". For example: { a --> bc }. Start with the single symbol "a". You have to write the bc after the "a" before you can strike out "ab"

• a --> abc --> abc --> c

I'd argue that in this example (at least) two clock pulses are required, or a single clock plus a delay that acts as a 2nd state. Bill Wvbailey (talk) 21:38, 29 November 2007 (UTC)

It's not a matter of clock pulses or any other "implementation issue". A tag system (or the equivalent "tag machine") is an abstract system whose definition is in terms of a single compound operation — what Post called the tag operation. Viewed in terms of an abstract machine, that operation constitutes just one state, in exactly the same sense as the compound operation involved in a single TM state. --r.e.s. (talk) 23:13, 29 November 2007 (UTC)

Implementation issues still apply to abstract computations. The only "abstraction" is their unlimited memory capacity. Do you have a cc of Minsky 1967? If so see 2.0.1 Moments of Time and 2.1 States and Signals(p. 12ff) . I've noticed that the computer-science notion of "state" differs very much from that of the engineer's and physicist's notions. While I too have written thousands of lines of code that simulate "state machines" I recognize that each "state" is equipped with many true internal states and any notion that these compound events represent a single "state" is flat-out wrong with respect to the physics of the events and the engineering behind them. Minsky defines "state" satisfactorily enough for an engineer and physicist (they include both position and velocity of all the elements in the system -- Minsky is saying that the velocity of all the elements is 0 during what he calls a "state" between ticks of a clock); he then observes that the output state at the moment t must not depend on the input state at that same time t" in order to "prevent unrealizable -- paradoxical -- descriptions of situtaions..." (p. 14)

In support of my complaint I'd also recommend the paper by Robin Gandy where he addresses this same issue of the speed of light:

Robin Gandy 1980, Church's Thesis and the Principles for Mechanisms in J. Barwise, H. J. Keisler and K. Kunen, eds., The Kleene Symposium", North-Holland Publishing Company (1980) 123-148.

I prefer the Post implementation that you describe. It's clear, clean and correct. In his rejected 1941 -- which he clearly rewrote for his 1943 -- he stated the tag system this way:

"...we set up the following operation for obtaining from any given non-null sequence

"B = b₁ b₂ ... b_l

" on the symbols 0, 1, ..., u-1, a unique derived sequence B' on those symbols. To the right end of B adjoin the sequence associated with the symbol _b1 in the given basis, and from the left end of this augmented sequence remove the first v elements -- all if there be less than v elements....⁵¹" (The Undecidable p. 371)

"⁵¹. In an early formulation of this problem, b₁ was first checked off, the corresponding associated sequence added, then the v-th element after b1 was checked off, corresponding associated sequence added, and so on. Whether the iterative process terminated or not then depended on whether the ever advancing check mark did or did not overtake the usually advancing right end of the sequence, whence the suggestive name proposed by Gill for the problem." (The Undecidable p. 371)

'nuf said about this. I had no luck on the state-machine page trying to make a similar point: that the C-S definition of "state" is misleading and in the eyes of an engineer and physicist flat wrong, even with the definitions and quotations in hand from a variety of books. Bill Wvbailey 17:27, 1 December 2007 (UTC)

When formulated as an abstract machine, it's immediately clear that the "tag machine" equivalent of a tag system has only one state in its "controller logic". A computation by an abstract machine is typically described as a sequence of transitions from one "complete configuration of the system" to another — i.e., a "trajectory" in the set C of all possible complete configurations of the system, according to some fixed transition function. (Input & output functions being appropriately defined w.r.t. C, as well.) For example, the complete configuration of a Turing machine is typically specified by a triplet (q, A, bB), where q is the "controller state" and A/B are the finite tape contents to the left/right of the current cell, whose content is b. Similarly, the complete configuration of a tag machine is specified simply by (W) (the current tag-word) alone — there are no multiple states of the controller. In programming terms, the tag-system controller logic is a program that's just a single case-statement that's always the "current state(ment)", by definition of the tag operation. OTOH, a "variant-tag machine" with multiple controller states might have its complete configuration specified by (q, W, j), where q is an instruction pointer to the current state(ment) in the controller program (now having possibly a number of more-primitive instructions, etc.), and j is a pointer to the current letter of the current word W. --r.e.s. 20:56, 1 December 2007 (UTC)

A possible source of confusion about the term "state" is that the complete system-configuration of an abstract machine is sometimes called the system state. A physicist might want to compare the set C, of complete configurations of such a machine, to the phase space of a physical system (although C is a countable set, whereas the latter typically isn't). An abstract machine's controller-state is a component of its system state, analogous to a physical system's spatial configuration (say) being a component of its physical system state. In this analogy, a computation of an abstract machine is a trajectory in its configuration space C under the action of the machine's transition function, similar to a physical system having a trajectory in phase space under the action of physical laws. --r.e.s. 20:56, 1 December 2007 (UTC)

n-tag definition

When it says 2-tag system, what does the 2 refer to? It seems to be the halting length, but the article doesn't seem to explicitly say, and I'm new to this topic, so I'm not positive. — Olathe (talk) 01:42, 30 October 2012 (UTC)

change this to https://en.m.wikipedia.org/wiki/Tag_system_(mathematics)

We should clearly disambiguate this from tag systems in the non-mathematical sense.

For example https://news.ycombinator.com/item?id=35597934 (https://buttondown.email/hillelwayne/archive/tag-systems/) is not related. 2403:6200:8851:D9B4:4843:9546:EBBC:EB0A (talk) 11:20, 14 July 2023 (UTC)