理論計(jì)算機(jī)科學(xué)中的幾個(gè)問題

理論計(jì)算機(jī)科學(xué)中的幾個(gè)問題第1頁，課件共45頁，創(chuàng)作于2023年2月EATCS(歐洲理論計(jì)算機(jī)科學(xué)協(xié)會(huì))：主辦雜志：TheoreticalComputerScience主辦會(huì)議：ICALP(InternationalColloquimonAutomata,Languages,andProgramming)

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

是否可能建立基于除直覺主義邏輯之外的非經(jīng)典邏輯的數(shù)學(xué)理論？第18頁，課件共45頁，創(chuàng)作于2023年2月J.B.RosserandA.R.Turquette,Many-ValuedLogics,North-Holland,Amsterdam,1952“ThefactthatitisthuspossibletogeneralizeTheordinarytwo-valuedlogicsoasnotonlytocoverthecaseofmany-valuedstatementcalculi,butofmany-valuedquantificationtheoryaswell,naturallysuggeststhepossibilityoffurtherextendingourtreatmentofmany-valuedlogictocoverthecaseofmany-valuedsets,equality,numbers,etc.第19頁，課件共45頁，創(chuàng)作于2023年2月Sincewenowhaveageneraltheoryofmanyvaluedpredicatecalculi,thereislittledoubtaboutthepossibilityofsuccessfullydevelopingsuchextendedmany-valuedtheories....weshallconsidertheircarefulstudyoneofthemajorunsolvedproblemsofmany-valuedlogic.”第20頁，課件共45頁，創(chuàng)作于2023年2月A.Mostowski,ThirtyYearsofFoundationalStudies

ActaPhilosophicaFennica,1965J.Lukasiewicz(1920’s)hopedthattherewouldbesomenon-classicallogicswhichcanbeproperlyusedinmathematicsasnon-EuclideangeometrydoesMostofnon-classicallogicsinventedsofarhavenotbeenreallyusedinmathematics,andintuitionisticlogicseemsthatuniqueoneofnon-classicallogicswhichstillhasanopportunitytocarryouttheLukasiewicz'sproject第21頁，課件共45頁，創(chuàng)作于2023年2月J.Dieudonne,Thecurrenttrendofpuremathematics,

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

量子計(jì)算的邏輯基礎(chǔ)何在?第25頁，課件共45頁，創(chuàng)作于2023年2月G.BirkhoffandJ.vonNeumann,Thelogicofquantummechanics,AnnalsofMathematics,37(1936)823-843“whatlogicalstructureonemayhopetofindinphysicaltheorieswhich,likequantummechanics,donotconformtoclassicallogic.第26頁，課件共45頁，創(chuàng)作于2023年2月Ourmainconclusion,…,isthatonecanreasonablyexpecttofindacalculusofpropositionswhichisformallyindistinguishablefromthecalculusoflinearsubspaces[ofHilbertspace]withrespecttosetproducts,linearsums,andorthogonalcomplements–andresemblestheusualcalculusofpropositionswithrespectto'and','or',and'not'.”第27頁，課件共45頁，創(chuàng)作于2023年2月Sasaki定理(1957):

(1)ThesetofallclosedsubspacesofaHilbertspacewiththeinclusionrelationisacompleteorthomodularlattice;(2)ItisamodularlatticeifandonlyiftheHilbertspaceisfinite-dimensional第28頁，課件共45頁，創(chuàng)作于2023年2月量子邏輯:

（1）Thetheoryoforthomodularlattices（2）Alogicwhosesetoftruthvaluesisanorthomodularlattice第29頁，課件共45頁，創(chuàng)作于2023年2月量子邏輯已經(jīng)存在?。ㄕ嬲模﹩栴}：

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