Make the longest run ever. The solution must end in a stop eventually, but how long a run can you make?
It can be a single colour solution, double colour solution or multi colour solution
This is a simple 10 bit counter, and will stop when falling into the red trap
Ok, so that’s on a simulator and uses more than standard pieces in a set, but with gear bits surely a few hundred thousand is easily possible.
131199 ??
I think I can do this on a standard board with pieces as delivered.
Solution for ball pattern 131199 balls long (board, as delivered- if you keep replenishing the balls!)
Blue side counts 1024, then releases a red ball, that immediately goes to blue. This repeats 127 times. Then another 1024 blue balls go, but the final red ball released does not get to the pattern, but is intercepted.
Length =( 127*(1024+1)) +1024 = 131199
Two comments to what has already been done…
-
I don’t think solving this on a simulator using more pieces than the standard issue game is interesting, because one can always build a larger counter using more bit pieces… so an arbitrarily long run can be output. (Just tell me how long N you want, and I’ll create a counter with log N bit pieces that does the trick.)
-
I was very interested in @RingTheBell 's solution, in particular because it had 18 bit parts (10 regular, and 8 gear bit), yet counts higher than 2^18. That seems impossible, because of the following reasoning:
With 18 bit pieces, there are only 2^18 different board configurations. If during the generating of a run of output balls any configuration is repeated, then the output sequence will never stop - the machine is in an infinite loop. Thus, at most 2^18 balls output is possible.
Yet, the solution given counted to greater than 2^18. What gives??
The explanation is that there are more than 2^18 configurations… there is an extra degree of freedom, depending on whether a ball is coming down from the blue/left, or red/right side. The levers and ball feeders thus are acting like a 19th bit… The overall state space has size 2^19. (I.e., there are 2^19 configurations, given by specifying the orientation of each of the 18 bits, and which of the two ball feeders is about to release a ball.)
So, the natural question then is: Can we get a run of size 2^19 ?
That would be the absolute maximum possible (unless there is some other subtle nuance that I’m overlooking). Can it be achieved? If it can, it will probably require each of the eighteen bits to be reachable from both ball release mechanisms.
Edit: I played around a bit and came up with this proof of concept:
This layout has a four-bit counter (the blue bits) yet counts 32 instead of 16 balls… it first counts 16 balls released from the left, then switches over and counts 16 balls released from the right, then halts.
Unfortunately, the mechanism to switch between the two counting phases is using four gear bits, which is a waste, since with a total of eight bits we could have instead just counted using blue balls alone up to 2^8 = 256. But I was just trying to demonstrate a point - the use of a counter to count twice the maximum value.
After re-examining my solution, I have discovered how to get a 2^(n+1)-1 ball pattern using only n bits, but it will not fit on a standard Turing Tumble board. The key is to think of my solution as an 18-bit counter which has been split in two. Since the board is not tall enough to have all 18 bits in a row, the overflow from the 10th bit, rather than triggering the 11th bit directly, instead triggers a red ball which triggers the 11th bit. Basically, between these two bits we are swapping a blue ball for a red ball. Because this substitution does not affect the state of the counter, it will still correctly count the number of blue balls. This also means that this substitution can be made at any point in the counter. I have illustrated this phenomenon using a 4-bit counter:
If Bb is the number of bits that count blue balls and Br is the number of bits that count red balls, then the total number of balls in the output pattern will be 2^(Bb+Br)+2^Br-1. From this equation and from the example above, we can see that the longest pattern occurs when Bb = 0 (one blue ball and one red ball dropped per count), which gives 2^(0+Br)+2^Br-1 = 2^(Br+1)-1. Obviously, Br = 18 will not fit on the board. In fact, 8 seems to be the largest possible value of Br for a standard TT board. I don’t think this is quite a proof that my solution yields the longest possible pattern with only the parts in the kit, but it is certainly strong justification. I think to prove it one would have to prove that a simple binary counter is the most efficient use of gear bits for the purposes of counting.
1 Like
This is a very nice demonstration of how to use n bits to count to 2^(n+1). (I’m counting the last released ball, which ends up in the interceptor, as part of the sequence.)
I think a proof that this is the most theoretically possible follows along the lines of what I said earlier. Usually proofs trying to show “this way is the best” are quite difficult, because who can imagine what bizarre other way one might come up with that might, for example, use n bits in a way different than counting? So, the proof is along information-theoretic lines. I’ll try to firm up what I wrote so that hopefully it is more clear.
Consider the state of the system just as a ball is being released from a ball hopper. The only pieces that are given that can have more than a single state are the bit pieces. (While it is true that the ramps change state (i.e., move, flip…) while the marbles go through them, they return to the same orientation after the marble passes. So, they exhibit only a single state (their untipped one) just as a ball is being released.)
So, by “state of the system” as a ball is being released, we mean the layout of pieces, the orientation of all of the bits on the board, and the information as to whether a blue ball or red ball is about to be released.
It should be clear that for any layout of any number of pieces from those that are available, the total number of distinct states that can be exhibited is at most 2 * 2^18 = 2^19. This corresponds to the placing of all of the pieces in the layout, the orientation of up to 18 bit pieces, and the information as to whether a blue or red ball is being released.
The only thing that can change during a run is the orientation of the bits, and whether a blue or red ball is being released.
Assuming an inexhaustible supply of blue and red balls, in any run of a layout, if the same overall system state is revisited before a ball is intercepted, then it should also be clear that the machine is in an infinite loop, and will continue to re-visit that system state again and again, thus never stopping with a fixed output. As we are only interested in how many balls can be released with the sequence subsequently stopping, such a run is not a solution - so any solution must avoid re-visiting a system state.
Since there are only 2^19 system states, at most 2^19 balls may be released before a system state is repeated, so an output of 2^19 balls (including the last one in the interceptor) is the maximum possible.
What does this show? That IF the board were long enough, the longest output run would be 2^19 (or, if you prefer not to count the one in the interceptor, 2^19-1). However, the board isn’t long enough to achieve a solution of the type in your last picture.
So, where are we? The theoretical limit is 2^19, but likely that can’t be achieved. You’ve shown 2^10 * 2^8 + 2^8 = 262,400 on your previous solution, by splitting the 18 counters into 10|8. (meaning 10 left, 8 right). Your best using the technique suggested above would be a 0|18 split, but the board isn’t long enough to do that. But could we implement an 8|10 split, giving a run of length 2^8 * 2^10 + 2^10 = 263,168? Or, perhaps a 9|9 split, which would give 262,656?
Even if these improvements can be made to your original solution, there is a big gap between those numbers and the limit of 2^19.
I think perhaps this upper bound of 2^19 is too loose, and can be brought down some, based on my earlier suggestion that to involve a bit in a counter for each side, the bit has to be reachable from each ball hopper. The board layout and length puts significant limitations on this, which is why we can’t have a stack of 18 bits. I’m wondering whether an upper bound can be derived from looking at the number of bits reachable from both ball hoppers, the number of bits reachable from the left hopper only, and the number of bits reachable from the right hopper only. Somehow, those three numbers might figure in.