Multihead Finite-State Dimension

We introduce multihead finite-state dimension, a generalization of finite-state dimension in which a group of finite-state agents (the heads) with oblivious, one-way movement rules, each reporting only one symbol at a time, enable their leader to bet on subsequent symbols in an infinite data stream. In aggregate, such a scheme constitutes an h-head finite state gambler whose maximum achievable growth rate of capital in this task, quantified using betting strategies called gales, determines the multihead finite-state dimension of the sequence. The 1-head case is equivalent to finite-state dimension as defined by Dai, Lathrop, Lutz and Mayordomo (2004). In our main theorem, we prove a strict hierarchy as the number of heads increases, giving an explicit sequence family that separates, for each positive integer h, the earning power of h-head finite-state gamblers from that of (h+ 1)-head finite-state gamblers. We prove that multihead finite-state dimension is stable under finite unions but that the corresponding quantity for any fixed number h>1 of heads—the h-head finite-state predimension—lacks this stability property.

Committee: Jack Lutz (major professor), Andrew Miner, James Lathrop, Steven Kautz, and Timothy NcNicholl