…or why one-dimensional two-way cellular automata operating in linear time are likely more powerful than their real-time counterparts.
The evacuation platform creaks in the waves — a long, narrow beam with a line of shipwreck survivors standing shoulder-to-shoulder, all facing the distant lights of the rescue ship.
Each survivor sees everyone ahead, but the chaos behind them is a mystery.
Over the roar of the storm, a rescue helicopter swoops in from behind.
To lift the platform without capsizing it, the hoist rope must be attached to the one survivor standing exactly in the middle.
Attach it anywhere else, and the whole platform will flip like a seesaw.
The survivors are hoarse from smoke; none of them can speak.
Yet they can hear the helicopter pilot — the only person able to give instructions.
The pilot, half-blinded by sea spray, can see only the last survivor at the back of the line.
No idea how many others are hidden in the storm — could be dozens, hundreds, or more.
Before lowering the rope, the pilot shouts down:
- A strategy every survivor must follow,
- A finite set of distinct items (colored tags, numbered clips, strange shapes…),
- And attaches those items to the rope in a chosen initial order.
Then the rope descends into the darkness.
The last survivor grabs the rope.
One by one, as the rope moves only forward, each survivor may:
- Glance at all survivors ahead of them,
- Inspect the current order of the items on the rope,
- Rearrange those items however they like,
- And then choose:
If they believe they are the true middle, they fix the rope to the platform and signal the helicopter.
If not, they hand it to the next survivor.
The rope cannot move backward.
Only the first attachment counts.
Can the pilot choose a finite set of items, their initial order, and a strategy such that — no matter how many survivors are on the platform — the correct middle survivor is always the one who attaches the rope?