文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Centre for Discrete Mathematics and Theoretical Computer Science Mathematical Proofs at a C
侵权投诉

Centre for Discrete Mathematics and Theoretical Computer Science Mathematical Proofs at a C

Abstract. For more than 2000 years, from Pythagoras and Euclid to Hilbert and Bourbaki, mathematical proofs were essentially based on axiomatic-deductive reasoning. In the last decades, the increasing length and complexity of many mathematical proofs led t

expertsthattheproofworksinprincipleseemstobeeasierthanmakingsurethattheprogramreallyworks.AdemonstrationthatthereexistsawaytocompileTEXisnotenough!HenceKnuth’swarning:“Bewareofbugsintheabovecode:Ihaveonlyproveditcorrect,nottriedit.”

Itisjustthemomenttoask,togetherwithR.Graham:“Ifnohumanbeingcaneverhopetocheckaproof,isitreallyaproof?”Continuingthisquestion,wemayask:Whataboutthefateofamathematicaltheoremwhoseunderstandingisinthehandsofonlyafewpersons?Letusobservethatinbothcasesdiscussedabove(4CPandtheclassi cationtheorem)itisnotonlytheglobal,holisticunderstandingunderquestion,butalsoitslocalvalidity.

Anotherexampleofhumilitysomeeminentmathematiciansareforcedtoadoptwithrespecttoyesterday’shighexigencyofrigorwasgivenrecentlybyoneofthemostprestigiousmathematicaljournals,situatedforalongtimeatthetopofmathematicalcreativity:AnnalsofMathematics.WelearnfromKarlSigmund[35]thattheproofproposedbyThomasHalesinAugust1998andthecorrespondingjointpaperbyHalesandFergusoncon rmingKepler’sconjectureaboutthedensestpossiblepackingofunitspheresintoacontainer,wasacceptedforpublicationintheAnnalsofMathematics,

butwithanintroductoryremarkbytheeditors,adisclaimerasitwere,statingthattheyhadbeenunabletoverifythecorrectnessofthe250-pagemanuscriptwithabsolutecertainty.

Theproofissolongandbasedtosuchanextentonmassivecomputations,thattheplatoonofmathematicianschargedwiththetaskofcheckingitranoutofsteam.RobertMacPherson,theAnnals’editorinchargeoftheproject,statedthat“therefereesputalevelofenergyintothisthatis,inmyexperience,un-precedented.Buttheyendedupbeingonly99percentcertainthattheproofwascorrect”.However,notonlythereferees,theauthorhimself,ThomasHales,‘wasexhausted’,asSigmundobserves.Hewasadvisedtore-writethemanuscript:hedidn’t,butinsteadhestartedanotherproject,‘FormalProofofKepler’(FPK),aprojectwhichputstheorem-veri cationonequalfootingwithKnuth’sprogram-veri cation.Programmingamachinetocheckhumanreasoninggivesanewtypeofinsightwhichhasitsownkindofbeauty.Hereisthebitter-ironicalcommentbySigmund:

Aftercomputer-basedtheorem-proving,thisisthenextgreatleapforward:computer-basedproofchecking.Pushedtothelimit,thiswouldseemtoentailaself-referentialloop.Maybethepuristswhoinsistthataproofisaproofiftheycanunderstanditarerightafterall.Ontheotherhand,computer-basedrefereeingissuchapromisingconcept,forreviewers,editors,andauthorsalike,thatitseemsunthinkablethatthecommunitywillnotsuccumbtothetemptation.

So,whatistheperspective?ItappearsthatFPKwillrequire20man-yearstocheckeverysinglestepofHales’proof.“Ifallgoeswell,wethencanbe100percentcertain”,concludesSigmund([35],p.67).

上一页第10页

你可能喜欢

热门文档

相关文档

  • 2010年度SCI分区(大类)

    -SERIES B DISCRETE EVENT DYNAMIC SYSTEMS-THEORY AND APPLICATIONS DISCRETE MATHEMATICS DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE Documenta Mathematica? ...

  • Incompleteness, Complexity, Randomness and Beyond_...

    Centre for Discrete Mathematics and Theoretical Computer Science Incompleteness, ...In their monumental Principia Mathematica (1925-1927), Whitehead and Russell ...

  • Is Incompleteness A Serious Problem

    G. J. Chaitin IBM Research, Yorktown Heights, USA CDMTCS-281 July 2006 Centre for Discrete Mathematics and Theoretical Computer Science Is Incompleteness A...

  • 2006 SCI 影响因子

    MATHEMATICA ACTA MATHEMATICA HUNGARICA ACTA MATHEMATICA SCIENTIA ACTA MATHEMATICA ...DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE DOKLADY MATHEMATICS DUKE ...

  • JCR分区(2011年版)

    软件工程 DISCRETE MATH DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE ...J 0018-2079 数学 HIST MATH HISTORIA MATHEMATICA 0315-0860 数学 HOMOL ...

  • for the assignment problem. In XIII Brazilian Opera...

    DIMACS workshop on parallel processing of discrete optimization problems. Technical Report 94-20, Center for Discrete Mathematics and Theoretical Computer Science...

  • 数学类SCI

    discrete mathematics and theoretical computer science 1365-8050 0 0 0 1.061 0.421 32 参考 MEDITERR J MATH mediterranean journal of mathematics 1660-5446 ...

  • 2011年_软件_物联网的关键理论与技术专题内容

    Dimacs Series in Discrete Mathematics and Theoretical Computer Science, 1999:39-70. [3] VITTER J S. Random sampling with a reservoir[J].ACM Trans on ...

  • 2010-SCI收录

    2010-SCI 2011-04-07 23:15 Acta Mathematica Annals of Mathematics Annals ...(离散数学) Discrete Mathematics and Theoretical Computer Science(离散) ...

  • 怎样投稿和处理投稿过程中出现的问题

    Discrete Applied Mathematics (emphasizes algorithms and applications) 1 Discrete Mathematics and Theoretical Computer Science Electronic Journal of Combinatorics Europ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email