理论计算机科学中的几个问题精选文档.ppt

《理论计算机科学中的几个问题精选文档.ppt》由会员分享，可在线阅读，更多相关《理论计算机科学中的几个问题精选文档.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、理论计算机科学中的几个问题本讲稿第一页，共四十五页nEATCS(EATCS(欧洲理论计算机科学协会欧洲理论计算机科学协会)：主办杂志：Theoretical Computer Science主办会议：ICALP(International Colloquim on Automata,Languages,and Programming)本讲稿第二页，共四十五页“Theoretical Computer Science is mathematical and abstract in spirit,but it derives its motivations from practical and e

2、veryday computation.Its aim is to understand the nature of computation and,as a consequence of this understanding,provide more efficient methodologies.”本讲稿第三页，共四十五页Section A:Algorithms,automata,complexity and gamesSection B:Logic,semantics and theory of programmingSection C:Natural computing(evoluti

3、onary computing,neural network,molecular computring,quantum computing,)本讲稿第四页，共四十五页n美国的理论计算机科学美国的理论计算机科学：ACM STOC,IEEE FOCS算法与复杂性，人工智能理论（如Logical AI）本讲稿第五页，共四十五页n欧洲的理论计算机科学欧洲的理论计算机科学：形式化方法，形式语义学，本讲稿第六页，共四十五页n我国在理论计算机科学（包括美式、欧式）方面有许多非常出色的工作如何进一步发展我国的理论计算机科学如何进一步发展我国的理论计算机科学？本讲稿第七页，共四十五页P.R.Halmos:“问题

4、是数学的心脏问题是数学的心脏”推而广之：“问题是一切（纯）科学的心问题是一切（纯）科学的心脏脏”发展理论计算机科学，我们需要好的问题！本讲稿第八页，共四十五页n波兰（华沙、里沃夫）数学学派的启示波兰（华沙、里沃夫）数学学派的启示：有自己特色的、根本性的问题有与国际上同类工作相同的深度本讲稿第九页，共四十五页问题问题1 1：n可否建立基于量子逻辑（或其它非可否建立基于量子逻辑（或其它非经典逻辑）的计算理论？是否需要建经典逻辑）的计算理论？是否需要建立这样的理论？立这样的理论？本讲稿第十页，共四十五页nAn axiomatization of a mathematical theory consi

5、sts of a system of fundamental notions as well as a set of axioms about these notions 本讲稿第十一页，共四十五页nA mathematical theory is then the set of theorems which can be derived from the axioms本讲稿第十二页，共四十五页nOne needs a certain logic to provide tools for reasoning in the derivation of these theorems from th

6、e axioms本讲稿第十三页，共四十五页A.Heyting(1963),Axiomatic Projective Geometry,North-Holland,Amsterdam,1963nIn elementary axiomatics logic was used in an unanalyzed form本讲稿第十四页，共四十五页nThe studies for foundations of mathematics beginning in the early of twentieth century:It had been realized that a major part of

7、mathematics has to exploit the full power of classical(Boolean)logic,the strongest one in the family of existing logics本讲稿第十五页，共四十五页nA few mathematicians took some kind of constructive position which is in more or less explicit opposition to certain forms of mathematical reasoning used by the majori

8、ty of the mathematical community:L.E.J.Brouwer,H.Poincare,L.Kronecker,H.Weyl本讲稿第十六页，共四十五页nSome of them even endeavored to establish so-called constructive mathematics,the part of mathematics that could be rebuilt on constructivist principlesnThe logic employed in the development of constructive math

9、ematics is intuitionistic logic which is weaker than classical logic本讲稿第十七页，共四十五页n20世纪逻辑学家创造了许多不同于经典（Boolean）逻辑与直觉主义逻辑的非经典逻辑逻辑学家的问题逻辑学家的问题:是否可能建立基于除直觉主义逻辑之外的非经典逻辑的数学理论？本讲稿第十八页，共四十五页J.B.Rosser and A.R.Turquette,Many-Valued Logics,North-Holland,Amsterdam,1952“The fact that it is thus possible to gener

10、alize The ordinary two-valued logic so as not only tocover the case of many-valued statement calculi,but of many-valued quantification theory as well,naturally suggests the possibility of further extending our treatment of many-valued logic to cover the case of many-valued sets,equality,numbers,etc.

11、本讲稿第十九页，共四十五页Since we now have a general theory of manyvalued predicate calculi,there is little doubt about the possibility of successfully developing such extended many-valued theories.we shall consider their carefulstudy one of the major unsolved problems of many-valued logic.”本讲稿第二十页，共四十五页A.Mosto

12、wski,Thirty Years of Foundational Studies Acta Philosophica Fennica,1965nJ.Lukasiewicz(1920s)hoped that there would be some non-classical logics which can be properly used in mathematics as non-Euclidean geometry doesMost of non-classical logics invented so far have not been really used in mathemati

13、cs,and intuitionistic logic seems that unique one of non-classical logics which still has an opportunity to carry out the Lukasiewiczs project本讲稿第二十一页，共四十五页J.Dieudonne,The current trend of pure mathematics,Advances in Mathematics 27(1978)235-255nMathematical logicians have been developing a variety

14、of non-classical logics such as second-order logic,modal logic and many-valued logic,but these logics are completely useless for mathematicians working in other research areas本讲稿第二十二页，共四十五页n计算理论也是基于经典（Boolean）逻辑的数学理论（理论）计算机科学家的问题：（理论）计算机科学家的问题：是否需要建立基于非经典逻辑的计算理论？本讲稿第二十三页，共四十五页量子计算的主要研究方向量子计算的主要研究方向:

15、1.物理实现2.物理模型3.数学模型4.算法与复杂性本讲稿第二十四页，共四十五页问题问题:量子计算的逻辑基础何在?本讲稿第二十五页，共四十五页G.Birkhoff and J.von Neumann,The logic of quantum mechanics,Annals of Mathematics,37(1936)823-843“what logical structure one may hope to find in physical theories which,like quantum mechanics,do not conform to classical logic.本讲稿

16、第二十六页，共四十五页Our main conclusion,is that one can reasonably expect to find a calculus of propositions which is formally indistinguishable from the calculus of linear subspaces of Hilbert space with respect to set products,linear sums,and orthogonal complements and resembles the usual calculus of propo

17、sitions with respect to and,or,and not.”本讲稿第二十七页，共四十五页SasakiSasaki定理定理(1957):(1957):(1)The set of all closed subspaces of a Hilbert space with the inclusion relation is a complete orthomodular lattice;(2)It is a modular lattice if and only if the Hilbert space is finite-dimensional本讲稿第二十八页，共四十五页量子逻辑

18、量子逻辑:（1）The theory of orthomodular lattices（2）A logic whose set of truth values is an orthomodular lattice本讲稿第二十九页，共四十五页量子逻辑已经存在！（真正的）问题：（真正的）问题：能否建立基于量子逻辑的计算理论？本讲稿第三十页，共四十五页问题2：何为计算智能？什么是计算可实现的何为计算智能？什么是计算可实现的智能？智能？注：这里“计算智能”指的不是作为“神经网络、Fuzzy逻辑、进化计算”等的总称本讲稿第三十一页，共四十五页n智能是什么?我们没有好的答案！本讲稿第三十二页，共四十五页n

19、（可）计算理论（可）计算理论回答的问题：什么是计算？n信息论信息论回答的问题：什么是信息？本讲稿第三十三页，共四十五页n什么是智能？我们有（盲人摸象式的）答案：计算是智能，推理是智能，本讲稿第三十四页，共四十五页n比较一本标准的人工智能教科书与一本标准的数学教科书：N.J.Nilsson,Artificial Intelligence,Morgan Kaufmann,1998J.L.Kelley,General Topology,van Nostrand,1955本讲稿第三十五页，共四十五页Nilsson书的目录书的目录：I.Reactive machinesII.Search in stat

20、e spacesIII.Knowledge representation and reasoningIV.Planning methods based on logicV.Communication and integration本讲稿第三十六页，共四十五页Kelley书的目录书的目录：I.Topological spacesII.Moore-Smith convergenceIII.Product spaces and quotient spacesIV.Embedding and metrizationV.Compact spaces VI.Uniform spacesVII.Functi

21、on spaces本讲稿第三十七页，共四十五页The Nagata-Smirnov Metrization Theorem:A topological space is metrizable if and only if it is regular and has a sigma-locally finite base.回答的问题：拓扑空间什么时候是可度量化的？本讲稿第三十八页，共四十五页S.L.Andresen,John McCarthy:father of AI,IEEE Intelligent Systems,17:5(2002)84-85.If John McCarthy,the fa

22、ther of AI were to coin a new phrase for“artificial intelligence”today,he would probably use“computational intelligence.”“If we were starting today,I think Id use that term,”MaCarthy says.本讲稿第三十九页，共四十五页n我们没有能够回答问题：什么是计算可实现的智能？n因此，我们仍然处于“computational AI”的史前期！本讲稿第四十页，共四十五页问题3：从从“Logical AI”到到“Semanti

23、c AI(基于基于语义的语义的AI)AI)”?本讲稿第四十一页，共四十五页n科学发展的内部动力科学发展的内部动力：(i)S.R.Buss,A.S.Kechris,A.Pillay and R.A.Shore,The Prospects for mathematical logic in the twenty-first century,The Bulletin of Symbolic Logic 7(2001)169-196.本讲稿第四十二页，共四十五页“True AI will involve semantic reasoning based on machine understanding.”(ii)如何建立AI与Semantics的桥梁？本讲稿第四十三页，共四十五页n科学发展的外部动力：科学发展的外部动力：Semantic web,Semantic Grid本讲稿第四十四页，共四十五页敬请指教！谢谢！本讲稿第四十五页，共四十五页