Timeline for Computability of prime difference function
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 17, 2020 at 15:05 | comment | added | Noah Schweber | 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. | |
| Jan 17, 2020 at 15:03 | comment | added | Noah Schweber | @Vincent The mere knowledge that something is computable doesn't usually give us much concrete information. E.g. let $X=\{n:$ ($n=0$ and P$\not=$NP) or ($n=1$ and P$=$NP)$\}$. Trivially $X$ is computable, but we don't know what algorithm computes $X$. | |
| Jan 17, 2020 at 14:19 | comment | added | Vincent | @NoahSchweber Can you clarify the issue in your last comment for me? I would expect that if the twin prime conjecture is undecidable then we have no way of computing the value of $f(2)$ for if we had, then we could just do the computation and hence decide the twin prime conjecture. Where do I go wrong? | |
| Oct 26, 2017 at 14:55 | vote | accept | Dominic van der Zypen | ||
| Sep 22, 2015 at 15:37 | comment | added | Noah Schweber | @JoelDavidHamkins Sorry, that was my bad, you're absolutely right. I was unclear - I should have said "there is no obvious direct relationship." I was just getting at the confusion between "an atomic fact about the function is undecidable in a specific system" and "the function is not computable", which is a subtle issue (at least, it tripped me up when I was learning this). | |
| Sep 22, 2015 at 15:33 | comment | added | Joel David Hamkins | @NoahSchweber, how can you assert such a definitive statement about what is possible? It seems to me that we don't really know anything about it with certainty. | |
| Sep 22, 2015 at 14:32 | comment | added | Noah Schweber | @DominicvanderZypen There's no direct relationship - the function could be computable even if the twin prime conjecture fails, or is undecidable. | |
| Sep 22, 2015 at 14:00 | comment | added | Dominic van der Zypen | @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... | |
| Sep 22, 2015 at 13:19 | comment | added | Jeppe Stig Nielsen | If we just require the existence of one difference $p-q=n$, we need only run up to $q=1117$ to verify that all even $n$ not exceeding $7\cdot 10^7$ admit such a representation. However, if we require (like in the question), arbitrarily large $q$ values for each single $n$, then no explicit $n$ is known to belong to $f^{-1}( \{ 1 \} )$, but Zhang's recent result shows that at least one such $n$ exists below $7 \cdot 10^7$. | |
| Sep 22, 2015 at 11:43 | comment | added | Joel David Hamkins | Dominic, I'm not sure that this is actually the answer to your question. | |
| Sep 22, 2015 at 11:22 | vote | accept | Dominic van der Zypen | ||
| Sep 22, 2015 at 13:58 | |||||
| Sep 22, 2015 at 10:58 | comment | added | Joel David Hamkins | He didn't mention a reason, except that of course the question is not yet settled. | |
| Sep 22, 2015 at 10:55 | comment | added | Stefan Kohl♦ | 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. | |
| Sep 22, 2015 at 10:55 | comment | added | Joel David Hamkins | I don't know how to prove that. | |
| Sep 22, 2015 at 10:51 | comment | added | Dominic van der Zypen | Am I right in assuming that the following implication holds? If the twin prime conjecture is undecidable, then $f:\omega\to\{0,1\}$ as described above is non-computable. | |
| Sep 22, 2015 at 10:45 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |