Ramsey's theorem and computability theory
An infinite version of Ramsey's theorem states that for every coloring
of
$[\omega]^n$ (the set of all $n$--element subsets of $\omega$) by finitely
many colors, there is an infinite set $A$ which is homogeneous for
that
coloring, i.e., all elements of $[A]^n$ have the same color. After
an
introduction to the necessary background in computability theory, we
present a survey of results concerning the complexity of infinite
homogeneous sets for effectively given (computable or computably
enumerable) colorings.