Computational limits of tiny programmable machines revealed
The smallest programmable machine and the hardness of analyzing it
Computational Complexity
Summary
The paper looks at very small computing machines called pebble automata, which are simple models for programmable devices. The authors show how a tiny machine with just three pebbles can mimic any basic computer that reads input letters. They also find that figuring out if an even smaller two-pebble machine can tell apart two specific words is a very hard problem, as difficult as some known tough puzzles in mathematics. Finally, they explain how hard it is to separate strings using small machines, linking this difficulty to big open questions in computer science.
What this means in practice
- •For automata theory designers: Designers of small computing models can use hardness results to avoid infeasible verification tasks in minimal programmable machines.
- •For formal language engineers: Formal language tool builders can understand limits on optimizing smallest automata separating given strings to improve string pattern analysis tools.
A theory result. No direct application yet.
Authors
J. Andres Montoya
Abstract
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 deterministic finite automaton (DFA) on a given input word, establishing a link between pebble automata capabilities, Kolmogorov complexity, and automatic complexity. Next, we restrict our architectural framework to two-pebble programmable machines U(2,N) simulating DFAs with at most N states. We analyze the decision problem ANAL(U(2,5)), which asks whether a five-state program can separate two distinct finite words. By establishing a polynomial-time reduction from the quasi-identity checking problem for finite semigroups, we prove that ANAL(U(2,5)) is NP-complete. Finally, we explore the complexity of separating binary strings under the Exponential Time Hypothesis (ETH), showing how computational hardness implies polynomial lower bounds for the size of the smallest DFAs separating binary strings.