show/hide this revision's text 3 edited tags
show/hide this revision's text 2 edited title

Using undecidability to answer Can the twin primes conjectureprime problem be solved with a single use of a halting oracle?

show/hide this revision's text 1

Using undecidability to answer the twin primes conjecture

It 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