3
$\begingroup$

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?

$\endgroup$

1 Answer 1

7
$\begingroup$

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. We don't need an oracle for a predicate that we can already compute quickly, and so these oracles will not offer dramatic improvements to our computational power. Having an undecidable or infeasible predicate, on the other hand, can offer a genuine computational advantage.

$\endgroup$
5
  • $\begingroup$ I don't really see how this answers the question of "would [H-machines] help us solve any open conjectures in number-theory, such as the twin-prime conjecture?" In theory, faster computers could of course help humanity prove or disprove all sorts of conjectures. These particular oracles (giving digits of various mathematical constants) don't seem that useful, but who knows? $\endgroup$ Commented Mar 30 at 21:46
  • 1
    $\begingroup$ @SamHopkins I argued that if one has a polytime oracle, then the speedup is at best polytime—we don't need an oracle for a property we can already compute easily—and so the speed up is negligible. Doesn't this directly address the question? Of course, having a noncomputable oracle or even a nonfeasible oracle will enable useful speedup in computation. $\endgroup$ Commented Mar 31 at 12:18
  • $\begingroup$ I see. I guess I was just thrown off by your last sentence ("In the sense of computability theory, as opposed to complexity theory, this is a neglible improvement") which seemed to suggest that computability theory was the most relevant issue where, when I think the complexity theory aspect is pretty relevant to the actual human practice of mathematics research. $\endgroup$ Commented Mar 31 at 12:24
  • $\begingroup$ Yes, I guess I view it a little differently now. I'll edit. $\endgroup$ Commented Mar 31 at 12:32
  • 1
    $\begingroup$ I have edited . $\endgroup$ Commented Mar 31 at 12:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .