The question has now been settled! All even periods are possible. This result was proved by James B. Shearer of the IBM Thomas J. Watson Research Center in Yorktown Heights, New York. Shearer writes:
"I read with interest the computing science column 'A Question of Numbers' by Brian Hayes in the January-February 1996 American Scientist. The column discussed, among other things, what periods a certain tag system can have. I believe I can show that any even period is realizable.
"The tag system can be described as follows. It maps finite binary strings to finite binary strings. If the first digit is 0, we add 00 to the end of the string and delete the first three digits. Alternatively, if the first digit is 1, we add 1101 to the end of the string and again delete the first three digits.
"I now show how to form strings with any desired even period under the above mapping. Let A=001101. Let B=110111010000. It is easy to see that A has period 2; that is, after two iterations of the mapping, the original string is regenerated. Similarly, B has period 4. Furthermore, A has length 6 and B has length 12. This means A*X will map to X*A after 2 steps and that B*X will map to X*B after 4 steps. (Here * denotes concatenation of strings, and X is any string). It follows easily that A^n*B (the string consisting of n copies of A followed by one copy of B) will return to itself after 2n+4 steps. There remains the possibility that the actual period might be a divisor of 2n+4 rather than 2n+4 itself, but this possibility is excluded by observing that no intermediate string can end 10000. Hence we can obtain all even periods with a suitable choice of n."