Turing Tumble Community

What patterns are(n't) possible?

Just some general musings…I was marveling at the variety of problems and patterns that have been proposed and achieved, both in the original book, as well as in the discussions here. We know that with large enough board and sufficient supply of pieces the TT can do anything a computer can, and so any finite sequence can be generated. But what about the TT as it comes out of the box?

There are 2^n possible sequences of length n. What is the largest value of n so that all 2^n sequences can be generated with the original TT set? Or, said differently, what is the shortest sequence that cannot be generated?

It seems that sequences with regularity of some sort will be easiest to generate with a smaller number of pieces, and sequences with no apparent regularity or repeating pattern will require more pieces. Perhaps that would be a place to start to find short sequences that cannot be generated.

1 Like

This is my guess and my thought process, though it may not be correct
First off, I’m going to assume an upper bound would be as many balls come in the box (~20 each color). We can make another approximation by assuming the pattern is RBR n[RB] BRB for now. Now, we need to find n. In order to do this we need to find the largest counter that can be changed by 2 balls (This is ignoring a lot of small factors), and still flip positions. With this, we get n=9, so an upper bound would be around RBRRBRBRBRBRBRBRBRBRBBRB, giving 2^24. Now, possibly we need to find one shorter than this, such as shortening the beginning sequence.

If we started with BR n[RB] BR, that would shorten n down to 5, giving BRRBRBRBRBRBBR as an answer, granted, we still haven’t even brought up the amount of pieces in the box, which may or may not come into play.

I don’t think I understand your notation.
Also, in my musings, I was imagining we had as many balls as we needed. But, I suspect that there are already many patterns with the about 40 balls that can’t be generated. In fact I’ll bet there are 10-ball patterns that can’t be generated.

Here is my knee-jerk attempt at a candidate. BB RRR B R B RR .
Why? Because it seems to have no repetition or structure that one can easily exploit. I haven’t had a hand at trying to build it, since I’m feeling lazy. But being cooped in will probably give me plenty of time…

Ah, that makes more sense. I shall attempt to change it this way. Thank you very muchc for specifying.

The very largest I could get that is a good enough example for now is 128R, 1B, 128R, 1B, 64R, etc. This is based on the largest counter I could make on a single board with a single ball before switching to another color one time, which can count to, which is 64. We can make this even smaller with an actual pattern of R BB RR B R BB RR B R BB RR B R B R
[Repeat] or (Infinite)(3(1R 2B 2R 1B) 1R). This limits not by the amount of resources but by the board’s space. This uses 21 balls before it repeats, though I can almost guarantee there is a shorter pattern. I am jumping a bit to conclusions with this guess, though it isn’t very far out that this pattern is indeed impossible to make on a board.

Here was my test board to get this pattern by making a short sequence that used “all” of the board, starting with a red lever
https://www.lodev.org/jstumble/?board=bbrgbgbglexeleerllfxrfrrrf1rreerrrlee1rxeer0lre0_71_70