|
3 |
edited tags
|
||
|
2 |
edited title
|
||
Using undecidability to answer Can the twin primes conjectureprime problem be solved with a single use of a halting oracle? |
||||
|
1 |
|
||
Using undecidability to answer the twin primes conjectureIt occurred to me that if it were possible to determine whether a given program halts, that could be used to answer the twin primes conjecture A) Write a program which takes input n and then counts upward until it's found n pairs of twin primes B) Write a program which for any input n returns true if A halts and false otherwise C) Write a program which counts upward running B on every n until B returns false D) If C halts, there are finitely many twin primes, otherwise infinite. I was wondering if there was a way to do this without nesting halting problems... ie if you only get one chance to ask whether a program halts, is that sufficient to answer the twin primes conjecture
|
||||

