Sign In

Communications of the ACM

ACM News

How Close Are Computers to Automating Mathematical Reasoning?

View as: Print Mobile App Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
Racing to find a mathematical proof.

Computers are useful for big calculations, but proofs require something different. Conjectures arise from inductive reasoning, while proofs generally follow deductive, step-by-step logic.

Credit: Maria Nguyen/Quanta Magazine

in the 1970s, the late mathematician Paul Cohen, the only person to ever win a Fields Medal for work in mathematical logic, reportedly made a sweeping prediction that continues to excite and irritate mathematicians — that "at some unspecified future time, mathematicians would be replaced by computers." Cohen, legendary for his daring methods in set theory, predicted that all of mathematics could be automated, including the writing of proofs.

A proof is a step-by-step logical argument that verifies the truth of a conjecture, or a mathematical proposition. (Once it's proved, a conjecture becomes a theorem.) It both establishes the validity of a statement and explains why it's true. A proof is strange, though. It's abstract and untethered to material experience. "They're this crazy contact between an imaginary, nonphysical world and biologically evolved creatures," said the cognitive scientist Simon DeDeo of Carnegie Mellon University, who studies mathematical certainty by analyzing the structure of proofs. "We did not evolve to do this."

Computers are useful for big calculations, but proofs require something different. Conjectures arise from inductive reasoning — a kind of intuition about an interesting problem — and proofs generally follow deductive, step-by-step logic. They often require complicated creative thinking as well as the more laborious work of filling in the gaps, and machines can't achieve this combination.

Computerized theorem provers can be broken down into two categories. Automated theorem provers, or ATPs, typically use brute-force methods to crunch through big calculations. Interactive theorem provers, or ITPs, act as proof assistants that can verify the accuracy of an argument and check existing proofs for errors. But these two strategies, even when combined (as is the case with newer theorem provers), don't add up to automated reasoning.

Plus, the tools haven't been met with open arms, and the majority of mathematicians don't use or welcome them. "They're very controversial for mathematicians," DeDeo said. "Most of them don't like the idea."


From Quanta Magazine
View Full Article



No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
ACM Resources