Recursive presentation of a structure

A recursive presentation identifies the domain of a countable structure with a computable set, with its basic operations given by total computable functions and its basic relations decidable. In a fixed finite signature this makes evaluation of atomic formulas effective. A countable structure may have a recursive presentation of a structure only for some choices of presentation, or none at all.

A computable isomorphism is an isomorphism between presented structures whose underlying map is a total computable function. For presentations on $\mathbb{N}$, its inverse is computable too: enumerate inputs until the required output occurs. Two abstractly isomorphic structures with a recursive presentation of a structure need not admit a computable isomorphism between the chosen presentations.