  In this paper, we investigate connections between structures present in every
generic extension of the universe $V$ and computability theory. We introduce
the notion of {\em generic Muchnik reducibility} that can be used to to compare
the complexity of uncountable structures; we establish basic properties of this
reducibility, and study it in the context of {\em generic presentability}, the
existence of a copy of the structure in every extension by a given forcing. We
show that every forcing notion making $\omega_2$ countable generically presents
some countable structure with no copy in the ground model; and that every
structure generically presentble by a forcing notion that does not make
$\omega_2$ countable has a copy in the ground model. We also show that any
countable structure $\mathcal{A}$ that is generically presentable by a forcing
notion not collapsing $\omega_1$ has a countable copy in $V$, as does any
structure $\mathcal{B}$ generically Muchnik reducible to a structure
$\mathcal{A}$ of cardinality $\aleph_1$. The former positive result yields a
new proof of Harrington's result that counterexamples to Vaught's conjecture
have models of power $\aleph_1$ with Scott rank arbitrarily high below
$\omega_2$. Finally, we show that a rigid structure with copies in all generic
extensions by a given forcing has a copy already in the ground model.
