理論計算機科學中的幾個問題

1、理論計算機科學中的幾個問題,應明生清華大學計算機科學與技術系智能技術與系統(tǒng)國家重點實驗室,,EATCS(歐洲理論計算機科學協(xié)會)：主辦雜志： Theoretical Computer Science主辦會議：ICALP (International Colloquim on Automata, Languages, and Programming),,“Theoretical Computer Science is m

2、athematical and abstract in spirit, but it derives its motivations from practical and everyday computation. Its aim is to understand the nature of computation and, as a consequence of this understanding, provide mor

3、e efficient methodologies.”,,Section A: Algorithms, automata, complexity and gamesSection B: Logic, semantics and theory of programmingSection C: Natural computing (evolutiona

4、ry computing, neural network, molecular computring, quantum computing, …),,美國的理論計算機科學：ACM STOC, IEEE FOCS算法與復雜性， 人工智能理論（如Logical AI）,,歐洲的理論計算機科學：形式化方法， 形式語義學， …,,我國在理論計算機科學（包括

5、美式、歐式）方面有許多非常出色的工作如何進一步發(fā)展我國的理論計算機科學？,,P. R. Halmos: “問題是數學的心臟”推而廣之： “問題是一切（純）科學的心臟”發(fā)展理論計算機科學，我們需要好的問題！,,波蘭（華沙、里沃夫）數學學派的啟示：有自己特色的、根本性的問題有與國際上同類工作相同的深度,問題1：,可否建立基于量子邏輯（或其它非經典邏輯）的計算理論？是否需要建立這樣的理論？,,An axiomati

6、zation of a mathematical theory consists of a system of fundamental notions as well as a set of axioms about these notions,,A mathematical theory is then the set of theorems which can be derived from the axioms,,One

7、 needs a certain logic to provide tools for reasoning in the derivation of these theorems from the axioms,,A. Heyting (1963), Axiomatic Projective Geometry, North-Holland, Amsterdam, 1963In elementary axiomatics lo

8、gic was used in an unanalyzed form,,The studies for foundations of mathematics beginning in the early of twentieth century:It had been realized that a major part of mathematics has to exploit the full power of clas

9、sical (Boolean) logic, the strongest one in the family of existing logics,,A few mathematicians took some kind of constructive position which is in more or less explicit opposition to certain forms of mathematical re

10、asoning used by the majority of the mathematical community: L. E. J. Brouwer, H. Poincare, L.Kronecker, H. Weyl,,Some of them even endeavored to establish so-called constructive mathematics, the part of mathematics

11、that could be rebuilt on constructivist principlesThe logic employed in the development of constructive mathematics is intuitionistic logic which is weaker than classical logic,,20世紀邏輯學家創(chuàng)造了許多不同于經典（Boolean）邏輯與直覺主義邏輯

12、的非經典邏輯邏輯學家的問題: 是否可能建立基于除直覺主義邏輯之外的非經典邏輯的數學理論？,J. B. Rosser and A. R. Turquette, Many-Valued Logics, North-Holland, Amsterdam, 1952,“The fact that it is thus possible to generalize The ordinary two-valued logic so

13、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 th

14、e case of many-valued sets, equality, numbers, etc.,,Since we now have a general theory of manyvalued predicate calculi, there is little doubt about the possibility of successfully developing such extended many-value

15、d theories. ... we shall consider their carefulstudy one of the major unsolved problems of many-valued logic.”,A. Mostowski, Thirty Years of Foundational Studies Acta Philosophica Fennica, 1965,J. Lukasiewicz (1920’s

16、) 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 mathematics, an

17、d intuitionistic logic seems that unique one of non-classical logics which still has an opportunity to carry out the Lukasiewicz's project,J. Dieudonne, The current trend of pure mathematics,Advances in Mathemati

18、cs 27(1978)235-255,Mathematical logicians have been developing a variety of non-classical logics such as second-order logic, modal logic and many-valued logic, but these logics are completely useless for mathematicia

19、ns working in other research areas,,計算理論也是基于經典（Boolean）邏輯的數學理論（理論）計算機科學家的問題：是否需要建立基于非經典邏輯的計算理論？,,量子計算的主要研究方向:1. 物理實現(xiàn)2. 物理模型3. 數學模型4. 算法與復雜性,,問題: 量子計算的邏輯基礎何在?,,G. Birkhoff and J. von Neumann, The logic of

20、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.,,Our main conclusion, …,

21、 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 ortho

22、gonal complements – and resembles the usual calculus of propositions with respect to 'and', 'or', and 'not'.”,,Sasaki定理(1957): (1) The set of all closed subspaces of a Hilbert space with the

23、 inclusion relation is a complete orthomodular lattice; (2) It is a modular lattice if and only if the Hilbert space is finite-dimensional,,量子邏輯: （1） The theory of orthomodular lattices（2） A logic whose set of tr

24、uth values is an orthomodular lattice,,量子邏輯已經存在?。ㄕ嬲模﹩栴}： 能否建立基于量子邏輯的計算理論？,問題2：,何為計算智能？什么是計算可實現(xiàn)的智能？注：這里“計算智能”指的不是作為“神經網絡、Fuzzy邏輯、進化計算”等的總稱,,智能是什么?我們沒有好的答案！,,（可）計算理論回答的問題： 什么是計算？信息論回答的問題：什么是信息？,,什么是智能？我們有

25、（盲人摸象式的）答案：計算是智能，推理是智能，…,,比較一本標準的人工智能教科書與一本標準的數學教科書：N. J. Nilsson, Artificial Intelligence, Morgan Kaufmann, 1998J. L. Kelley, General Topology, van Nostrand, 1955,,Nilsson書的目錄：Reactive machinesSearch in state

26、 spacesKnowledge representation and reasoningPlanning methods based on logicCommunication and integration,,Kelley書的目錄：Topological spacesMoore-Smith convergenceProduct spaces and quotient spacesEmbedding and metri

27、zationCompact spaces Uniform spacesFunction 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.回答的問題：拓撲空間什么時候是可度量化的

28、？,,S. L. Andresen, John McCarthy: father of AI, IEEE Intelligent Systems, 17:5(2002)84-85.If John McCarthy, the father of AI were to coin a new phrase for “artificial intelligence” today, he would probably use “comp

29、utational intelligence.”“If we were starting today, I think I’d use that term,” MaCarthy says.,,我們沒有能夠回答問題：什么是計算可實現(xiàn)的智能？因此，我們仍然處于“computational AI”的史前期！,問題3：,從“Logical AI”到“Semantic AI(基于語義的AI)”?,,科學發(fā)展的內部動力：(i)

30、 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 o