Metraipolis › archive › dc_752d38238d09

The smallest programmable machine and the hardness of analyzing it — arXiv:2610.10399

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.10399
License (as archived)
CC0-1.0
Archived
2026-10-08T12:50:00.055Z
SHA-256 of the archived text
685f08591da268e5ea5557e8010d385a3184d5f114999d5d23e44ffc72cf95ed
Stable URL of this page
https://metraipolis.com/documento/dc_752d38238d09

How to cite

The smallest programmable machine and the hardness of analyzing it — arXiv:2610.10399 — arXiv (en), https://arxiv.org/abs/2610.10399 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_752d38238d09 (Metraipolis archive dc_752d38238d09, sha256 685f08591da268e5ea5557e8010d385a3184d5f114999d5d23e44ffc72cf95ed)
BibTeX
@misc{dc752d38238d09,
  title = {The smallest programmable machine and the hardness of analyzing it — arXiv:2610.10399},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.10399},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_752d38238d09; sha256 685f08591da268e5ea5557e8010d385a3184d5f114999d5d23e44ffc72cf95ed},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.10399. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2610.10399 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:20:00.308Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).