[Theoretical, hard] Access an infinite number of columns


#1

This is a theoretical challenge. Finding a solution and explaining it will naturally be harder (and different) than typical puzzles.

Suppose that…

  • In addition to blue bits, we have red bits. The only difference is color and only to make it easier to distinguish these special bits from any regular bits that may be added.
  • There is one ball drop instead of two at a fixed location on the board.
  • The board is infinite in extent around the ball drop. (The upper portion may be ignored.)
  • An infinite number of flippers are available. When a ball lands on one, it is removed from the board and a new ball is released from the ball drop.

The challenge: Place an infinite number of red bits along with any number of other components (except intercepters) such that…

  • Each red bit is in its own column. That is, no red bit is directly vertically above another red bit.
  • Each red bit is flipped exactly once.
  • Each red bit is flipped within a finite amount of time from the first ball dropping.
  • Each ball flips at most one red bit. (Edited this in just now.)

There is no requirement that these red bits be at the same horizontal level. I expect they will be along diagonal lines in some way.

I don’t (yet) have a solution for this. Good luck!


Proof of Turing Completeness?
Proof of Turing Completeness?
#2

I might be misunderstanding or trivializing your problem.

Near as I can tell, an infinite diagonal of red bits, each with initial condition pointing away from the next red bit, meets your requirements.

The first bit will always be flipped because it is directly beneath the ball emitter, and bits are always flipped when balls land on them.

If any bit on row N-1 is flipped then the bit on row N must be flipped because bit N-1 will direct its marble toward bit N, and bits are always flipped when balls land on them.

All red bits are in separate columns because they are all on a diagonal.
All red bits are each flipped exactly once because only one ball will ever be released, and that ball will flip all of the red bits.
All red bits are flipped within a finite amount of time from the last ball dropping, because for any bit N it will be flipped N cycles after the first ball drops.

If red bits can be in any arbitrary starting state, then instead of an infinite diagonal of red bits use an infinite diagonal of a three line pattern: red bit on line 1, green piece on either side of the red bit directing the ball back toward the middle on line 2, and green piece directing the ball toward the next red bit on line 3. Each of the line 3 green pieces must be pointing the same direction.


#3

Ah-ha, good catch! I missed one condition: each ball flips at most one red bit. I’ll add that to the original post.


#4

Edit: . . . sorry, it’s clearly not trivial any longer if it takes multiple rows for each repeating block. I was hasty and sort of insulted your puzzle and I apologize.


#5

No worries, I was totally ready to accept that this puzzle is easier than I thought. :slight_smile:


#6

Turns out, my puzzle was easier than I thought. Having an actual board to work on helped a lot.

Emulator link

The functional unit here is composed of two gear bits, one gear, one ramp, one crossover, and one (“red”) bit. They can be placed arbitrarily far apart so long as you can connect the output from the crossover of one to the top gear bit of the next one. Also, each unit can be reflected horizontally if one wishes to extend to the left instead of the right.


#7

Sorry. X__X

The solutions to infinite-sized things (when solvable at all) tend to reduce to “solve the first one” and “given a solved N-1, solve N.”


#8

That does usually happen, yes! I was just thinking that this one might’ve ended up with column spacing being some function other than a constant.