principleMinor
Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (proofs, etc.)?
Viewed 0 times
fromsuchbeingpreventsetcreasoncomputersthatfundamentallimitation
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#70286, answer score: 5
Revisions (0)
No revisions yet.