Orbit-Finite Sets
summary
Claims an equivalence between the syntactic notion definable sets (finite set‑builder expressions over a fixed atom structure) and the semantic notion orbit‑finite (finitely many orbits under atom automorphisms) for oligomorphic atom structures, proves a Church–Turing–style robustness result, and gives an operational semantics (for‑loops over infinite definable sets, aggregating by set‑union, threads must have uniformly bounded time). Implements a C library prototype (Kopczyński/Toruńczyk), shows reachability and automata nonemptiness decidable, and proves deterministic machines cannot capture all computable cases (alternation or nondeterminism needed).
AI-written summary · about