Comparing the Effective Content of Subshifts

Abstract

Motivated by Ziegler's computability-theoretic characterisation of finite absolute presentability between groups, we prove an analogous theorem in symbolic dynamics. We introduce the notion of one subshift being finitely determined over another and show that this relation is characterised by Ziegler reducibility between their co-languages. We further investigate a notion of existential closure for subshifts.

Accepted to Computability in Europe 2026; 16 pages