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 o
f 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 Harringtons result that counterexamples to Vaughts 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.
We prove that, for every theory $T$ which is given by an ${mathcal L}_{omega_1,omega}$ sentence, $T$ has less than $2^{aleph_0}$ many countable models if and only if we have that, for every $Xin 2^omega$ on a cone of Turing degrees, every $X$-hyperar
ithmetic model of $T$ has an $X$-computable copy. We also find a concrete description, relative to some oracle, of the Turing-degree spectra of all the models of a counterexample to Vaughts conjecture.
We prove that there is a structure, indeed a linear ordering, whose degree spectrum is the set of all non-hyperarithmetic degrees. We also show that degree spectra can distinguish measure from category.
Assuming that $0^#$ exists, we prove that there is a structure that can effectively interpret its own jump. In particular, we get a structure $mathcal A$ such that [ Sp({mathcal A}) = {{bf x}:{bf x}in Sp ({mathcal A})}, ] where $Sp ({mathcal A})$ is
the set of Turing degrees which compute a copy of $mathcal A$. It turns out that, more interesting than the result itself, is its unexpected complexity. We prove that higher-order arithmetic, which is the union of full $n$th-order arithmetic for all $n$, cannot prove the existence of such a structure.
We show that for every K-trivial real X, there is no representation of a continuous probability measure m such that X is 1-random relative to m.
