(No linguistics that I can see.)
A follow-up to my posting on Collatz sequences, picking up an open question in one-symbol Smullyan systems, from an obscure 1970 paper by Stephen Isard and me.
(In one-symbol Smullyan systems, the objects are strings of a single symbol, let’s say 1, subject to very simple rules for producing new strings.) Simplifying things some, the system (devised by Steve) we considered started with 1 and advanced by two rules:
(1) x ⇢ xxx
(2) xx1 ⇢ x
The first triples any number, the second reduces any odd number 2N+1 to N. So from 11111 (that is, 5), we get either to 15 or to 2. It’s easy to see that all the strings are of a length ≣ 0 or 1 (mod 3) (but not ≣2). The question is whether every string of length ≣ 0 or 1 (mod 3) is enumerated by this oss. We showed in the 1970 paper that any exception could not be less than 7044, which is ≣ 0 (mod 3): 7044 = 3 x 2348. So, can we get from 1 to 7044?
A tricky question. 1 ⇢ 3, then 3 ⇢ either 9 or 1, then 9 ⇢ either 27 or 4, 27 ⇢ either 81 or 13, 81 ⇢ either 243 or 40, 13 ⇢ either 39 or 6, etc. There’s a lot of profuse branching in these productions, which the computational resources available to us in 1970 couldn’t really cope with. Greg Huber and Kyle Kawagoe at UC Santa Barbara approached the problem with vastly greater computer power than we had in 1970 and (much more important) with an algorithm (not yet published) for traversing the production trees efficiently. They were kind enough to send us (today) the results for 1 ⇢ … ⇢ 7044 (which I report on here with their permission). Yes, you can get to 7044, in about a hundred steps.
So the smallest possible exception isn’t one, but that of course doesn’t answer the open question. Math marches on.
Leave a Reply