Skip to main content
MathOverflow

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

13
  • 4
    $\begingroup$ Is there a specific reason for the assumption that the set of prime differences has a reasonable chance to be noncomputable? -- I think the basic heuristics pretty clearly suggests it's just the set of even natural numbers. $\endgroup$ Commented Sep 22, 2015 at 10:55
  • 1
    $\begingroup$ Dominic, I'm not sure that this is actually the answer to your question. $\endgroup$ Commented Sep 22, 2015 at 11:43
  • 1
    $\begingroup$ @JoelDavidHamkins - I accepted your answer because it seemed to me that the answer to my question depends on the decidability of the Twin Primes Conjecture, but now I'm confused whether that's the case... $\endgroup$ Commented Sep 22, 2015 at 14:00
  • 2
    $\begingroup$ @DominicvanderZypen There's no direct relationship - the function could be computable even if the twin prime conjecture fails, or is undecidable. $\endgroup$ Commented Sep 22, 2015 at 14:32
  • 2
    $\begingroup$ Basically, something can be "nonconstructively computable" - that is, we can have a definable set/function $X$ and a program $\Phi$ which computes $X$ but such that there is no proof in our theory that $\Phi$ (or any other specific program) computes $X$. This is a weird mix of classical and constructive flavors, but is a key feature of the subject. $\endgroup$ Commented Jan 17, 2020 at 15:05