# How to prove there is no algorithm for a problem e.g. generating next prime?

Say I want to find the next prime directly without a test. AFAIK there is no known formula. Is it possible that since we've failed to find a formula, then we might be able to prove that there is no formula and there is no algorithm for generating next prime directly?

I'm trying to understand if there is a method for knowing whether there is a method.

-
It would be hard to formalize your question because of the restriction "without a test". – Tunococ Jan 19 '13 at 6:00
Can you make it a more precise statement, like putting the limit on the amount of memory allowed? – Tunococ Jan 19 '13 at 6:17
It might be helpful to review Prime Formulas. Regards – Amzoti Jan 19 '13 at 6:28
While I don't know about the specific problem you mention, there are of course many problems for which you can show that no algorithm running in a certain time exists, under certain computational models. – Suresh Venkat Jan 19 '13 at 7:13
The most common thing I have seen to prove undecidability is reduction from the Halting Problem. But the example is bad. Finding the next prime is solvable by simple sieving. – Tim Seguine Jan 20 '13 at 13:59

Only method is to put your problem in some class of perfectly solvable problems, and show its insolubility inside a class.

Example is application of Galois theory to prove, that equation's $x^5 + x + 1 = 0$ solution is not expressible in terms of radicals.

Other example is expressing informal notion of algorithm as a Turing machine and next prove undecidability of halting problem for any Turing machine.

Given these two results, do we have sufficient evidence to think that those two problems (analytical roots of given polynom and halting problem) are really insoluble?

May be we must regard this as evidence, that idea to solve polynomial equations in radicals needs to be replaced, and that Turing machine is too narrow abstraction?

Since we still don't know anything better, than solving equations in radicals, and we don't know any exceptions for Church–Turing thesis. That is why we are using words like "insolubility in radicals", "undecidable [if Church-Turing thesis holds] problem", etc.

If you want to do so in number theory for prime numbers, you must first create a framework for similar tasks, rich enough to comply with intuitive notions, and then show, that exact problem like "next prime number for given one" have no solution inside this framework. Or may be you will see, that it really have one...

-

In order prove or disprove anything you would need a logical progression that is correct and leaves no doubt about the claim. When it comes to primes and their progression, it would likely be harder to prove that there isn't a formula then proving that there is one since you would need to come up with something new in both cases.

-