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

1、理論計(jì)算機(jī)科學(xué)中的幾個(gè)問題,應(yīng)明生清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系智能技術(shù)與系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室,,EATCS(歐洲理論計(jì)算機(jī)科學(xué)協(xié)會(huì))：主辦雜志： Theoretical Computer Science主辦會(huì)議：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, …),,美國的理論計(jì)算機(jī)科學(xué)：ACM STOC, IEEE FOCS算法與復(fù)雜性， 人工智能理論（如Logical AI）,,歐洲的理論計(jì)算機(jī)科學(xué)：形式化方法， 形式語義學(xué)， …,,我國在理論計(jì)算機(jī)科學(xué)（包括

5、美式、歐式）方面有許多非常出色的工作如何進(jìn)一步發(fā)展我國的理論計(jì)算機(jī)科學(xué)？,,P. R. Halmos: “問題是數(shù)學(xué)的心臟”推而廣之： “問題是一切（純）科學(xué)的心臟”發(fā)展理論計(jì)算機(jī)科學(xué)，我們需要好的問題！,,波蘭（華沙、里沃夫）數(shù)學(xué)學(xué)派的啟示：有自己特色的、根本性的問題有與國際上同類工作相同的深度,問題1：,可否建立基于量子邏輯（或其它非經(jīng)典邏輯）的計(jì)算理論？是否需要建立這樣的理論？,,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世紀(jì)邏輯學(xué)家創(chuàng)造了許多不同于經(jīng)典（Boolean）邏輯與直覺主義邏輯

12、的非經(jīng)典邏輯邏輯學(xué)家的問題: 是否可能建立基于除直覺主義邏輯之外的非經(jīng)典邏輯的數(shù)學(xué)理論？,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,,計(jì)算理論也是基于經(jīng)典（Boolean）邏輯的數(shù)學(xué)理論（理論）計(jì)算機(jī)科學(xué)家的問題：是否需要建立基于非經(jīng)典邏輯的計(jì)算理論？,,量子計(jì)算的主要研究方向:1. 物理實(shí)現(xiàn)2. 物理模型3. 數(shù)學(xué)模型4. 算法與復(fù)雜性,,問題: 量子計(jì)算的邏輯基礎(chǔ)何在?,,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,,量子邏輯已經(jīng)存在?。ㄕ嬲模﹩栴}： 能否建立基于量子邏輯的計(jì)算理論？,問題2：,何為計(jì)算智能？什么是計(jì)算可實(shí)現(xiàn)的智能？注：這里“計(jì)算智能”指的不是作為“神經(jīng)網(wǎng)絡(luò)、Fuzzy邏輯、進(jìn)化計(jì)算”等的總稱,,智能是什么?我們沒有好的答案！,,（可）計(jì)算理論回答的問題： 什么是計(jì)算？信息論回答的問題：什么是信息？,,什么是智能？我們有

25、（盲人摸象式的）答案：計(jì)算是智能，推理是智能，…,,比較一本標(biāo)準(zhǔn)的人工智能教科書與一本標(biāo)準(zhǔn)的數(shù)學(xué)教科書：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.回答的問題：拓?fù)淇臻g什么時(shí)候是可度量化的

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.,,我們沒有能夠回答問題：什么是計(jì)算可實(shí)現(xiàn)的智能？因此，我們?nèi)匀惶幱凇癱omputational AI”的史前期！,問題3：,從“Logical AI”到“Semantic AI(基于語義的AI)”?,,科學(xué)發(fā)展的內(nèi)部動(dòng)力：(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