One Adaptive Trailing Head Can Outperform Many Oblivious Trailing Heads
This work strengthens a known separation between adaptive and oblivious strategies in finite-state dimension, showing that adaptivity provides a dramatic advantage over scale.
The paper proves that a single adaptive trailing head can outperform arbitrarily many oblivious trailing heads in finite-state dimension, with a performance gap exceeding 0.3.
In the setting of multi-head finite-state dimensions, trailing heads lag behind a leading head, accessing past data to aid a finite-state gambler placing bets on successive bits read by the leading head. Cruz, Glashausser, Li, and Lutz (2026) proved that, for any fixed number of trailing heads, adaptive (data-dependent) movement rules can strictly outperform oblivious (data-independent) movement schedules. In this paper we strengthen that separation by proving that a single trailing head with adaptive movements can outperform, by a large and uniform margin, arbitrarily many trailing heads with oblivious movements. Formally, our main theorem states that there is a binary sequence whose adaptive two-head finite-state strong dimension is less than its oblivious multi-head finite-state dimension, and that the gap is greater than 0.3.