理论计算机科学中的几个问题

理论计算机科学中的几个问题第一页，共四十五页，2022年，8月28日EATCS(欧洲理论计算机科学协会)：主办杂志：TheoreticalComputerScience主办会议：ICALP(InternationalColloquimonAutomata,Languages,andProgramming)

第二页，共四十五页，2022年，8月28日“TheoreticalComputerScienceismathematicalandabstractinspirit,butitderivesitsmotivationsfrompracticalandeverydaycomputation.Itsaimistounderstandthenatureofcomputationand,asaconsequenceofthisunderstanding,providemoreefficientmethodologies.”第三页，共四十五页，2022年，8月28日SectionA:Algorithms,automata,complexityandgamesSectionB:Logic,semanticsandtheoryofprogrammingSectionC:Naturalcomputing(evolutionarycomputing,neuralnetwork,molecularcomputring,quantumcomputing,…)第四页，共四十五页，2022年，8月28日美国的理论计算机科学：ACMSTOC,IEEEFOCS算法与复杂性，人工智能理论（如LogicalAI）第五页，共四十五页，2022年，8月28日欧洲的理论计算机科学：形式化方法，形式语义学，…第六页，共四十五页，2022年，8月28日我国在理论计算机科学（包括美式、欧式）方面有许多非常出色的工作如何进一步发展我国的理论计算机科学？第七页，共四十五页，2022年，8月28日P.R.Halmos:“问题是数学的心脏”推而广之：“问题是一切（纯）科学的心脏”发展理论计算机科学，我们需要好的问题！第八页，共四十五页，2022年，8月28日波兰（华沙、里沃夫）数学学派的启示：有自己特色的、根本性的问题有与国际上同类工作相同的深度第九页，共四十五页，2022年，8月28日问题1：可否建立基于量子逻辑（或其它非经典逻辑）的计算理论？是否需要建立这样的理论？第十页，共四十五页，2022年，8月28日Anaxiomatizationofamathematicaltheoryconsistsofasystemoffundamentalnotionsaswellasasetofaxiomsaboutthesenotions第十一页，共四十五页，2022年，8月28日Amathematicaltheoryisthenthesetoftheoremswhichcanbederivedfromtheaxioms第十二页，共四十五页，2022年，8月28日Oneneedsacertainlogictoprovidetoolsforreasoninginthederivationofthesetheoremsfromtheaxioms第十三页，共四十五页，2022年，8月28日A.Heyting(1963),AxiomaticProjectiveGeometry,North-Holland,Amsterdam,1963Inelementaryaxiomaticslogicwasusedinanunanalyzedform第十四页，共四十五页，2022年，8月28日Thestudiesforfoundationsofmathematicsbeginningintheearlyoftwentiethcentury:Ithadbeenrealizedthatamajorpartofmathematicshastoexploitthefullpowerofclassical(Boolean)logic,thestrongestoneinthefamilyofexistinglogics第十五页，共四十五页，2022年，8月28日Afewmathematicianstooksomekindofconstructivepositionwhichisinmoreorlessexplicitoppositiontocertainformsofmathematicalreasoningusedbythemajorityofthemathematicalcommunity:L.E.J.Brouwer,H.Poincare,L.Kronecker,H.Weyl第十六页，共四十五页，2022年，8月28日Someofthemevenendeavoredtoestablishso-calledconstructivemathematics,thepartofmathematicsthatcouldberebuiltonconstructivistprinciplesThelogicemployedinthedevelopmentofconstructivemathematicsisintuitionisticlogicwhichisweakerthanclassicallogic第十七页，共四十五页，2022年，8月28日20世纪逻辑学家创造了许多不同于经典（Boolean）逻辑与直觉主义逻辑的非经典逻辑逻辑学家的问题:

是否可能建立基于除直觉主义逻辑之外的非经典逻辑的数学理论？第十八页，共四十五页，2022年，8月28日J.B.RosserandA.R.Turquette,Many-ValuedLogics,North-Holland,Amsterdam,1952“ThefactthatitisthuspossibletogeneralizeTheordinarytwo-valuedlogicsoasnotonlytocoverthecaseofmany-valuedstatementcalculi,butofmany-valuedquantificationtheoryaswell,naturallysuggeststhepossibilityoffurtherextendingourtreatmentofmany-valuedlogictocoverthecaseofmany-valuedsets,equality,numbers,etc.第十九页，共四十五页，2022年，8月28日Sincewenowhaveageneraltheoryofmanyvaluedpredicatecalculi,thereislittledoubtaboutthepossibilityofsuccessfullydevelopingsuchextendedmany-valuedtheories....weshallconsidertheircarefulstudyoneofthemajorunsolvedproblemsofmany-valuedlogic.”第二十页，共四十五页，2022年，8月28日A.Mostowski,ThirtyYearsofFoundationalStudies

ActaPhilosophicaFennica,1965J.Lukasiewicz(1920’s)hopedthattherewouldbesomenon-classicallogicswhichcanbeproperlyusedinmathematicsasnon-EuclideangeometrydoesMostofnon-classicallogicsinventedsofarhavenotbeenreallyusedinmathematics,andintuitionisticlogicseemsthatuniqueoneofnon-classicallogicswhichstillhasanopportunitytocarryouttheLukasiewicz'sproject第二十一页，共四十五页，2022年，8月28日J.Dieudonne,Thecurrenttrendofpuremathematics,

AdvancesinMathematics27(1978)235-255Mathematicallogicianshavebeendevelopingavarietyofnon-classicallogicssuchassecond-orderlogic,modallogicandmany-valuedlogic,buttheselogicsarecompletelyuselessformathematiciansworkinginotherresearchareas第二十二页，共四十五页，2022年，8月28日计算理论也是基于经典（Boolean）逻辑的数学理论（理论）计算机科学家的问题：是否需要建立基于非经典逻辑的计算理论？第二十三页，共四十五页，2022年，8月28日量子计算的主要研究方向:1.物理实现2.物理模型3.数学模型4.算法与复杂性第二十四页，共四十五页，2022年，8月28日问题:

量子计算的逻辑基础何在?第二十五页，共四十五页，2022年，8月28日G.BirkhoffandJ.vonNeumann,Thelogicofquantummechanics,AnnalsofMathematics,37(1936)823-843“whatlogicalstructureonemayhopetofindinphysicaltheorieswhich,likequantummechanics,donotconformtoclassicallogic.第二十六页，共四十五页，2022年，8月28日Ourmainconclusion,…,isthatonecanreasonablyexpecttofindacalculusofpropositionswhichisformallyindistinguishablefromthecalculusoflinearsubspaces[ofHilbertspace]withrespecttosetproducts,linearsums,andorthogonalcomplements–andresemblestheusualcalculusofpropositionswithrespectto'and','or',and'not'.”第二十七页，共四十五页，2022年，8月28日Sasaki定理(1957):

(1)ThesetofallclosedsubspacesofaHilbertspacewiththeinclusionrelationisacompleteorthomodularlattice;(2)ItisamodularlatticeifandonlyiftheHilbertspaceisfinite-dimensional第二十八页，共四十五页，2022年，8月28日量子逻辑:

（1）Thetheoryoforthomodularlattices（2）Alogicwhosesetoftruthvaluesisanorthomodularlattice第二十九页，共四十五页，2022年，8月28日量子逻辑已经存在！（真正的）问题：

能否建立基于量子逻辑的计算理论？第三十页，共四十五页，2022年，8月28日问题2：何为计算智能？什么是计算可实现的智能？注：这里“计算智能”指的不是作为“神经网络、Fuzzy逻辑、进化计算”等的总称第三十一页，共四十五页，2022年，8月28日智能是什么?我们没有好的答案！第三十二页，共四十五页，2022年，8月28日（可）计算理论回答的问题：什么是计算？信息论回答的问题：什么是信息？第三十三页，共四十五页，2022年，8月28日什么是智能？我们有（盲人摸象式的）答案：计算是智能，推理是智能，…第三十四页，共四十五页，2022年，8月28日比较一本标准的人工智能教科书与一本标准的数学教科书：N.J.Nilsson,ArtificialIntelligence,MorganKaufmann,1998J.L.Kelley,GeneralTopology,vanNostrand,1955第三十五页，共四十五页，2022年，8月28日Nilsson书的目录：ReactivemachinesSearchinstatespacesKnowledgerepresentationandreasoningPlanningmethodsbasedonlogicCommunicationandintegration第三十六页，共四十五页，2022年，8月28日Kelley书的目录：TopologicalspacesMoore-SmithconvergenceProductspacesandquotientspacesEmbeddingandmetrizationCompactspacesUniformspacesFunctionspaces第三十七页，共四十五页，2022年，8月28日TheNagata-SmirnovMetrizationTheorem:Atopologicalspaceismetrizableifandonlyifitisregularandhasasigma-locallyfinitebase.回答的问题：拓扑空间什么时候是可度量化的？第三十八页，共四十五页，2022年，8月28日S.L.Andresen,JohnMcCarthy:fatherofAI,IEEEIntelligentSystems,17:5(2002)84-85.IfJohnMcCarthy,thefatherofAIweretocoinanewphrasefor“artificialinte