# Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (proofs, etc.)?

I'm a student, so I apologise if this is an idiotic question: Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (posing conjectures, proofs, etc.)? Why or why not?

I have heard arguments that computers will never be able to do mathematics close to the ability of humans, and these arguments are sometimes justified with reference to P vs NP (assuming that $P \not = NP$). It is said that, since these problems are NP rather than P (?), the solutions (proofs) could either be so lengthy as to not be understandable and/or verifiable by humans, or the solutions (proofs) would take so much time that the task practically becomes impossible. Are these statements true? Why or why not?

• Well, if P=NP, we would have a polytime algorithm which, given any conjecture and a natural $n$, can find a proof of length $\leq n$ if there's one. If computer hardware keeps getting more and more powerful, computers might eventually be better than humans in finding proofs.
– chi
Feb 14 '17 at 11:27

The fundamental restriction is human computer programmers' inability so far to create computers equipped with real intelligence. "Never" is a very long time, so it's hard to accept that something will "never" happen unless there is a very good argument.

Human brains and computers are not fundamentally different. The practical difference is that some human brains are programmed in a significantly better way for finding mathematical proofs, while computers have other advantages. With equally good programming, computers would probably have the advantage.

And remember that the majority of humans are also unable to do any mathematics better than current computers can.

PS: P vs. NP is a red herring. Computers are not able to generally solve NP complete problems above modest size because it is too computational intensive (but often many instances can be solved, just not all). But nor can humans. No mathematical proof that humans have found ever involved solving a hard instance of an NP-complete problem. On the other hand, there are many problems in P that are just as unsolvable.

PS. In general the problem "given a mathematical hypothesis, is there a proof for it" will be NP-hard (take any instance of an NP-complete problem, and declare that "answer is YES" is a mathematical hypothesis). The question "is there a proof for Fermat's Last Theorem" is obviously an easy instance of that problem :-) Since it took humans 357 years to prove, we can take bets if computers will manage quicker.

• I am not sure that this is correct. I mean, as far as I know, we do not exactly know how our brain find proves on a "computational level". It is reasonable to assume that it works algorithmical since this is a concept, which human brains developed, but maybe there is some other stuff going on. Feb 14 '17 at 13:45

It depends what you mean by "doing mathematics". If you mean large scale computation, computers can easily do this, as can be seen from programs like Wolfram Alpha. Engines like these are obviously not perfect, but given the rate of development in machine intelligence, I don't think we have reason to believe this is a cause for limitation.

If by "doing mathematics" you mean applying deductive reasoning to given axioms, or formulating proofs, there are in fact computer generated proofs. It is even a big controversy whether the mathematical community should accept such proofs as valid, because they are often far to large for any human to check. Of course this is very new, and there is also much room for improvement. But again, no inherent limitations here.

One of the only limitations unrelated to human ability I can think of would be limitations inherent to mathematics, particularly Gödel's incompleteness theorems. Every set of axioms containing basic arithmetic is either inconsistent or incomplete. The Halting Problem is another great example that shows computers cannot do everything.

• The validation of proofs for mathematicians is equivalent to experimental validation of hypotheses for physicists/chemist. I guess the question becomes, if we ever had a computer that could conduct any physical experiment for us and provide an unverifiable result that is presumably correct, should we accept it as valid without verification? It's certainly an interesting question. Feb 14 '17 at 15:48
• @ThePointer Indeed. On top of the factor of whether to trust technology more than the human mind, many argue that computer assisted proofs also diminish the importance of elegance. And isn't mathematics more about understanding than it is about the actual result? Feb 14 '17 at 15:55
• Absolutely. Many conjectures, despite having not been proven, have been computationally shown to have a likely result, so nearly all mathematicians already expect a certain conclusion. The value in mathematical proofs comes from the techniques used in proving the conjecture -- the elegance. Although, It may be that even this becomes possible in the future... Feb 14 '17 at 16:01
• "The validation of proofs for mathematicians is equivalent to experimental validation of hypotheses for physicists/chemist." No it isn't. An experiment can only falsify or fail to falsify a scientific hypothesis; a proof can either falsify or validate a mathematical hypothesis. And, sure, there could be a mistake in the proof but there could also be a mistake in the interpretation of the experiment. Even if you want to take a sociological view of mathematics (we want it to be absolute truth but it isn't because we're fallible), proof is not the same as experiment. Feb 14 '17 at 16:19