A Turing machine is a mathematical formalization of a computer (program). If $y\in(0,1)$, a Turing machine with [oracle][1] $y$ has access to the digits of $y$, and can used them during its computations. We say that $x\le_T y$ iff there is a machine with oracle $y$ that allows us to compute the digits of $x\in(0,1)$.

There are only countably many programs, so a simple diagonalization argument shows that there are reals $x$ and $y$ with $x{\not\le}_T y$ and $y{\not\le}_T x$. $(*)$

Being a set theorist, when I first learned of this notion, I couldn't help it but to come up with the following proof of $(*)$:

> Again by counting, every $x$ has only
> countably many $\le_T$-predecessors.
> So, if CH fails, there are
> Turing-incomparable reals. By the
> technique of forcing, we can find a
> (boolean valued) extension $V'$ of the
> universe $V$ of sets where CH fails,
> and so $(*)$ holds in this extension.
> Shoenfield's absoluteness theorem
> tells us that $\Sigma^1_2$-statements
> are absolute between (transitive)
> models with the same ordinals. The
> statement $(*)$, "there are
> Turing-incomparable reals" is
> $\Sigma^1_1$, so Shoenfield's
> absoluteness applies to it.
> Working from the point of view of $V'$ and considering $V'$ and $V$, it follows
> that $(*)$ also holds in $V$.

It turns out that Joel Hamkins also found this argument, and he used it in the context of his theory of Infinite time Turing machines, for which the simple diagonalization proof does not apply. So, at least in this case, the insane proof actually was useful at the end.

  [1]: http://en.wikipedia.org/wiki/Oracle_machine