# Generically computable structures and isomorphisms

We define notions of generically, coarsely, and densely computable relations, structures and isomorphisms. For example, a binary relation R on $\omega$ is generically computable if there is a partial computable function $\Phi: \omega \times \omega \to \{0,1\}$ such that $\Phi = \chi_R$ on the domain of $\Phi$ and there is a c.e. set of asymptotic density one such that $A \times A$ is a subset of the domain of $\Phi$; the set $A$ and the relation $R$ are said to be faithful if whenever $a \in A$ and $aRb$ then $b \in A$. It is shown that every equivalence structure has a generically computable copy. However, $E$ has a faithful generically computable copy if and only if it has an infinite faithful substructure with a computable copy. We define a notion of generically computable isomorphisms and apply this in particular to the classic structure consisting of infinitely many classes of size 1 and of size 2. We show that if the classes of size 2 have asymptotic density one in two structures A and B, then A and B are generically computably isomorphic.