MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I call an H-machine a machine that can be connected to turing machines and that takes as input a natural integer n and instantly returns the n'th digit of the mathematical constant H.

Is there a proof/disproof/(or any kind of argument of what we should expect) that access to any combination of the e,Pi,sqrt(2),zeta(3) or euler-macheroni-machines would help us solve any open conjectures in number-theory, such as the twin-prime conjecture?

Would any other problems such as factoring large integers gain any speedup?

share|cite|improve this question
up vote 7 down vote accepted

Your $H$-machine concept is essentially the same as the concept of oracle computation, due originally to Turing, which gave rise to the elaborate theory of Turing degrees in computability theory. The idea in that subject is that a machine with oracle $B$ is allowed to make membership queries of $B$ during the course of computation, and an oracle $A$ is said to be computable relative to $B$, written $A\leq_T B$, if membership in $A$ is computable from a machine with oracle $B$.

The philosophy of the subject is that the concept of relative computability provides a measure of the relative information content of two oracles. In this way, the structure of the Turing degrees themselves can be viewed as the structure of the possible information contents of infinite sets. If $A\leq_T B$, then $B$ has at least as much information content as $A$, since any query to $A$ can be replicated via a computation involving queries to $B$. In particular, if $B$ itself is computable, then all such queries to $B$ can ultimately be simulated by a computational procedure, and so $A$ also will be computable. It follows, therefore, that minimal (trivial) Turing degree is the equivalence class consisting of all decidable sets.

In your case, the reals you mention $e$, $\pi$, $\sqrt{2}$ are decidable reals, and even polynomial time decidable, and so having them as an oracle provides at most a polynomial time speed-up in computational power. In the sense of computability theory, as opposed to complexity theory, this is a neglible improvement.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.