https://hal.inria.fr/hal-01146744v3Jeandel, EmmanuelEmmanuelJeandelCARTE - Theoretical adverse computations, and safety - Inria Nancy - Grand Est - Inria - Institut National de Recherche en Informatique et en Automatique - LORIA - FM - Department of Formal Methods - LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications - Inria - Institut National de Recherche en Informatique et en Automatique - UL - Université de Lorraine - CNRS - Centre National de la Recherche ScientifiqueEnumeration Reducibility in Closure Spaces with Applications to Logic and AlgebraHAL CCSD2015universal algebra symbolic dynamics computability combinatorial group theory[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM][INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO][MATH.MATH-CT] Mathematics [math]/Category Theory [math.CT]Jeandel, Emmanuel2017-08-04 12:38:562023-03-24 14:53:052017-08-07 16:58:12enPreprints, Working Papers, ...https://hal.inria.fr/hal-01146744v3/documenthttps://hal.inria.fr/hal-01146744v2application/pdf3 In many instances in first order logic or computable algebra, classical theorems show that many problems are undecidable for general structures, but become decidable if some rigidity is imposed on the structure. For example, the set of theorems in many finitely axiomatisable theories is nonrecursive, but the set of theorems for any finitely axiomatisable complete theory is recursive. Finitely presented groups might have an nonrecursive word problem, but finitely presented simple groups have a recursive word problem. In this article we introduce a topological framework based on closure spaces to show that many of these proofs can be obtained in a similar setting. We will show in particular that these statements can be generalized to cover arbitrary structures, with no finite or recursive presentation/axiomatization. This generalizes in particular work by Kuznetsov and others. Examples from first order logic and symbolic dynamics will be discussed at length.