Preprint
Oct 2026
The smallest programmable machine and the hardness of analyzing it
We investigate the computational complexity of analyzing the structural and behavioral properties of deterministic k-pebble automata, which represent a natural framework for studying minimal programmable machines. First, we provide an explicit construction of a three-pebble automaton U capable of simulating any determi...
J. Montoya
· 0 citations