Comparing models of multi-head finite-state prediction
A finite-state gambler is a low-resource computational device that moves forward through a stream of data, iteratively making predictions about the next symbol. If the data follows a pattern that is sufficiently simple and localized, then the gambler can win money over time by placing bets according to these predictions. Studying the capabilities and winning rates of these computationally restricted gamblers has yielded significant insights about data compression and ergodic number theory.
This project will investigate variants in which multiple low-resource devices moving through the sequence at different rates cooperate to make predictions. These multi-head gamblers are still resource-efficient, but they can take advantage of long-range correlations in data, potentially revealing larger-scale structural patterns. Our focus will be on establishing equivalences between different types of multi-head gamblers by showing how they can simulate one another.