2026-08-21T18:34:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27441 2026-08-21T14:42:40Z ddc:004 open_access

Multi-Head Finite-State Dimension Huang, Xiang Li, Xiaoyuan Lutz, Jack H. Lutz, Neil Finite-state dimension effective dimension algorithmic randomness We introduce multi-head 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 multi-head 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 multi-head 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xiang Huang and Xiaoyuan Li and Jack H. Lutz and Neil Lutz 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.59 urn:nbn:de:0030-drops-274410 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.59 eng https://creativecommons.org/licenses/by/4.0/legalcode