理論計算機科學(xué)中的幾個問題第一頁，共四十五頁，編輯于2023年，星期一EATCS(歐洲理論計算機科學(xué)協(xié)會)：主辦雜志：TheoreticalComputerScience主辦會議：ICALP(InternationalColloquimonAutomata,Languages,andProgramming)

第二頁，共四十五頁，編輯于2023年，星期一“TheoreticalComputerScienceismathematicalandabstractinspirit,butitderivesitsmotivationsfrompracticalandeverydaycomputation.Itsaimistounderstandthenatureofcomputationand,asaconsequenceofthisunderstanding,providemoreefficientmethodologies.”第三頁，共四十五頁，編輯于2023年，星期一SectionA:Algorithms,automata,complexityandgamesSectionB:Logic,semanticsandtheoryofprogrammingSectionC:Naturalcomputing(evolutionarycomputing,neuralnetwork,molecularcomputring,quantumcomputing,…)第四頁，共四十五頁，編輯于2023年，星期一美國的理論計算機科學(xué)：ACMSTOC,IEEEFOCS算法與復(fù)雜性，人工智能理論（如LogicalAI）第五頁，共四十五頁，編輯于2023年，星期一歐洲的理論計算機科學(xué)：形式化方法，形式語義學(xué)，…第六頁，共四十五頁，編輯于2023年，星期一我國在理論計算機科學(xué)（包括美式、歐式）方面有許多非常出色的工作如何進一步發(fā)展我國的理論計算機科學(xué)？第七頁，共四十五頁，編輯于2023年，星期一P.R.Halmos:“問題是數(shù)學(xué)的心臟”推而廣之：“問題是一切（純）科學(xué)的心臟”發(fā)展理論計算機科學(xué)，我們需要好的問題！第八頁，共四十五頁，編輯于2023年，星期一波蘭（華沙、里沃夫）數(shù)學(xué)學(xué)派的啟示：有自己特色的、根本性的問題有與國際上同類工作相同的深度第九頁，共四十五頁，編輯于2023年，星期一問題1：可否建立基于量子邏輯（或其它非經(jīng)典邏輯）的計算理論？是否需要建立這樣的理論？第十頁，共四十五頁，編輯于2023年，星期一Anaxiomatizationofamathematicaltheoryconsistsofasystemoffundamentalnotionsaswellasasetofaxiomsaboutthesenotions第十一頁，共四十五頁，編輯于2023年，星期一Amathematicaltheoryisthenthesetoftheoremswhichcanbederivedfromtheaxioms第十二頁，共四十五頁，編輯于2023年，星期一Oneneedsacertainlogictoprovidetoolsforreasoninginthederivationofthesetheoremsfromtheaxioms第十三頁，共四十五頁，編輯于2023年，星期一A.Heyting(1963),AxiomaticProjectiveGeometry,North-Holland,Amsterdam,1963Inelementaryaxiomaticslogicwasusedinanunanalyzedform第十四頁，共四十五頁，編輯于2023年，星期一Thestudiesforfoundationsofmathematicsbeginningintheearlyoftwentiethcentury:Ithadbeenrealizedthatamajorpartofmathematicshastoexploitthefullpowerofclassical(Boolean)logic,thestrongestoneinthefamilyofexistinglogics第十五頁，共四十五頁，編輯于2023年，星期一Afewmathematicianstooksomekindofconstructivepositionwhichisinmoreorlessexplicitoppositiontocertainformsofmathematicalreasoningusedbythemajorityofthemathematicalcommunity:L.E.J.Brouwer,H.Poincare,L.Kronecker,H.Weyl第十六頁，共四十五頁，編輯于2023年，星期一Someofthemevenendeavoredtoestablishso-calledconstructivemathematics,thepartofmathematicsthatcouldberebuiltonconstructivistprinciplesThelogicemployedinthedevelopmentofconstructivemathematicsisintuitionisticlogicwhichisweakerthanclassicallogic第十七頁，共四十五頁，編輯于2023年，星期一20世紀(jì)邏輯學(xué)家創(chuàng)造了許多不同于經(jīng)典（Boolean）邏輯與直覺主義邏輯的非經(jīng)典邏輯邏輯學(xué)家的問題:

是否可能建立基于除直覺主義邏輯之外的非經(jīng)典邏輯的數(shù)學(xué)理論？第十八頁，共四十五頁，編輯于2023年，星期一J.B.RosserandA.R.Turquette,Many-ValuedLogics,North-Holland,Amsterdam,1952“ThefactthatitisthuspossibletogeneralizeTheordinarytwo-valuedlogicsoasnotonlytocoverthecaseofmany-valuedstatementcalculi,butofmany-valuedquantificationtheoryaswell,naturallysuggeststhepossibilityoffurtherextendingourtreatmentofmany-valuedlogictocoverthecaseofmany-valuedsets,equality,numbers,etc.第十九頁，共四十五頁，編輯于2023年，星期一Sincewenowhaveageneraltheoryofmanyvaluedpredicatecalculi,thereislittledoubtaboutthepossibilityofsuccessfullydevelopingsuchextendedmany-valuedtheories....weshallconsidertheircarefulstudyoneofthemajorunsolvedproblemsofmany-valuedlogic.”第二十頁，共四十五頁，編輯于2023年，星期一A.Mostowski,ThirtyYearsofFoundationalStudies

ActaPhilosophicaFennica,1965J.Lukasiewicz(1920’s)hopedthattherewouldbesomenon-classicallogicswhichcanbeproperlyusedinmathematicsasnon-EuclideangeometrydoesMostofnon-classicallogicsinventedsofarhavenotbeenreallyusedinmathematics,andintuitionisticlogicseemsthatuniqueoneofnon-classicallogicswhichstillhasanopportunitytocarryouttheLukasiewicz'sproject第二十一頁，共四十五頁，編輯于2023年，星期一J.Dieudonne,Thecurrenttrendofpuremathematics,

AdvancesinMathematics27(1978)235-255Mathematicallogicianshavebeendevelopingavarietyofnon-classicallogicssuchassecond-orderlogic,modallogicandmany-valuedlogic,buttheselogicsarecompletelyuselessformathematiciansworkinginotherresearchareas第二十二頁，共四十五頁，編輯于2023年，星期一計算理論也是基于經(jīng)典（Boolean）邏輯的數(shù)學(xué)理論（理論）計算機科學(xué)家的問題：是否需要建立基于非經(jīng)典邏輯的計算理論？第二十三頁，共四十五頁，編輯于2023年，星期一量子計算的主要研究方向:1.物理實現(xiàn)2.物理模型3.數(shù)學(xué)模型4.算法與復(fù)雜性第二十四頁，共四十五頁，編輯于2023年，星期一問題:

量子計算的邏輯基礎(chǔ)何在?第二十五頁，共四十五頁，編輯于2023年，星期一G.BirkhoffandJ.vonNeumann,Thelogicofquantummechanics,AnnalsofMathematics,37(1936)823-843“whatlogicalstructureonemayhopetofindinphysicaltheorieswhich,likequantummechanics,donotconformtoclassicallogic.第二十六頁，共四十五頁，編輯于2023年，星期一Ourmainconclusion,…,isthatonecanreasonablyexpecttofindacalculusofpropositionswhichisformallyindistinguishablefromthecalculusoflinearsubspaces[ofHilbertspace]withrespecttosetproducts,linearsums,andorthogonalcomplements–andresemblestheusualcalculusofpropositionswithrespectto'and','or',and'not'.”第二十七頁，共四十五頁，編輯于2023年，星期一Sasaki定理(1957):

(1)ThesetofallclosedsubspacesofaHilbertspacewiththeinclusionrelationisacompleteorthomodularlattice;(2)ItisamodularlatticeifandonlyiftheHilbertspaceisfinite-dimensional第二十八頁，共四十五頁，編輯于2023年，星期一量子邏輯:

（1）Thetheoryoforthomodularlattices（2）Alogicwhosesetoftruthvaluesisanorthomodularlattice第二十九頁，共四十五頁，編輯于2023年，星期一量子邏輯已經(jīng)存在?。ㄕ嬲模﹩栴}：

能否建立基于量子邏輯的計算理論？第三十頁，共四十五頁，編輯于2023年，星期一問題2：何為計算智能？什么是計算可實現(xiàn)的智能？注：這里“計算智能”指的不是作為“神經(jīng)網(wǎng)絡(luò)、Fuzzy邏輯、進化計算”等的總稱第三十一頁，共四十五頁，編輯于2023年，星期一智能是什么?我們沒有好的答案！第三十二頁，共四十五頁，編輯于2023年，星期一（可）計算理論回答的問題：什么是計算？信息論回答的問題：什么是信息？第三十三頁，共四十五頁，編輯于2023年，星期一什么是智能？我們有（盲人摸象式的）答案：計算是智能，推理是智能，…第三十四頁，共四十五頁，編輯于2023年，星期一比較一本標(biāo)準(zhǔn)的人工智能教科書與一本標(biāo)準(zhǔn)的數(shù)學(xué)教科書：N.J.Nilsson,ArtificialIntelligence,MorganKaufmann,1998J.L.Kelley,GeneralTopology,vanNostrand,1955第三十五頁，共四十五頁，編輯于2023年，星期一Nilsson書的目錄：ReactivemachinesSearchinstatespacesKnowledgerepresentationandreasoningPlanningmethodsbasedonlogicCommunicationandintegration第三十六頁，共四十五頁，編輯于2023年，星期一Kelley書的目錄：TopologicalspacesMoore-SmithconvergenceProductspacesandquotientspacesEmbeddingandmetrizationCompactspacesUniformspacesFunctionspaces第三十七頁，共四十五頁，編輯于2023年，星期一TheNagata-SmirnovMetrizationTheorem:Atopologicalspaceismetrizableifandonlyifitisregularandhasasigma-locallyfinitebase.回答的問題：拓?fù)淇臻g什么時候是可度量化的？第三十八頁，共四十五頁，編輯于2023年，星期一S.L.Andresen,JohnMcCarthy:fatherofAI,IEEEIntelligentSystems,17:5(2002)84-85.IfJohnMcCarthy,thefatherofAIweretocoinanewphrasefor“artificialintelli