There is a lot of research on the boundary between decidability and undecidability of the halting problem for small models of computation: Turing machines, tag systems, CAs, ... This boundary is clearly linked to the (non-)universality of such models.I'm wondering if there are similar works on the logic-side:What are the smallest theories for which the boundary between  decidability and undecidability (of valid formulas) is unknown ?  Is there a survey paper on the subject ?I realize that it is not easy to formalize the notion of small theory (or simple theory), but it should include the number of axioms of the theory and the size of the signature.For example Andrzej Grzegorczyk in Undecidability without arithmetization (Studia Logica 79(2005))proved that Tarskis theory of concatenation (TC) is already undecidable; the axioms are:TC1: $x*(y*z) = (x*y)*z$TC2: $(x*y = u*v ) \to \exists w((x*w = u \land w*v = y)\lor(u*w = x \land w*y = v))$TC3: $\neg (\alpha = x*y)$TC4: $\neg (\beta = x*y)$TC5: $\neg (\alpha = \beta)$
Boundary between decidability and undecidability for small theories
reference request;lo.logic