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.

@inproceedings{Jeandel17,
  title = {Enumeration reducibility in closure spaces with applications to logic and algebra},
  author = {Emmanuel Jeandel},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005086}
}