AI summaryⓘ
The authors study randomized algorithms that usually stop but can run forever on rare inputs called random tapes. They analyze the complexity and fractal dimension of these exceptional tapes, providing bounds that describe how likely long running times are under various conditions. By comparing different repair rules on graphs, they show that even when basic termination measures match, the detailed behavior can differ greatly, sometimes causing one process to stop quickly and another to run indefinitely. Their results also extend to k-SAT problems, linking entropy measures to the likelihood of fast termination and the complexity of infinite runs. Finally, they present an exact formula relating the probabilities of runs to their coded descriptions and tail behavior.
randomized algorithmsrandom tapesKolmogorov complexityHausdorff dimensiontermination probabilityk-SATentropystopping timerepair rulestrace growth
Abstract
A randomized algorithm may terminate almost surely even though exceptional random tapes make it run forever. This paper studies the survival tail, the Kolmogorov complexity of one such tape, and the Hausdorff dimension of all of them. For each $s>0$ at which the powered repair matrices commute, the main theorem bounds $\sum_wP[w]^s$ over surviving prefixes $w$, uniformly over deterministic nonanticipating selectors. The case $s=1$ controls termination; the full family gives weak-source and dimension bounds. The source powers contain information absent even from the ordinary repair kernel and the complete stopping-time law. Under one common finite tape source, two overlapping disagreement-repair rules on a four-vertex path have the same ordinary kernels and the same stopping-time law for every selector, yet their nontermination dimensions can be arbitrarily close to zero and one. At one common source-power level, the same dominated tape source makes one rule run forever but gives the other an exponential stopping tail. The separation is caused by action labels that produce the same state transition and are therefore invisible at power one. For bounded-dependence $k$-SAT, conditional block min-entropy above the trace-growth threshold gives exponential termination, and the effective dimension of an individual infinite run is bounded by the trace growth induced by the clauses repaired infinitely often. Tree formulas asymptotically attain the maximum-degree dimension and global source bounds, while clique formulas attain the graph-specific one-step threshold in the stated regime. An exact backward likelihood identity complements these setwise results with tail and coding bounds for each run.