I'd say $\mathbb{Q}$ is level 2, as a $\Sigma^{0}_{2}$ set.

StackOverflow thread: stackoverflow.com/questions/1224491/…

Any irrational number will do, some can be "computed" very fast, like 0.01001000100001...

en.wikipedia.org/wiki/Rado_graph?

Most probably you are right. No points for me. (but, to nitpick, the reduction is from the halting problem, not to it) It's obvious that in any possible proof one has to use computability theory and show that the function is not equal to any of the computable ones. Diagonalization is the most natural way to do it. When this constitutes a "self-reference", it's hard to specify.

Available online: uob-community.ballarat.edu.au/~smorris/topology.htm

See also: en.wikipedia.org/wiki/Polynomial_hierarchy

Very good references. I think you can post using hyperlinks now.