Timeless Machines: Computability Across Eras
Description
This book constitutes the refereed proceedings of the 22nd Conference on Timeless Machines: Computability Across Eras, CiE 2026, held in Trier, Germany, during July 27-31, 2026.
The 30 full papers included in this book were carefully reviewed and selected from 57 submissions. The conference had six special sessions: Learning Theory Meets Computability Theory; Groups and Computability; At the Borderline of Universality; Natural Computation and Bioinformatics; Quantum Computing and Information; and the History and Philosophy of Computing.
Additionally the main proceedings includes 6 full papers and the front matter contains 16 abstracts that derive from the invited talks, tutorials, and special sessions.
More details
Content
.- Invited Papers.
.- The CDSAT Method for Satisfiability Modulo Theories and Assignment: an Exposition.
.- Effective second countability in computable analysis.
.- Towards a Computational Quantum Logic: An Overview of an Ongoing Research Program.
.- Represented spaces of represented spaces.
.- Computation with Real Numbers and Continuous-Time Dynamical Systems.
.- Proof-Carrying Neuro-Symbolic Code.
.- Uniform Functional Interpretations.
.- Computable Analysis for Extraction of Certified Programs and its Applications.
.- Contributed Papers.
.- The existence of primitive recursive structures.
.- Space-bounded online Kolmogorov complexity is additive.
.- On learning existentially definable subsets in a computable structure.
.- Transfinite structured programming.
.- Computability of Real Functions with Oracle Pointer Machines implies Real-Time simulation of Chemical Reaction Networks.
.- Computability of Initial Value Problems.
.- Full generalized effective reducibility.
.- On S-Degrees of some Representations of Irrational Numbers.
.- Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs.
.- Binary Expansions of Regular Reals and Reordered Computable Numbers.
.- Properties of Range Sets of Continuous Functions in Reverse Mathematics.
.- The theory of reachability of trace-pushdown systems.
.- A point to set principle for finite-state dimension and relativized equidistribution porperties.
.- Some structural complexity results for $\exists \mathbb R$.
.- On the computational power of C-random strings.
.- Generalized learnability of stochastic principles.
.- Computably discrete represented spaces.
.- Multidimensional tilings and MSO logic.
.- Injectivity of polynomials over finite discrete dynamical systems.
.- Weihrauch problems as containers.
.- On the reverse mathematics of cut-elimination and determinacy.
.- $L {\omega\omega}$, $L {\omega 1\omega}$, and Wadge hierarchy.
.- Ordinal Invariants of the $h$-Preorder on $k$-Labeled Forests.
.- Completeness theorems for modal logic in second-order arithmetic.
.- Variants of Solovay reducibility.
.- Constructive Analysis of Maximal Ideals in Z[X] by the Material Interpretation.
.- Alternation-Bounded Semi-Unbounded Fan-in Cascading Circuits and the Complementation Closure Property.