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.

Name of research group, project, or lab
Lutz research group
Representative publication
Logistics Information:
Project categories
Applied and Computational Mathematics and Statistics
Computer Science & Engineering
Mathematics
Student ranks applicable
Sophomore
Junior
Senior
Graduate Student
Student qualifications

Familiarity with finite-state automata (e.g., by taking Theory of Computing) and comfort with writing mathematical proofs.

Hours per week
1 credit / 3-6 hours
Compensation
Research for Credit
Number of openings
2
Project start
Spring 2027
Contact Information:
Mentor
nlutz2@nd.edu
Name of project director or principal investigator
Neil Lutz
Email address of project director or principal investigator
nlutz2@nd.edu
2 sp. | 0 appl.
Hours per week
1 credit / 3-6 hours
Project categories
Applied and Computational Mathematics and Statistics (+2)
Applied and Computational Mathematics and StatisticsComputer Science & EngineeringMathematics