I found this website two weeks ago, and read n-gram-CPS from https://discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141/2.
Since n-gram-CPS seems easy to implement, I reimplement the version described in readme and found that it fails on many trivial cases (e.g. cannot distinguish the length of 1111…1 mod 2).
Add more history information to the tape helps a lot in many cases.
For example, if 1111…11 is generated by a translated cycle of shift 2, and the transition of last update of each position is recorded on the tape, it may look like (1,(A,0))(1,(B,1))(1,(A,0))(1,(B,1))…(1,(A,0))(1,(B,1)).
However, fixed length historical information is not enough, as nested loops may overwrite all useful historical information. LRU cache is a solution (but not perfect) for this: we can record the order of the last occurrence of all 10 possible transitions in each position.
2 Likes